Insert/emplace in verschachtelte map<char, vector<unique_ptr>>



  • Hi, folgender Programmschnipsel:

    typedef std::unordered_map<Key, std::unique_ptr<ValueType>> KeyValueMap;
    struct BlockElementNew {
                std::vector<std::string> identity;
                KeyValueMap condition;
    }
    typedef std::vector<std::unique_ptr<BlockElementNew>> BlockListNew;
    typedef std::unordered_map<Block, BlockListNew> ConfigBlockNew;
    
    
    ConfigBlockNew blocks;
    Block blockType = Block::nothing;
    std::unique_ptr<BlockElementNew> block_ptr;
    
    int i = 0;
    while(i++ < 5) {
    
    // ..
    // unwichtiger code
    // ...
                    if (block_ptr) {
    
                                    ConfigBlockNew::iterator it = blocks.find(blockType);
                                    if (it == blocks.end()) {
                                    // Wie füge ich "block_ptr" in place in die map?
    
                                    //auto result = blocks.emplace(ConfigBlockNew::value_type(blockType, { } ));
                                    //auto result = blocks.emplace(blockType, BlockListNew::value_type(std::make_unique<BlockElementNew>()));
                                    //auto result = blocks.insert(blockType, BlockListNew::value_type(std::move(block_ptr)) );
                                    } else {
                                                   it->second.push_back(std::move(block_ptr));
                                    }
    
                    block_ptr.reset();
                    }
    }
    
    1. Meine Frage, wie ist der richtige Aufruf von insert/emplace um das Element welches vor der Schleife (block_ptr) erzeugt wurde direkt in die Liste zu verschieben.

    2. Und zweite frage, ist es nach dem verschieben noch sicher ".reset()" auf zu rufen? Der Grund liegt darin das in der while mit block_ptr gearbeitet wird und auch einige if abfragen kommen ob block_ptr true ist oder nicht. Nach dem .reset() kann es sein, das block_ptr im weiteren Verlauf wieder mit std::make_unique neue zugewiesen wird.

    3. Macht es überhaupt Sinn std::vector<std::unique_ptr<BlockElementNew>> zu nutzen? Oder sollte man das unique_ptr in diesem Fall weg lassen? ValueType ist ein Generic struct was dafür sorgt das ich in allen abgeleiteten struct einige Operator implementieren muss.


  • Mod

    Warum ist ConfigBlockNew nicht einfach eine unordered_multimap<Block, BlockElementNew>? Dann sparst du dir die gesamte Logik und vermeidest noch Duplikate in der inneren Liste (falls das intendiert ist).

    Ansonsten wäre eine elegantere Art, das Element einzufügen, mittels try_emplace, wodurch du zweifaches Suchen in der Map (einmal in find und danach in emplace) vermeidest:

    auto [it, inserted] = blocks.try_emplace(blockType, BlockListNew{move(block_ptr)});
    if (!inserted)
      it->second.push_back(std::move(block_ptr));
    

    Zu deiner zweiten Frage: Natürlich ist es sicher, einen smart pointer nach dem moven neu zuzuweisen (was auch eines der Ziele von Move-Semantik ist). Aber es ist überflüssig, den Zeiger wiederholt zu verwenden, statt ihn lokaler zu definieren, was zu saubererem Code führt.
    Ich würde vorschlagen, du zeigst auch den Code, den du für unwichtig befindest, und erklärst deine Entscheidungen bzgl. Datenstrukturen. Dann kann man mehr dazu sagen.



  • @Columbo Es lebt O.O



  • Ich würde vielleicht auch bei Listen mit Smart Pointern auf vector verzichten. Dieser Container droht bei jeder Modifizierung seiner Sequenz seinen Speicher zu reallokieren. Das macht nicht nur alte Referenzen kaputt, sondern kann auch beispielsweise zu überflüssigen Reference-Counting-Code führen, wenn du da beispielsweise einen shared_ptr<> reinsteckst. In solchen Fälle würde ich also immer eine std::list<> bevorzugen.

    Achtung, EDIT: Stimmt leider nicht ganz.


  • Mod

    @spiri Wie wir im Forum schon oft eruiert haben, ist eine list so gut wie nie einem vector vorzuziehen. Keine Ahnung, was dein Argument mit dem reallozieren da verloren hat.



  • Das mein ich:

    #include <iostream>
    
    static std::size_t tote_mietz = 0;
    
    struct foo{
        ~foo(){
            ++tote_mietz;
        }
    };
    
    
    #include <list>
    #include <vector>
    
    
    template<typename C>
    void test(C& container){
        for(int n=0; n!=10; ++n)
            container.emplace_back();
    }
    
    int main(){
        {
            std::vector<foo> vec;
            test(vec);
        }
    
        std::cout << tote_mietz << " tote Mietzen.\n";
        tote_mietz = 0;
    
        {
            std::list<foo> list;
            test(list);
        }
    
        std::cout << tote_mietz << " tote Mietzen.\n";
    }
    

    Durch die Reallokationen die der vector macht wird immer häufiger der Destruktor aufgerufen. Wenn man jetzt Datentypen hat, wo im Dtor immer irgendwas gemacht wird (z.b. reference counting), dann hat man eben durch den vector vermehrt unnötigen reference counting code den man ausführt.

    Und darum würde ich bei sowas wie nem shared_ptr<> dann eher auf ne list<> zugreifen, weil die dir 10 tote Mietzen garantiert. 🙂

    EDIT: Hm, die list<> ist tatsächlich etwas langsamer. Hätt ich nicht gedacht 🙂

    #include <iostream>
    #include <chrono>
    #include <memory>
    
    using namespace std::chrono;
    
    template<typename Function>
    void speedtest(Function&& func){
        auto start = system_clock::now();
        func();
        std::cout << duration_cast<milliseconds>(system_clock::now() - start).count() << '\n';
    }
    
    
    template<typename T>
    void f(){
        T container;
    
        for(std::size_t n=0; n!=10000000; ++n)
            container.emplace_back(std::make_shared<int>(1));
    }
    
    
    #include <vector>
    #include <list>
    
    int main(){
        speedtest(&::f<std::vector<std::shared_ptr<int>>>);
        speedtest(&::f<std::list<std::shared_ptr<int>>>);
    }
    

  • Mod

    list werden solche naiven, akademischen Herleitungen nie gerecht. Tatsache ist, dass die Maschinen auf denen wir arbeiten, auf räumliche und zeitliche Lokalität hin optimiert sind. Listen platzieren ihre Knoten letztendlich zufällig im Speicher, und haben damit einen entscheidenden Defizit gegenüber einer zusammenhängenden, sequentiellen Datenstruktur wie vector.

    Daher darf man bei jedem Post, der list durch Komplexität als optimale Datenstruktur ableiten möchte, getrost skeptisch sein und auf eine Messung warten.



  • J, der vector ist tatsächlich schneller, ich verstehe allerdings die Funktionsweise nicht ganz. Kann auch sein dass ich ein bisschen aufm Schlauch steh:

    #include "collection/test_t.hpp"
    
    
    using type = test_t<int>;
    
    
    template<typename C>
    void f(){
        C container;
    
        for(int n=0; n!=3; ++n)
            container.emplace_back();
    }
    
    
    #include <vector>
    #include <list>
    
    int main(){
        f<std::vector<type>>();
        std::cout << "\n\n";
        f<std::list<type>>();
    }
    

    Der Auswurf:

    test_t<int>::test_t() [T = int]
    test_t<int>::test_t() [T = int]
    test_t<int>::~test_t() [T = int]
    test_t<int>::test_t() [T = int]
    test_t<int>::~test_t() [T = int]
    test_t<int>::~test_t() [T = int]
    test_t<int>::~test_t() [T = int]
    test_t<int>::~test_t() [T = int]
    test_t<int>::~test_t() [T = int]
    
    
    test_t<int>::test_t() [T = int]
    test_t<int>::test_t() [T = int]
    test_t<int>::test_t() [T = int]
    test_t<int>::~test_t() [T = int]
    test_t<int>::~test_t() [T = int]
    test_t<int>::~test_t() [T = int]
    

    Die Ctor/Dtor-Calls von list<> versteh ich ja. Aber wie kann es sein dass der vector<> hier so viele Dtor-Calls macht? Er macht ein Dtor Call wenn schon ein Element drin ist und ich ein neues reinpusche klar. Aber müsste dieses alte Element dann nicht auch irgendwie wieder neu konstruiert werden? Also fehlt da für mich noch sowas wie ein Ctor in der Ausgabe.


  • Mod

    Der vector wird zweimal realloziert, beim jeweils zweiten und dritten emplace_back. Das führt zu 1+2=3 Destruktoraufrufen plus den 3 ohnehin anfallenden, macht 6.

    Edit: Ah, du wunderst dich über die fehlenden Konstruktoraufrufe: Deine Klasse vergisst Move/Copy Konstruktoren anzuzeigen.



  • Ja ok. Aber wenn ein Element middm Dtor gekillt wird muss dieser doch auch irgendwie wieder neu konstruiert werden oder nicht?

    @Columbo sagte in Insert/emplace in verschachtelte map<char, vector<unique_ptr>>:

    Edit: Ah, du wunderst dich über die fehlenden Konstruktoraufrufe: Deine Klasse vergisst Move/Copy Konstruktoren anzuzeigen.

    Ja genau 🙂 Nein.

    
        template<typename X>
        test_t(test_t<X>&& rhs) : value{std::move(rhs.value)}{
            std::cerr << __PRETTY_FUNCTION__ << '\n';
        }
    
        template<typename X>
        test_t& operator= (test_t<X>&& rhs){
            std::cerr << __PRETTY_FUNCTION__ << '\n';
            value = std::move(rhs.value);
            return *this;
        }
    

    Und hier:

        template<typename X>
        test_t(const test_t<X>& rhs) : value{rhs.value}{
            std::cerr << __PRETTY_FUNCTION__ << '\n';
        }
    
        template<typename X>
        test_t& operator= (const test_t<X>& rhs){
            std::cerr << __PRETTY_FUNCTION__ << '\n';
            value = rhs.value;
            return *this;
        }
    

    Vielleicht eine Art Optimierung oder so?


  • Mod

    Dein Code muss aber einen Konstruktor übersehen, weil die Ausgabe sonst suggeriert, dass mehr Objekte zerstört werden als erzeugt.

    #include <iostream>
    #include <list>
    #include <vector>
    
    struct A {
        ~A() {std::cout << "~A()\n";}
        A(A&&) {std::cout << "A(&&)\n";}
        A() {std::cout << "A()\n";}
    };
    
    int main(){
        std::vector<A> container;
    
        for(int n=0; n!=3; ++n) {
            std::cout << n << '\n';
            container.emplace_back();
        }
    }
    

    Hier sehe ich

    0
    A()
    1
    A()
    A(&&)
    ~A()
    2
    A()
    A(&&)
    A(&&)
    ~A()
    ~A()
    ~A()
    ~A()
    ~A()
    


  • Bei deinem Code kommt bei mir das gleiche raus. Aber nein, eigentlich denk ich nicht dass ich was vergessen habe.

    template<typename T>
    struct test_t{
        T value;
    
        test_t(){
            std::cerr << __PRETTY_FUNCTION__ << '\n';
        }
    
        template<typename X>
        test_t(X&& val) : value{std::forward<X>(val)}{
            std::cerr << __PRETTY_FUNCTION__ << '\n';
        }
    
        template<typename X>
        test_t(const test_t<X>& rhs) : value{rhs.value}{
            std::cerr << __PRETTY_FUNCTION__ << '\n';
        }
    
        template<typename X>
        test_t& operator= (const test_t<X>& rhs){
            std::cerr << __PRETTY_FUNCTION__ << '\n';
            value = rhs.value;
            return *this;
        }
    
        template<typename X>
        test_t(test_t<X>&& rhs) : value{std::move(rhs.value)}{
            std::cerr << __PRETTY_FUNCTION__ << '\n';
        }
    
        template<typename X>
        test_t& operator= (test_t<X>&& rhs){
            std::cerr << __PRETTY_FUNCTION__ << '\n';
            value = std::move(rhs.value);
            return *this;
        }
    
        ~test_t(){
            std::cerr << __PRETTY_FUNCTION__ << '\n';
        }
    };
    

    Ähm ich habs versucht zu debuggen und bin auf komisches Verhalten gestoßen. Ich setze den Breakpoint in Zeile 27 und 28 starte den Debugger und dann bleibt der Debugger im Destruktor hängen. Ja, als hätte ich den Breakpoint dahin gesetzt. Hab ich aber nicht. Hab das jetzt 3 Mal versucht. Hab auch "Rebuild entire project" gemacht. Ich setze den Breakpoint im Move Ctor und stehen bleibt der Debugger im Dtor. Kein Witz.

    Gleiches Verhalten für clang++ und g++ mit gdb und QtCreator als Interface.

    Das macht er nur bei templates.


  • Mod

    Poste mal ein vollständiges Beispiel.



  • Hier.
    Hier das Gegenstück.

    Nur dtor calls.

    EDIT: Wie sieht das eigentlich mit den Adressen bei move aus? Bei nem Pointer oder ner Referenz zielt man immer auf die gleiche Adresse. Pass by value erzeugt immer eine neue Adresse. Vielleicht liegt es ja an move? Aber dann versteh ich nicht warum das bloß bei ner templatisierten Klasse ist.



  • Wenn der move-Konstructor nicht noexcept ist, verwendet std::vector::emplace_back den Kopierkonstruktor, wenn sich die Gösse ändert.


  • Mod

    @spiri Du hast den Kopier- bzw. Move-Konstruktor doch gar nicht deklariert. Deine Konstruktoren sind Templates, die beliebige Spezialisierungen annehmen. Aendere mal den Konstruktor zu

    test_t(test_t&& rhs) : value{std::move(rhs.value)}{
         std::cerr << __PRETTY_FUNCTION__ << '\n';
    }
    

    https://coliru.stacked-crooked.com/a/0a17ef0a662e7bbd



  • Bitte die Diskussion nicht zu sehr abschweifen lassen 🙂

    Wie gewünscht Poste ich mal den restlichen Code und eine genaue Erklärung meiner Intension.
    Der Code ist dafür da, um eine Konfiguration aus zu lesen. Sie wird einmalig ausgelesen und dann nur noch drauf gelesen. Ziel ist es, dass das spätere abfragen der Konfiguration so schnell wie möglich geht. Das einmalige einlesen kann durch aus langsamer sein (darum auch regex). Es wird maximal die Konfiguration komplett neu eingelesen. Die Konfiguration kann wie folgt aussehen:

    EDIT: Warum ich std::unordered_map<Block, BlockListNew> ConfigBlockNew; anstelle einer multimap genommen habe, kann ich persönlich gerade nicht sagen. Der Code ist schon älter und ich schreibe den gerade neu. Es gab bestimmt Gründe warum dem so war, die ich leider jetzt nicht mehr kenne ^^

    key value
    key2 value2
    
    # Kommentar
    // Auch ein Kommentar
    
    /*
    Mehrzeiliges Kommentar
    Bla bla
    */
    
    blockKeyABC BlockValue {
        key value
        key2 value, value2
    }
    
    blockKeyABC BlockValue2 {
    
    }
    
    blockKeyDEF Value {
    
    }
    
    key3 value3
    

    Der Grund warum ich "Blöcke" erst in am ende des Block } hinzufüge, liegt darin das im block auch "ignore 1" stehen könnte und der block dann zwar ausgelesen wurde, jedoch nicht hinzugefügt werden soll. std::vector nutze ich, da die Reihenfolge genauso so wie in der Konfiguration angegeben wurde auch erhalten bleiben soll. Innerhalb eines Block soll/darf jeder key nur 1 mal vorkommen. Die BlockKey sind vorgeben, also es gibt eine Liste welche möglich sind, ungültige Blöcke werden einfach ignoriert.

    int CConfig::parseConfigFile(const std::string &path)
    	{
    		std::ifstream fh(path);
    		if (!fh.is_open())
    		{
    			// Kann Datei nicht öffnen
    			return -1;
    		}
    
            KeyValueMap config;
            ConfigBlock blockConfigs;
            ConfigBlockNew blocks;
    		bool inCommand = false;
    
            Block blockType = Block::nothing;
            std::unique_ptr<BlockElementNew> block_ptr;
    
    		std::string line;
    		std::smatch match;
    
    		int i = 0;
    		
    		//
    		while (std::getline(fh, line))
    		{
    			i++;
    
                // Prüfe auf UTF-8 BOM
    			if (i == 1 && line.size() >= 3)
    			{
    				if (line[0] == (char)0xEF && line[1] == (char)0xBB && line[2] == (char)0xBF)
    				{
    					// std::cout << "UTF8 detected!" << std::endl;
    					line.erase(0, 3);
    				}
    			}
    			
                if (block_ptr) {
                    std::cout << "block_ptr is true" << std::endl;
                } else {
                    std::cout << "block_ptr is false" << std::endl;
                }
    
    			// Lösche Zeilenumbruch am ende
    			// Lösche Tab und leerzeichen am Anfang und Ende
    			Misc::trim(line);
    
    			// Wenn Zeile leer ist
    			if (line.size() == 0)
    			{
    				continue;
    			}
    
    			// Überspringe # und //
    			if (line[0] == '#' || (line.size() >= 2 && line.substr(0,2) == "//"))
    			{
    				continue;
    			}
    
    			if (!inCommand && line.size() >= 2 && line.substr(0,2) == "/*")
    			{
    				// Block Kommentar Anfang
    				inCommand = true;
    				continue;
    			}
    			
    			if (inCommand && std::regex_search(line, std::regex("\\*/$")))
    			{
    				// Block Kommentar Ende
    				inCommand = false;
    				continue;
    			}
    
    			if (inCommand)
    			{
    				// Block Kommentar Zeile
    				continue;
    			}
    
    			// Beginne Block
    			if (!block_ptr && std::regex_search(line, match, std::regex("(\\w+?)\\s+(.*?)\\s*\\{$")))
    			{
    				// Suche zu dem Schlüssel (string) den enum-class Wert
    				// Dabei ignoriere Groß- und Kleinschreibung des Schlüssel
    				auto const enumKey = BlockNameMap.find(match[1]);
    				if (enumKey == BlockNameMap.end())
    				{
    					std::cout << "Unbekannter Blockname [" << match[1] << "]" << std::endl;
    					// Schlüssel nicht gefunden, Warnung ausgeben
    					continue;
    				}
                    
                    blockType = enumKey->second;
                    std::cout << "Starte Block [" << match[1] << "]" << std::endl;
    
    				// ConfigBlock::iterator it = blockConfigs.find(enumKey->second);	//  enumKey->second  = CConfig::Block
                    
                    /*
    				// Suche nach Blockgruppe
    				if (it == blockConfigs.end())
    				{
    					// Blockgruppe gibt es in der map noch nicht, erstelle diesen
    					std::cout << "BlockConfig nicht gefunden, neue erstellen" << std::endl;
                        
                        std::pair<ConfigBlock::iterator, bool> result = blockConfigs.insert(ConfigBlock::value_type(enumKey->second, {}));
                        // std::pair<ConfigBlockNew::iterator, bool> result2 = blockConfigsNew.insert(ConfigBlockNew::value_type(enumKey->second, {}));
                        
                        if (result.second == false)
                        {
                            // Hinzufügen fehlgeschlagen
                            // std::cout << "Hinzufügen der BlockConfig fehlgeschlagen" << std::endl;
                            return i;
                        }
                        
                        it = result.first;
                        //it2 = result2.first;
    				}
                    */
                    
                    
    				// match[2] = BlockValue1, BlockValue2
    				// Zerlege match[2] in vector
                    auto identity = Misc::split(match[2].str(), ',');
    
                    // Die einzelnen Einträge trimmen
                    Misc::trim(identity);
    
                    block_ptr = std::make_unique<BlockElementNew>(identity);
    			}
    			else if (block_ptr && line == "}")
    			{
    				// Block Ende
                    std::cout << "Beende Block " << std::endl;
                    
                    
                    // Suche nach dem Block-Typ (enumClass)
                    ConfigBlockNew::iterator it = blocks.find(blockType);
                    
                    // Wenn Typ nicht gefunden wurde, füge ihn hinzu
                    if (it == blocks.end())
                    {
                        // Blockgruppe gibt es in der map noch nicht, erstelle diesen
                        std::cout << "Block-Config nicht gefunden, erstellen." << std::endl;
                        // BlockListNew tmp = BlockListNew (block_ptr);
                        
                        //auto result = blocks.insert(std::make_pair(blockType, BlockListNew{std::move(block_ptr)}));
                        // auto result = blocks.emplace();
                        // ConfigBlockNew blocks
                        //auto result = blocks.emplace(ConfigBlockNew::value_type(blockType, { } ));
                        // BlockListNew liste = { std::move(block_ptr) };
                        // auto result = blocks.emplace(std::make_pair(blockType, BlockListNew::value_type({ std::make_unique<BlockElementNew>(std::move(block_ptr)) }) ));
                        //auto result = blocks.emplace(blockType, BlockListNew::value_type(std::make_unique<BlockElementNew>()));
                        // auto result = blocks.insert(blockType, BlockListNew::value_type(std::move(block_ptr)) );
                        
                        /*
                        if (result.second == false)
                        {
                            // Hinzufügen fehlgeschlagen
                            std::cout << "Hinzufügen der Block-Config fehlgeschlagen" << std::endl;
                            return false;
                        }
                        else {
                            std::cout << "Hinzüfügen der neuen Blockliste erfolgreich" << std::endl;
                        }
                        */
                    
                        // std::move(block_ptr)
                    }
                    else {
                        // Block in die Hash-Map verschieben
                        it->second.push_back(std::move(block_ptr));
                    }
                    
                    // Pointer zurücksetzten
                    block_ptr.reset();
    			}
    			else
    			{
    				// TODO:
    				// Umsetzen von
    				// : key = value
    				
    				if (!std::regex_match(line, match, std::regex("^(\\w+?)\\s+(.*)")))
    				{
    					// Zeilen mit einem Key aber keinem Wert (ignorieren)
    					// std::cout << "Schlüssel ohne Wert: [" << line << "]" << std::endl;
    					continue;
    				}
    
    				// Gerade in Block-Element
    				if (block_ptr)
    				{
    					std::cout << "In Block Element" << std::endl;
    
    					// std::transform(match[1].str().begin(), match[1].str().end(), match[1].str().begin(), ::tolower);
    					
    					// Suche zu dem Schlüssel (string) den enum-class Wert
    					// Dabei ignoriere Groß- und Kleinschreibung des Schlüssel
    					auto const enumKey = KeyNameMap.find(match[1]);
    					if (enumKey == KeyNameMap.end())
    					{
    						// Schlüssel nicht gefunden, Warnung ausgeben
    						std::cout << "Unbekannter Blockschlüssel [" << match[1] << "]" << std::endl;
    						continue;
    					}
    					
    					switch (enumKey->second)
    					{
                                                    // irrelevant
    
    
    						default: {
    							//std::unique_ptr<ValueType> p = std::make_unique<ValueTypeString>(match[2]);
    							//block->condition3.insert(KeyValueMap3::value_type(enumKey->second, std::move(p)));
    							//block->condition.insert(KeyValueMap::value_type(enumKey->second, match[2]));
    						}
    					}
    				}
    				else
    				{
    					// std::cout << "Config Element" << std::endl;
    
    					auto const enumKey = KeyNameMap.find(match[1]);
    					if (enumKey == KeyNameMap.end())
    					{
    						// Schlüssel nicht gefunden, Warnung ausgeben
    						// std::cout << "Unbekannter Schlüssel [" << match[1] << "]" << std::endl;
    						continue;
    					}
    					
    					config.insert(KeyValueMap::value_type(enumKey->second, match[2]));
    					//block[enumKey->second] = match[2].str();
    					// config[match[1].str()] = { match[1], match[2] };
    				}
    			}
    		}
    
    		if (block_ptr)
    		{
    			
    			// Ein Config-Block wurde nicht geschlossen!
    			std::cout << "Ein Config-Block wurde nicht geschlossen!" << std::endl;
    			return -2;
    		}
    
    		if (fh.bad())
    		{
    			// Wenn irgendwas während des Dateilesen schief geht
    			return -1;
    		}
    
    		return 0;
    	}
    

Anmelden zum Antworten