środa, 28 listopada 2007

Jak zrobić set'a intów z własnym operatorem mniejszości

Czasem potrzebujemy utworzyć zbiór (set) liczb całkowitych (int'ów), w którym inaczej niż zwykle chcemy porównywać liczby.

Tak się dzieje np. w algorytmie Dijkstry, gdzie najmniejszy element w zbiorze to ten, który ma najmniejszą ogległość do źródła.

Załóżmy więc, że dana jest tablica globalna
int dist[1000000]; // odległości od źródła w alg. Dijkstry

Zbiór numerów wierzchołków tworzymy wówczas następująco, kluczowa jest struktura z operatorem wywołania operator():
struct cmp
{
// czy a jest mniejsze od b
bool operator() (const int &a, const int &b)
{
if (dist[a] < dist[b]) return true;
if (dist[a] > dist[b]) return false;
return a<b;
}
};
set<int, cmp> kopiec; // ;-)
Prześlij komentarz