unorderd_map emplace

[Eisflamme]

Hi,

ich habe folgende unordered_map:

struct intHash {int operator()(int key) {return key;}};

typedef std::unordered_map<int, MyPOD, intHash> Map;

Map x;

Manchmal möchte ich ein Element finden und zurückgeben. Wenn es noch nicht existiert, möchte ich es erstellen und dann zurückgeben.

Spricht irgendwas dagegen IMMER emplace zu nutzen, da es ja bei einem bereits vorhanden Element einfach den iterator auf das Bestehende zurückliefert? Oder hat das irgendwelche Performancenachteile?

Gruß
Eike

[poddylot]

Was spricht gegen operator[] wenn du sowieso einen POD hast? Bei einer unordered_map spielt das wohl kaum ins Gewicht.

[Ruvi]

Eisflamme schrieb:

Spricht irgendwas dagegen IMMER emplace zu nutzen, da es ja bei einem bereits vorhanden Element einfach den iterator auf das Bestehende zurückliefert? Oder hat das irgendwelche Performancenachteile?

Hi,

nach meiner Meinung spricht nur etwas gegen emplace, wenn irgendeines deiner Objekte aus dem Konstruktor eine exception werfen könnte.
Mit emplace verlierst Du (soweit ich mich erinnere) die Strong exception guarantee, weil das Objekt gleich innerhalb der Datenstruktur erstellt wird.

[lolbot]

Ruvi schrieb:

nach meiner Meinung spricht nur etwas gegen emplace, wenn irgendeines deiner Objekte aus dem Konstruktor eine exception werfen könnte.
Mit emplace verlierst Du (soweit ich mich erinnere) die Strong exception guarantee, weil das Objekt gleich innerhalb der Datenstruktur erstellt wird.

lol? In welchem Container sollte es je einen Unterschied zwischen kopieren und in-place erstellen geben?

[Ruvi]

lolbot schrieb:

lol? In welchem Container sollte es je einen Unterschied zwischen kopieren und in-place erstellen geben?

Versteh jetzt nicht ganz was es da zu lol'en gibt.

Strong exception safety: Can be implemented fairly easily by doing any allocation first and then copying into a temporary buffer that is eventually swapped if no errors are encountered. In this case, insertion of x into v will either succeed, or v will remain unchanged.

Das ist bei emplace oder emplace_back nicht der Fall da die Datenstruktur in jedem Fall veraendert ist, da du dass Objekt innerhalb der Datenstruktur erstellst.
Du hast fuer emplace_back also nur eine Basic exception safety.

Basic exception safety:
Implemented by ensuring that the size field is guaranteed to be updated if x is successfully inserted. Also, all allocations need to be handled in a way that prevents any chance of a memory leak, regardless of failure.

Das ist auch der Hauptgrund warum die Funktion push_back nicht geaendert wurde und man sich entschieden hat eine weitere Funktion emplace/ emplace_back zu implementieren, da es unter Umstaenden interfaces gibt die auf der Annahme beruhen, dass bei einer exception nichts veraendert ist.

Ich persoenlich verwende niemals emplace oder emplace_back, wenn die Moeglichkeit besteht, dass mein Konstruktor eine exception werfen koennte.
(Out of Memory zaehle ich mal nicht dazu).

Denn ich persoenlich finde es mehr als unschoen, dass meine Datenstruktur im Fall von emplace/back nicht in dem Zustand ist, wie sie vor der Exception war.

Beispiel:

#include <vector>
#include <exception>
using namespace std;

class Foo
{
public:
	Foo(){ throw(std::runtime_error("Error")); }
};

int main()
{
	vector<Foo> alpha;
	vector<Foo> beta;

	try{
	alpha.push_back(Foo());
	}
	catch (std::runtime_error)
	{
                //breakpoint setzen Capacity des Vectors = 0; 
                //Er wurde definitiv nicht veraendert
		int a = 5;
	}
	try{
	beta.emplace_back();
	}
	catch (std::runtime_error)
	{
                //breakpoint setzen Capacity des Vectors ist = 1;
                //Mit anderen Worten die Datenstruktur ist durch die Exception
                //dauerhaft veraendert worden.  Der Speicher der alloziert wurde
                //kann nicht weggeraeumt werden da man ansonsten die komplette
                //Datenstruktur neubauen muesste.
		int c = 7;
	}
}

P.S.: Das ganze Problem an der Sache wird einem nochmal deutlicher, wenn in meiner Klasse Foo jetzt noch ein paar ints sind und ich versuche 100.000 Pushbacks zu machen, die scheitern weil irgendwas generelles nicht geht.

Du hast dann mit anderen Worten einen riesigen leeren Vector rumliegen der unter Umstaenden hunderte von MB Speicher belegt und das alles nur weil Du dir ein copy/move ersparen wolltest.

[lolbot]

Ruvi schrieb:

lolbot schrieb:

lol? In welchem Container sollte es je einen Unterschied zwischen kopieren und in-place erstellen geben?

Versteh jetzt nicht ganz was es da zu lol'en gibt.

