STL: list, vector oder was sonst nehmen?

[Nexus]

out schrieb:

Dann suchst du wohl das? [...]

Oder gleich std::list::remove() .

[SeppJ]

out schrieb:

Smpff schrieb:

- durch die Liste durchgehen können

D.h. du brauchst kein random access, du willst immer nur von vorne nach hinten durchgehen? Dann nimmst du std::list .

Das würde ich so absolut nicht sagen. Die list hat zwar schnellstes Entfernen von Elementen, aber dafür ist der Rest einfach furchtbar lahm. Sofern das Entfernen nicht sehr oft in sehr großen Listen vorkommt, wird daher ein Programm mit einem Container der alles andere schneller macht (z.B. vector) insgesamt schneller sein.

[Eisflamme]

Eigentlich sollte man immer vector nehmen, außer es gibt triftige Gründe dagegen. Und selbst dann, muss man zusätzlich zu den std-Containern auch noch die boost-Container mitbedenken.

out:
Dieser Entscheidungsgraph führt leider nicht zu den besten Entscheidungen.

[TyRoXx]

Smpff schrieb:

Wie schon geschrieben gibt es nur diese Anforderungen:

- Elemente hinten anhängen
- beliebige Elemente entfernen
- durch die Liste durchgehen können
- Tempo
- Effizienz
- Tempo
- Effizienz

vector::pop_back entfernt auch ein "beliebiges" Element. Du musst dich schon präziser ausdrücken, wenn du sinnvolle Antworten möchtest. Soll ein Element anhand seines Wertes entfernt werden, seiner Position oder seiner Identität?
Was für Elemente sind das überhaupt? Muss die Reihenfolge der Elemente gleich bleiben?

[Smpff]

TyRoXx schrieb:

vector::pop_back entfernt auch ein "beliebiges" Element.

Falsch, das entfernt nicht ein beliebiges Element sondern exakt das letzte.

TyRoXx schrieb:

Du musst dich schon präziser ausdrücken, wenn du sinnvolle Antworten möchtest. Soll ein Element anhand seines Wertes entfernt werden, seiner Position oder seiner Identität?
Was für Elemente sind das überhaupt? Muss die Reihenfolge der Elemente gleich bleiben?

Die Reihenfolge muss nicht gleich bleiben. Ob ich ein Element entfernen möchte, entscheide ich, während ich durch die Liste durchgehe.

[Ethon]

std::vector ist ideal für dich. Wenn die Reihenfolge egal ist, besteht eben immer die Möglichkeit das aktuelle Element mit dem letzten zu swappen und recht effizient entfernen zu können. In allen anderen Bereichen ist der vector den anderen Containern sowieso total überlegen.

[TyRoXx]

Ethon schrieb:

std::vector ist ideal für dich. Wenn die Reihenfolge egal ist, besteht eben immer die Möglichkeit das aktuelle Element mit dem letzten zu swappen und recht effizient entfernen zu können. In allen anderen Bereichen ist der vector den anderen Containern sowieso total überlegen.

Das gibt es fertig als std::remove_if :

std::vector<T> elements;

//Iteriert über den vector und entfernt effizient die gewünschten Elemente.
//Effizient heißt hier, dass der Aufwand für das Entfernen pro Element konstant ist. Der naive Ansatz ist üblicherweise ein erase(it) pro Element, was lineare Laufzeit hat.
elements.erase(
	std::remove_if(
		elements.begin(),
		elements.end(),
		[](T &element) -> bool
	{
		//Einschränkungen: Der vector darf hier nicht in seiner Größe verändert
		//werden, weil sonst die Iteratoren ungültig würden.
		//Während des Iterierens kann sich die Reihenfolge der Elemente ändern.

		//..

		if (element.soll_geloescht_werden())
		{
			return true;
		}

		//..
		return false;
	}),
	elements.end());

[Eisflamme]

Ist das nicht langsamer? cplusplus.com/reference sagt, das ist so implementiert (äquivalent dazu):

template < class ForwardIterator, class Predicate >
  ForwardIterator remove_if ( ForwardIterator first, ForwardIterator last,
                              Predicate pred )
{
  ForwardIterator result = first;
  for ( ; first != last; ++first)
    if (!pred(*first)) *result++ = *first;
  return result;
}

Hier findet kein swap statt, sondern alle Elemente exklusive der zu löschenden werden ins Resultat kopiert. Ich weiß nicht, inwiefern das vom Compiler optimiert wird und der Algorithmus ist auch sicher besser als ein Neusortierungen vom vector, jedoch erscheint mir Swap immer noch besser, oder?

