Bleibt Zeiger zu Value bei unordered_map gleich?

Eisflamme

Hi,

wenn ich ne unordered_map<int, Obj> habe und irgendwo Zeiger auf Obj speichere und später dann ganz viel einfüge oder/auch lösche, bleiben die besagten Zeiger dann gültig oder nicht?

Viele Grüße
Eisflamme

Skym0sh0

Du meinst sowas?

struct Obj
{};

int main()
{
	std::unordered_map<int, Obj> map;

	map[0] = Obj();
	Obj * p = &map[0];

	for(int i = 0; i < N; i++)
		map[rand()] = Obj();

	// p noch konstant

	return 0;
}

Das dürfte crashen, denn der Container muss früher oder später sicherlich mal neuen Speicher anfordern und dann müssen die Objekte kopiert oder gemovet werden. Das wäre mein intuitives Gefühl.

Aber:

<a href= schrieb:

Reference">
Iterator validity
On most cases, all iterators in the container remain valid after the insertion. The only exception being when the growth of the container forces a rehash. In this case, all iterators in the container are invalidated.

A rehash is forced if the new container size after the insertion operation would increase above its capacity threshold (calculated as the container's bucket_count multiplied by its max_load_factor).

References to elements in the unordered_map container remain valid in all cases, even after a rehash.

Wobei sich das auf Iteratoren bezieht...

Nathan

Zu faul für Standard:

http://en.cppreference.com/w/cpp/container/unordered_map schrieb:

References and pointers to either key or data stored in the container are only invalidated by erasing that element, even when the corresponding iterator is invalidated.

Also nein, sie bleiben gültig.

Ethon

@Sky: Eine unordered map ist ein array von linked lists. Wenn das array wächst bleiben die Listenknoten trotzdem valid.

volkard

Nathan schrieb:

Zu faul für Standard:

http://en.cppreference.com/w/cpp/container/unordered_map schrieb:

References and pointers to either key or data stored in the container are only invalidated by erasing that element, even when the corresponding iterator is invalidated.

Also nein, sie bleiben gültig.

Uff. Ungewöhnlich, daß der Standard eine Implementierung so genau festlegt.

Eisflamme

Hi,

super, danke.

Viele Grüße
Eisflamme

Skym0sh0

Ethon schrieb:

@Sky: Eine unordered map ist ein array von linked lists. Wenn das array wächst bleiben die Listenknoten trotzdem valid.

Cool, das wusste ich nicht. Danke dir :>

hustbaer

volkard schrieb:

Nathan schrieb:

Zu faul für Standard:

http://en.cppreference.com/w/cpp/container/unordered_map schrieb:

References and pointers to either key or data stored in the container are only invalidated by erasing that element, even when the corresponding iterator is invalidated.

Also nein, sie bleiben gültig.

Uff. Ungewöhnlich, daß der Standard eine Implementierung so genau festlegt.

Nicht nur ungewöhnlich, sondern mMn. total bekloppt.
Damit wird effektiv verhindert dass jemand ne Implementierung baut die bei kleinen trivial kopierbaren Keys & Values auch nur ansatzweise konkurrenzfähig mit einer handgeschnitzten Lösung ist.

Würde mich echt interessieren was der Grund war diese Garantien festzuschreiben.
Ich meine, dort wo es wichtig ist dass sich Adressen nicht ändern hätte man auch einfach unique_ptr<Value> statt Value speichern können.

hustbaer

Ethon schrieb:

@Sky: Eine unordered map ist ein array von linked lists. Wenn das array wächst bleiben die Listenknoten trotzdem valid.

SO genau ist die Implementierung sicher nicht vorgeschrieben.
Und wäre da nicht diese mMn. völlig unnötige Garantie dass sowohl Adressen als auch Iteratoren gültig bleiben, dann gäbe es sehr sehr viele andere Möglichkeiten ne unordered map zu implementieren.

Ethon

Was außer chained hashing kann denn die Anforderungen erfüllen?
Ist doch das gleiche bei map, bei der mir keine Implementierung außer balancierten Bäumen einfallen würde.

Marthog

Ethon schrieb:

Was außer chained hashing kann denn die Anforderungen erfüllen?

Man kann z.B. ein Array mit pointern machen (aehnlich, aber nicht gleich). Ich kann mir auch noch komplizierte Methoden ausdenken, bei denen Elemente direkt im Feld gespeichert werden und beim rehash durch Pointer, indices, whatever auf das alte Feld ersetzt werden. Ob sich das lohnt? Wahrscheinlich nicht. Aber vielleicht wird mal eine neue Methode gefunden und dann darf das einfach implementiert werden, ohne dass der Standard irgendwelchen unnuetzen Kram vorgibt.