Stosując (matematycznej) Wektor w std :: map

Question

Powiązane: what can I use as std::map keys?

musiałem utworzyć odwzorowanie gdzie konkretne najważniejsze miejsca w przestrzeni mapie wykazów obiektów. std::map wydawało się to możliwe.

Więc jestem wpisując się std::map na xyz Vector

class Vector 
{ 
    float x,y,z 
} ; 

i robię std::map<Vector, std::vector<Object*> >. Zauważ, że klucz tutaj jest nie jest a std::vector, jest to obiekt z class Vector, który jest po prostu wektorem matematycznym xyz mojego własnego tworzenia.

celu wytworzenia „ściśle słaby zamawiania” Pisałem następujące przeciążenie dla operator<:

bool Vector::operator<(const Vector & b) const { 
    // z trumps, then y, then x 
    if(z < b.z) 
    { 
     return true ; 
    } 
    else if(z == b.z) 
    { 
     if(y < b.y) 
     { 
     // z == b.z and y < b.y 
     return true ; 
     } 
     else if(y == b.y) 
     { 
     if(x < b.x) 
     { 
      return true ; 
     } 
     else if(x == b.x) 
     { 
      // completely equal 
      return false ; 
     } 
     else 
     { 
      return false ; 
     } 
     } 
     else 
     { 
     // z==b.z and y >= b.y 
     return false ; 
     } 
    } 
    else 
    { 
     // z >= b.z 
     return false ; 
    } 
    } 

Jest trochę długi, ale przede wszystkim sprawia, że ​​tak może być dowolny wektor konsekwentnie mówi się, że mniej niż jakakolwiek inna wektor ((-1, -1, -1) < (-1, -1,1) i (-1, -1, 1)> (-1, -1, -1) na przykład).

Mój problem polega na tym, że to jest naprawdę sztuczne i chociaż je zakodowałem i działa, stwierdzam, że "zanieczyszcza" moją klasę Vector (matematycznie) za pomocą tego naprawdę dziwnego, sztucznego, nie matematycznego pojęcia "mniej niż" dla wektora.

Ale muszę utworzyć mapowanie, w którym określone kluczowe lokalizacje w mapie obszaru do niektórych obiektów, i std :: map wydaje się sposób to zrobić.

Sugestie? Gotowe rozwiązania gotowe!

Answer 1

Zamiast definiowania operator< dla klasy klucza, możesz nadać mapie niestandardowy komparator. Jest to obiekt funkcji, który pobiera dwa argumenty i zwraca true, jeśli pierwszy występuje przed drugim. Coś takiego:

struct CompareVectors 
{ 
    bool operator()(const Vector& a, const Vector& b) 
    { 
     // insert comparison code from question 
    } 
}; 

typedef std::map<Vector, Value, CompareVectors> VectorValueMap; 

Answer 2

Myślę, że twoje podejście jest w porządku. Jeśli martwisz się o zanieczyszczanie klasy Vector, to wierzę, funkcja stand-alone będzie działać tak samo dobrze:

bool operator<(const Vector& lhs, const Vector& rhs) 
{ 
    ... 
} 

ale tylko słowo ostrzeżenia: co robisz tutaj jest dość ryzykowne. Często występują błędy w obliczeniach zmiennoprzecinkowych. Załóżmy, że wstawiłeś jakiś punkt do mapy. Następnie obliczysz punkt i sprawdzisz mapę, aby sprawdzić, czy jest tam. Nawet jeśli z matematycznego punktu widzenia drugi punkt jest taki sam jak pierwszy, nie ma gwarancji, że znajdzie się on na mapie.

Answer 3

Myślę, że std::tr1::unordered_map jest dokładnie tym, czego potrzebujesz. Nie będzie wymagana ścisła słaba kolejność. GCC ma również coś podobnego w przestrzeni nazw tr1. Lub przejdź na Boost.Unordered.

nieuporządkowanego odpowiedniki z bardziej pieszym map lub set daje dwie zalety:

• Nie trzeba zdefiniować mniej niż gdzie żaden operator ma sens

