random_shuffle auf std::list<>

[XHansWurstX]

Hallo, meine C++ Referenz sagt aus: ...Diese Algorithmen sind Containerunabhängig, d.h. der Zugriff...erfolgt über Iteratoren...

Mit einem Vektor oder einem Array klappt es wunderbar

Nur eine std::list bekomme ich mit random_shuffle nicht gemischt.

no match for 'operator+' in '__first + 1' und verweist auf die stl_algo.h

[Tachyon]

Listen sind eine Ausnahme, weil sie sich aufgrund ihrer Struktur über einen anderen Algorithmus besser sortieren lassen als mit der std::sort Implementierung. Wenn Du Dir mal std::list genauer ansiehst, wirst Du feststellen, dass es dort eine Memberfunktion sort gibt.

Edit: Ach mist. Du willst ja random_shuffle haben. Das geht leider nicht mit Listen, weil sie keine Itaratoren für wahlfreien Zugriff haben. Es gibt verschiedene Klassen von Iteratoren, und random_shuffle braucht einen RandomAccessIterator.

[XHansWurstX]

Tachyon schrieb:

Wenn Du Dir mal std::list genauer ansiehst, wirst Du feststellen, dass es dort eine Memberfunktion sort gibt.

Ähem, ich wollte das Gegenteil Eine extrem unsortierte Liste

Ok, wir haben uns überschnitten, k, trotzdem Danke. Mich verwirrte der Begriff containerunabhängig.

[drakon]

random_shuffle braucht einen RandomAccessIterator, was std::list nun mal nicht bietet..

[Tachyon]

drakon schrieb:

random_shuffle braucht einen RandomAccessIterator, was std::list nun mal nicht bietet..

Bin ich eigentlich unsichtbar, oder wieso werde ich immer widerholt?

[Fellhuhn]

Mach doch irgend sowas (ungetestet):

template<class T>
void list_random_shuffle(list<T> &list){
  vector<T> tmp(list.begin(), list.end());
  random_shuffle(tmp.begin(), tmp.end());
  list.assign(tmp.begin(), tmp.end());
}

Nicht unbedingt performant aber simpel.

// EDIT: doch lieber assign

[drakon]

Tachyon schrieb:

drakon schrieb:

random_shuffle braucht einen RandomAccessIterator, was std::list nun mal nicht bietet..

Bin ich eigentlich unsichtbar, oder wieso werde ich immer widerholt?

Naja. Editieren ist nich.

(Bei mir kommt es halt manchmal vor, dass ich auf antworten klicke und während es lädt mach ich bei meinem eigenen Programm weiter und dann switch ich zurück und schreibe..)

[XHansWurstX]

Fellhuhn schrieb:

Mach doch irgend sowas (ungetestet):
...
Nicht unbedingt performant aber simpel.

Jo, das könnte klappen. Danke...

[Dravere]

XHansWurstX schrieb:

Mich verwirrte der Begriff containerunabhängig.

Containerunabhängig heisst, dass die Algorithmen nicht von den Container abhängen (logisch, ja?). Die Algorithmen hängen allerdings von den Iteratoren ab und das ist der entscheidende Punkt. std::list liefert, wie schon bereits erwähnt, nicht die richtigen Iteratoren.

Jetzt wirst du wohl sagen: "Ja aber, dann sind die Algorithmen doch Containerabhängig, einfach indirekt über ihre Iteratoren!"
Das stimmt allerdings nicht ganz. Du kannst die Iteratoren von std::list in eigene Iteratoren kapseln, welche die Voraussetzungen für RandomAccessIterators erfüllen. Die werden einfach wahrscheinlich ziemlich ineffizient sein, aber dann könntest du auch random_schuffle auf eine std::list anwenden.
Viel entscheidender aber noch ist, dass du beliebe Container selber bauen kannst. Sobald deine Container Random-Access-Iteratoren zur Verfügung stellen, kannst du sie mit random_shuffle verwenden. Deshalb eben Containerunabhängig.

Grüssli

[Don06]

Was man auch machen kann, um z.B. das unnötige Kopieren zu verhindern ist einen Container-Wrapper zu schreiben, der auch auf sequentielle Container Random Access ermöglicht. Das kann man über einen Vector von Iteratoren lösen. Das ganze könnte dann in etwa so aussehen:

std::list<int> int_list;
//...
RandomAccess< std::list<int> > random_access(int_list);
std::random_shuffle(random_access.begin(), random_access.end());

std::copy(int_list.begin(), int_list.end(), 
	std::ostream_iterator<int>(std::cout, " "));

Dafür muss RandomAccess allerdings mit etwas Aufwand zu einem gültigen Container (z.B. mit eigenen Iteratoren) gemacht werden. Der Vorteil ist, dass man das einmal schreibt und dann für alle sequentiellen Container verwenden kann.

Was du noch beachten solltest: Unter Umständen ist es angebrachter direkt einen std::vector zu verwenden. Jetzt sagst du bestimmt: Aber halt, ich füge doch öfter mal Elemente in der Mitte ein und lösche auch mal einige. Trotzdem kann es sein (besonders bei relativ wenig Elementen), dass ein std::vector immer noch performanter ist als eine std::list. Ich habe schon Tests gesehen, die zeigten, dass sich std::list auch bei häufigerem einfügen erst ab 50.000 Elementen "gelohnt" hat. Muss man aber für seinen Code am besten selber testen (ist ja nicht so schwierig, da std::Container ja zueinander kompatibel sind).

Gruß
Don06