std::map ohne less

Badestrand

Jover schrieb:

Badestrand schrieb:

Was spricht dagegen, einfach eine Ordnungsrelation zu definieren

weil eine ordnungsrelation einfach keinen sinn machen würde.

Ist doch egal, wird doch nur zum sortieren verwendet.

David_pb schrieb:

Oder du verwendest eben z.B. std::equal_to als Vergleicher. Nur ist dein Baum dann eben nicht besonders gut aus balanciert.

Hm, ich glaube der MSVC erwartet im Debug-Modus eine strikte Ordnung und prüft auf if(rel(a,b)) assert(!rel(b,a));

Dravere

Badestrand schrieb:

David_pb schrieb:

Oder du verwendest eben z.B. std::equal_to als Vergleicher. Nur ist dein Baum dann eben nicht besonders gut aus balanciert.

Hm, ich glaube der MSVC erwartet im Debug-Modus eine strikte Ordnung und prüft auf if(rel(a,b)) assert(!rel(b,a));

Der C++ Standard schreibt es sogar vor:

C++ Standard 14882:2003 - 23.1.2 Associative containers schrieb:

² Each associative container is parameterized on Key and an ordering relation Compare that induces a strict weak ordering (25.3) on elements of Key . In addition, map and multimap associate an arbitrary type T with the Key . The object of type Compare is called the comparison object of a container. This comparison object may be a pointer to function or an object of a type with an appropriate function call operator.

³ The phrase "equivalence of keys" means the equivalence relation imposed by the comparison and not the operator== on keys. That is, two keys k1 and k2 are considered to be equivalent if for the comparison object comp, comp(k1, k2) == false && comp(k2, k1) == false .

Grüssli

unskilled

Wenn du die Ordnungsrelation nicht in deiner Punkt-Klasse haben möchtest, dann machs doch so in etwa:

#include <set>

struct point
{
	float x, y;
};

struct point_less
{
	bool operator() (const point &lhs, const point &rhs) const
	{
		if(lhs.x == rhs.x)
			return lhs.y < rhs.y;
		else
			return lhs.x < rhs.x;
	}
};

int main()
{
	std::set<point, point_less> my_map;
}

bb

edit: das gleiche geht natürlich auch mit map und nicht set^^ weiß auch nich so genau, wieso ich set genommen hatte

edit: operator gebaut ^^

Jover

ich fürchte, dass die QPoint klasse eine so komplexe struktur hat, dass eine strikte ordnung kaum darauf zu definieren ist.

volkard

Jover schrieb:

ich fürchte, dass die QPoint klasse eine so komplexe struktur hat, dass eine strikte ordnung kaum darauf zu definieren ist.

Deine Befürchtungen kann ich zersteuen:

bool less(QPoint const& a,QPont const& b){
   if(a.x<b.x) return true;
   if(b.x<a.x) return false;

   if(a.y<b.y) return true;
   if(b.y<a.y) return false;

   if(a.z<b.z) return true;
   if(b.z<a.z) return false;

   if(a.hue<b.hue) return true;
   if(b.hue<a.hue) return false;

   ...//noch 25854 andere attribute
   return false;
}

volkard

struct point_less
{
friend bool operator< (const point &lhs, const point &rhs)

() statt <

Hast du schon einmal in Erwägung gezogen, dass std::map hier die falsche Struktur ist? Versuch es doch mal mit einer Hashtabelle.

Jover

hash_map -> genau das was ich brauche.

danke!

volkard

Tippgeber schrieb:

Hast du schon einmal in Erwägung gezogen, dass std::map hier die falsche Struktur ist? Versuch es doch mal mit einer Hashtabelle.

Ob die Hashtable oder der Baum passender sind, hängt von den zu erwartenden Operationen ab, wie oft Einfügungen, Löschungen, Suchen?
Außerdem: Manche Leute haben ein sehr schlechtes Gefühl beim Hashen von doubles, was vor allem Daran liegt, daß man sich alle Epsilon-Tests komplett verbaut.

unskilled

volkard schrieb:

struct point_less
{
friend bool operator< (const point &lhs, const point &rhs)

() statt <

korrekt, habs geändert ^^

volkard schrieb:

Tippgeber schrieb:

Hast du schon einmal in Erwägung gezogen, dass std::map hier die falsche Struktur ist? Versuch es doch mal mit einer Hashtabelle.

Ob die Hashtable oder der Baum passender sind, hängt von den zu erwartenden Operationen ab, wie oft Einfügungen, Löschungen, Suchen?
Außerdem: Manche Leute haben ein sehr schlechtes Gefühl beim Hashen von doubles, was vor allem Daran liegt, daß man sich alle Epsilon-Tests komplett verbaut.

Das ist ein Argument.

Was ich halt nicht machen würde, wäre einen Kleiner-Als-Operator für eine Punktklasse zu definieren. Aber gegen einen Funktor oder eine Funktion, die nur bei der Map angegeben wird und sonst nirgends für Verwirrung sorgt, spricht nichts.

Nur weil du zu faul bist, eine Ordnungsrelation zu definieren, solltest du nicht auf Hash-Maps wechseln.