• tabel mieszania może działają lepiej niż zbilansowane drzewa binarne, przy czym ten drugi jest preferowaną metodą implementacji uporządkowanych struktur: map lub set. Ale to zależy od wzoru/wymagań dostępu do danych.

Tak, tylko iść do przodu i zastosowanie:

typedef std::tr1::unordered_map<Vector, std::vector<Object *> > VectorMap; 

To sprawia, że ​​korzystanie z domyślnej funkcji mieszającej, która dba o wkładania/poszukiwaniu swojej mapie.

PS: obiekt > > zostanie naprawiony w nadchodzących standardach, a tym samym w przyszłych wersjach kompilatora.

Answer 4

Można go oddzielić od klasy. Następnie określ go jako operator porównania dla std :: map.

std::map<Vector,std::vector<Object*>,Compare> data; 

Gdzie Porównaj to funkcja (lub funktor), która może porównywać obiekty Vector holowania.
Wydaje mi się, że możesz uprościć operację porównywania.

bool Compare<(const Vector& lhs, const Vector& rhs) 
{ 
    // z trumps, then y, then x 
    if(lhs.z < rhs.z) 
    { return true ; 
    } 
    else if (lhs.z > rhs.z) 
    { return false; 
    } 
    // Otherwise z is equal 
    if(lhs.y < rhs.y) 
    { return true ; 
    } 
    else if(lhs.y > rhs.y) 
    { return false; 
    } 
    // Otherwise z and y are equal 
    if (lhs.x < rhs.x) 
    { return true; 
    } 
    /* Simple optimization Do not need this test 
     If this fails or succeeded the result is false. 
    else if(lhs.x > rhs.x) 
    { return false; 
    }*/ 
    // Otherwise z and y and x are all equal 
    return false; 
} 

Zawiadomienie, że testujemy mniej, a następnie więcej, a następnie wypadamy za równe. Osobiście lubię prostotę tego stylu. Ale często widzę to ściśnięciu tak:

bool Compare<(const Vector& lhs, const Vector& rhs) 
{ 
    // Note I use three separate if statements here for clarity. 
    // Combining them into a single statement is trivial/ 
    // 
    if ((lhs.z < rhs.z)          ) {return true;} 
    if ((lhs.z == rhs.z) && (lhs.y < rhs.y)     ) {return true;} 
    if ((lhs.z == rhs.z) && (lhs.y == rhs.y) && (lhs.x < rhs.x)) {return true;} 

    return false; 
} 

Answer 5

To normalne, że można zauważyć, że klasa jest zanieczyszczona przez to. Jest również zanieczyszczony z punktu widzenia CS.

Normalnym sposobem definiowania takiego operatora są funkcje bezpłatne (potencjalnie przyjacielskie).

Jednak pierwsze pytanie, które należy sobie zadać, brzmi: czy ma to sens. Problem polega na tym, że zdefiniowałeś metodę dla swojej klasy, która ma znaczenie tylko w ograniczonym kontekście, ale jest dostępna wszędzie. Dlatego „zanieczyszczenie” kopnięcia uczucie

Teraz, gdybym potrzebował takiego mapowanie z Vector do kolekcji Object s, tu są pytania, chciałbym zapytać siebie.

• Do I potrzebujesz zamówić Vector? Tak: std::map, nr: std::unordered_map lub std::tr1::unodered_map lub std::hash_map lub boost::unordered_map.
• Czy ta kolekcja jest właścicielem Object? Tak: boost::ptr_vector<Object> lub std::vector< std::unique_ptr<Object> >, nr: std::vector<Object*>

Teraz, w obu przypadkach (map i unordered_map), to będzie trzeba coś przekształcić mój klucz. Kolekcja dostarcza dodatkowy argument szablonu, który przyjmuje typ Functor.

Uwaga: jak wspomniano w innej odpowiedzi, reprezentacja zmiennoprzecinkowa jest niezręczna w komputerze, dlatego prawdopodobnie będziesz musiał rozluźnić znaczenie równości i zignorować cyfry niższego rzędu (ile zależy od twoich obliczeń).