[TyRoXx]

Eisflamme schrieb:

Ist das nicht langsamer? cplusplus.com/reference sagt, das ist so implementiert (äquivalent dazu):

template < class ForwardIterator, class Predicate >
  ForwardIterator remove_if ( ForwardIterator first, ForwardIterator last,
                              Predicate pred )
{
  ForwardIterator result = first;
  for ( ; first != last; ++first)
    if (!pred(*first)) *result++ = *first;
  return result;
}

Hier findet kein swap statt, sondern alle Elemente exklusive der zu löschenden werden ins Resultat kopiert. Ich weiß nicht, inwiefern das vom Compiler optimiert wird und der Algorithmus ist auch sicher besser als ein Neusortierungen vom vector, jedoch erscheint mir Swap immer noch besser, oder?

Selbstverständlich darf das auch mit swap oder move implementiert sein. Es überrascht mich gerade ein wenig, dass es nicht so vorgeschrieben ist. Ob das hier einen Unterschied macht, weiß ich nicht, denn der Fragesteller will uns ja nicht den Elementtyp verraten.

Man kann auch partition nehmen, das benutzt swap (in der Referenz wird std::swap verwendet, aber in der Praxis wird das wohl mit ADL-Unterstützung implementiert).

#include <vector>
#include <algorithm>
#include <iostream>

int main()
{
	std::vector<int> elements = {1, 2, 3, 4, 5};

	//Iteriert über den vector und entfernt effizient die gewünschten Elemente.
	//Effizient heißt hier, dass der Aufwand für das Entfernen pro Element konstant ist. Der naive Ansatz ist üblicherweise ein erase(it) pro Element, was lineare Laufzeit hat.
	elements.erase(
		std::partition(
			elements.begin(),
			elements.end(),
			[](int &element) -> bool
		{
			//Einschränkungen: Der vector darf hier nicht in seiner Größe verändert
			//werden, weil sonst die Iteratoren ungültig würden.
			//Während des Iterierens kann sich die Reihenfolge der Elemente ändern.

			//..

			if (element % 2)
			{
				//false für Entfernen
				return false;
			}

			//..
			return true;
		}),
		elements.end());

	for (auto i = elements.begin(); i != elements.end(); ++i)
	{
		std::cout << *i << "\n";
	}
}

2
4

[SeppJ]

TyRoXx schrieb:

Selbstverständlich darf das auch mit swap oder move implementiert sein.

Nein, kann es nicht. Denn remove_if hat die Reihenfolge der Elemente beizubehalten.

Hier soll eine spezielle Eigenart eines bestimmten Containers unter der Nebenbedingung, dass die Reihenfolge egal ist ausgenutzt werden. Da kannst du nicht einen ganz allgemeinen Algorithmus drauf loslassen.

[TyRoXx]

SeppJ schrieb:

TyRoXx schrieb:

Selbstverständlich darf das auch mit swap oder move implementiert sein.

Nein, kann es nicht. Denn remove_if hat die Reihenfolge der Elemente beizubehalten.

Kannst du erklären, warum das nicht mit move funktionieren soll?

Immerhin erfordert remove_if , dass die Elemente MoveAssignable sind:

25.3.8 Remove
[...]
template<class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
Predicate pred);
[...]
The type of *first shall satisfy the MoveAssignable requirements

SeppJ schrieb:

Hier soll eine spezielle Eigenart eines bestimmten Containers unter der Nebenbedingung, dass die Reihenfolge egal ist ausgenutzt werden. Da kannst du nicht einen ganz allgemeinen Algorithmus drauf loslassen.

Ja, ich hatte nicht bedacht, dass remove_if stabil ist.
Aber partition ist das nicht.

[SeppJ]

TyRoXx schrieb:

SeppJ schrieb:

TyRoXx schrieb:

Selbstverständlich darf das auch mit swap oder move implementiert sein.

Nein, kann es nicht. Denn remove_if hat die Reihenfolge der Elemente beizubehalten.

Kannst du erklären, warum das nicht mit move funktionieren soll?

Das bezog sich vor allem auf das swap. Denk auch dran, dass ein move hier auch nicht die ideale Lösung ist. Es müssen immer noch alle Elemente um eine Position nach vorne geschoben werden, ob durch klassische Zuweisung oder move ist da nur ein Details.