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


  • 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