Weil es falsch ist. vector::emplace_back nach Standard eine Strong Exception Guarantee (vorausgesetzt die Elemente sind kopierbar oder noexcept move-bar).

Ruvi schrieb:

Das ist bei emplace oder emplace_back nicht der Fall da die Datenstruktur in jedem Fall veraendert ist, da du dass Objekt innerhalb der Datenstruktur erstellst.

Also das Objekt existiert noch gar nicht, wenn eine Ausnahme geworfen wurde.

Zu deinem Beispiel: Sieht für mich nach einem Bug in deiner Standardbibliothek aus. Passiert das bei push_back nicht?

Die Aussage

Der Speicher der alloziert wurde
//kann nicht weggeraeumt werden da man ansonsten die komplette
//Datenstruktur neubauen muesste.

verstehe ich nicht. Wo genau ist das Problem mit
1. Speicher allokieren
2. Neues Element erzeugen. Falls Ausnahme => Speicher freigeben
3. Alte Elemente kopieren. Falls Ausnahme => Elemente löschen, Speicher freigeben.
4. Alte Elemente löschen, Zeiger umbiegen, Speicher freigeben.

Nebenbei geht es hier um unordered_map und dürfte emplace auch in deiner seltsame Standardbibliothek keinen Unterschied machen.

[lolbot]

Ruvi schrieb:

P.S.: Das ganze Problem an der Sache wird einem nochmal deutlicher, wenn in meiner Klasse Foo jetzt noch ein paar ints sind und ich versuche 100.000 Pushbacks zu machen, die scheitern weil irgendwas generelles nicht geht.

Du hast dann mit anderen Worten einen riesigen leeren Vector rumliegen der unter Umstaenden hunderte von MB Speicher belegt und das alles nur weil Du dir ein copy/move ersparen wolltest.

Glaube ich nicht. Kannst du das nachweisen?

[Ruvi]

lolbot schrieb:

Glaube ich nicht. Kannst du das nachweisen?

Interessant, Du hast recht.
Ich bin jetzt davon ausgegangen, dass sich das Problem addiert.

Nichtsdestotrotz habe ich mit push_back nicht das Problem, dass sich die Kapazitaet veraendert, weil das Objekt ausserhalb des Vectors erstellt wird.

Bei emplace_back bleibt der Vector mit 1 Capacity stehen in meinem Beispiel.
Vielleicht kann ja jemand anderes nochmal gucken aber die Strong exception gurantee waere damit nicht gegeben.

[lolbot]

Scheint ein Problem mit dem VC++ zu sein.

#include <vector>
#include <stdexcept>
#include <iostream>
using namespace std;

struct AlwaysThrow {
    AlwaysThrow(){ throw(std::runtime_error("Error")); }
};
struct ThrowOnCopy {
    ThrowOnCopy()=default;
    ThrowOnCopy(ThrowOnCopy const&) { throw(std::runtime_error("Error")); }
};

int main() {
    {
        vector<AlwaysThrow> v;
        try { v.emplace_back(); }
        catch (...) { std::cout << v.size() << "/" << v.capacity() << '\n'; }
    }
    {
        vector<ThrowOnCopy> v;
        try { v.push_back(ThrowOnCopy()); }
        catch (...) { std::cout << v.size() << "/" << v.capacity() << '\n'; }
    }
}

Gibt mit gcc und clang jeweils 0/0 aus, mit vc++ allerdings 0/1. Bei ThrowOnCopy darf alles passieren (nur Basic Guarantee), im ersten Fall sollte aber meinem Verständnis nach 0/0 herauskommen.

Hat jemand Lust, einen Bugreport zu erstellen?

[vector.modifiers]/1 schrieb:

template <class... Args> void emplace_back(Args&&... args);

Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid. If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator of T or by any InputIterator operation there are no effects. If an exception is thrown by the move constructor of a non- CopyInsertable T , the effects are unspecified.

PS: @Microsoft: lol!

[Ruvi]

lolbot schrieb:

Hat jemand Lust, einen Bugreport zu erstellen?

Ich habe mal einen erstellt> https://connect.microsoft.com/VisualStudio/feedback/details/1653220

[sebi707]

Ruvi schrieb:

lolbot schrieb:

Hat jemand Lust, einen Bugreport zu erstellen?

Ich habe mal einen erstellt> https://connect.microsoft.com/VisualStudio/feedback/details/1653220

Das Problem (wenn es überhaupt eins ist) ist bei VS2015 auch noch vorhanden. Mal sehen wann sich STL meldet.

[hustbaer]

BTW: Ist bei std::vector ne "small object optimization" erlaubt (wie z.B.: bei std::string )?
Das ist zwar nicht das Problem (hab's extra ausprobiert - .capacity() ist for dem erfolglosen emplace wirklich 0), aber würde mich interessieren ob eine Implementierung das machen darf.

[sebi707]

Scheinbar nicht. http://stackoverflow.com/questions/8190950/may-stdvector-make-use-of-small-buffer-optimization

[hustbaer]

Cool, danke

[Eisflamme]

Da hier niemand irgendwas wirft, klappt emplace.

operator[] geht auch, stimmt.

Danke!