Vector verändern während iteration



  • Ich habe mir mal eine Klasse gebaut die es erlaubt während des iterierens eines Vectors Elemente zu löschen/hinzuzufügen ohne, dass sich der iterator/size etc ändert und der compiler fehler ausspuckt.
    Gibt es in STL elegantere lösungen wie man sowas hinbekommt?
    Oder muss man jedes mal überlegen, in einer for-schleife, wenn man zb. ein element löscht bei welcher position man weiter macht um zum nächsten element zu gelangen?
    Oder doch eine klasse wie diese?

    Das ist die klasse, ist aber noch nicht vollständig.

    #ifndef LOCKABLEVECTOR_HPP
    #define LOCKABLEVECTOR_HPP
    #include <vector>
    #include <iostream>
    
    template <typename T>
    struct LockableVector
    {
    	void add(const T &value);
    	void remove(int index);
    	void lock();
    	void unlock();
    
    	const std::vector<T>& get_items();
    
    	private:
    	std::vector<T> added_new{};
    	std::vector<T> items{};
    	std::vector<int> items_validity{};
    
    	bool is_modified{false};
    	bool is_finished{true};
    
    	void merge();
    };
    
    template <typename T>
    void LockableVector<T>::add(const T &value)
    {
    	if (is_finished)
    	{
    		items.push_back(value);
    		items_validity.push_back(1);
    	}
    	else
    	{
    		added_new.push_back(value);
    		is_modified = true;
    	}
    }
    
    template <typename T>
    void LockableVector<T>::remove(int index)
    {
    	if (is_finished)
    	{
    		items.erase(items.begin() + index);
    		items_validity.erase(items_validity.begin() + index);
    	}
    	else
    	{
    		items_validity.at(index) = 0;
    		is_modified = true;
    	}
    }
    
    template <typename T>
    void LockableVector<T>::lock()
    {
    	if (!is_finished)
    	{
    		std::cout << "already locked";
    		return;
    	}
    	is_finished = false;
    }
    
    template <typename T>
    void LockableVector<T>::unlock()
    {
    	if (is_finished)
    		return;
    	merge();
    	is_finished = true;
    }
    
    template <typename T>
    const std::vector<T>& LockableVector<T>::get_items() { return items; }
    
    template <typename T>
    void LockableVector<T>::merge()
    {
    	if (is_modified)
    	{
    		const auto size = items.size() - 1;
    		for (auto i = size; i > 0; --i)
    			if (items_validity.at(i) == 0)
    			{
    				items.erase(items.begin() + i);
    				items_validity.erase(items_validity.begin() + i);
    			}
    		for (auto &item : added_new)
    		{
    			items.push_back(item);
    			items_validity.push_back(1);
    		}
    		added_new.clear();
    		is_modified = false;
    	}
    }
    #endif 
    

    added_new wird benutzt beim hinzufügen von elementen
    items sind die elemente
    items_validity wird beim deleten benutzt und besteht aus 0 und 1 (alle positionen mit 0 werden dann nach der iteration gelöscht)



  • Ich halte das für keine gute Idee. Das kostet sehr viel Performance. Warum ist es dir so wichtig, dass der Iterator stabil bleibt? Vielleicht solltest du dir eine andere Lösung überlegen, oder eine andere Datenstruktur nehmen?



  • Zu "löschendes" Element mit einem Element vom Ende des Vectors swappen und --new_end dann nach der Schleife erase?



  • @Mechanics sagte in Vector verändern während iteration:

    Warum ist es dir so wichtig, dass der Iterator stabil bleibt?

    Na weil wenn der iterator nicht stabil bleibt während ich den vector verändere dann bekommt man n error weil entweder der iterator größer wird(add) oder kleiner(delete)

    	std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    	for (auto i = v.begin(); i != v.end(); ++i)
    	{
    		std::cout << *i << " ";
    		if (*i == 1)
    			v.erase(i); // Error, can't increment vector iterator past end
    	}
    

    @Mechanics sagte in Vector verändern während iteration:

    oder eine andere Datenstruktur nehmen?

    Alle anderen datenstrukturen verhalten sich genauso oder nicht?

    @Swordfish sagte in Vector verändern während iteration:

    Zu "löschendes" Element mit einem Element vom Ende des Vectors swappen und --new_end dann nach der Schleife erase?

    Ja das würde funktionieren für delete, aber für adden? Müsste man dann quasi das neue element mit dem ersten swappen und ```cpp
    ++new_end



  • Erase gibt einen Iterator zurück, könnte man in dem Fall also ganz einfach lösen, mit 1-2 Zeilen mehr Code, statt eine sehr viel langsamere Datenstruktur aufzubauen.



  • @Bengel sagte in Vector verändern während iteration:

    Ja das würde funktionieren für delete, aber für adden? Müsste man dann quasi das neue element mit dem ersten swappen und ++new_end?

    Mit reserve() vor der schleife dafür sorgen, daß keine reallokation passieren kann und push_back()/emplace_back()?



  • @Bengel sagte in Vector verändern während iteration:

    Gibt es in STL elegantere lösungen wie man sowas hinbekommt?

    Also zum Löschen kannst du erase + std::remove_if nutzen:

    std::vector<int> v = {1, 2, 3, 4};
    // alle geraden Zahlen loeschen
    v.erase(std::remove_if(v.begin(), v.end(), [](int i){ return i%2 == 0; }), v.end());
    

    Edit: oder um bei deinem Beisiel oben zu bleiben, wo du die 1en löscht:

    v.erase(std::remove(v.begin(), v.end(), 1), v.end());
    

Anmelden zum Antworten