std::list Element verschieben?

FrEEzE2046

Hallo,

ich möchte ein spezielles Element einer std::list nach vorne bringen. Da ich jedoch einen Pointer auf dieses Element habe, möchte ich nicht push_front/erase verwenden, da dies ein neues Element anlegen würde und die Referenzierung somit ungültig werden würde.
Die Verwendung der Methode splice ist zwar funktionabel, aber nicht unbedingt performant, da der Zweck ja eigentlich das einfügen von (mehreren) Elementen in einer andere Liste ist.

Ich hab für beides mal ein Beispiel gemacht, damit ihr wisst was ich meine.

#include <list>
using std::list;

int main()
{
	int *p0 = nullptr;
	list<int> l(10);
	auto iter0 = l.begin();

	for( int i = 0; i < l.size(); ++i, ++iter0 ) {
		*iter0 = i;
	}

	iter0 = l.begin();
	++iter0;	// -> 1
	++iter0;	// -> 2
	++iter0;	// -> 3

	p0 = &*iter0;	// p0 -> 3

	l.push_front(*iter0);
	l.erase(iter0);
	iter0 = l.begin();	// -> 3

	/*
	list == { 3, 0, 1, 2, 4, 5, 6, 7, 8, 9 };
	p0 -> ???
	*/

	return 0;
}

int main()
{
	int *p0 = nullptr;
	list<int> l(10);
	auto iter0 = l.begin();

	for( int i = 0; i < l.size(); ++i, ++iter0 ) {
		*iter0 = i;
	}

	iter0 = l.begin();
	++iter0;	// -> 1
	++iter0;	// -> 2
	++iter0;	// -> 3

	p0 = &*iter0;	// p0 -> 3

	auto iter1 = iter0;
	l.splice(l.begin(), l, iter0, ++iter1);
	iter0 = l.begin();	// -> 3

	/*
	list == { 3, 0, 1, 2, 4, 5, 6, 7, 8, 9 };
	p0 -> 3
	*/

	return 0;
}

Welche Alternative hätte ich dazu? Ich möchte zwingend die std::list verwenden, da alle anderen STL-Container ggf. mehrere Elemente auf einmal allokieren wollen und dies mein Custom-Allocator (wie gewünscht) nicht unterstützt.

ipsec

FrEEzE2046 schrieb:

Die Verwendung der Methode splice ist zwar funktionabel, aber nicht unbedingt performant, da der Zweck ja eigentlich das einfügen von (mehreren) Elementen in einer andere Liste ist.

http://cplusplus.com/reference/stl/list/splice/ sagt, dass die Variante mit mehreren Elementen O(n) hat, die mit einem Element O(1).
Wie viel performanter willst du es denn noch?

Edit: ach ja, das O(n) bei mehreren Elementen gilt auch nur, wenn in eine andere Liste eingefügt wird, beim Verschieben innerhalb einer Liste ist es auch O(1).

FrEEzE2046

[quote="ipsec"]

FrEEzE2046 schrieb:

die mit einem Element O(1).

Das ist viel zu langsam ...

Das wollte ich wissen. Danke dir.

FrEEzE2046

Ich habe mich von Microsofts Deklaration irritieren lassen:

void splice(
   iterator _Where,
   list<Allocator>& _Right,
   iterator _First
);

Beschreibung dazu:

[b]_First[/b]
The first element in the range to be inserted from the argument list.

Es sah für mich so aus, als würden von _First an, alle Elemente kopiert.