Cette question d'architecture est assez simple, mais elle me dérange depuis des lustres.Question architecturale C++/STL sur l'utilisation de l'itérateur pour la suppression de la liste O (1) par des systèmes externes
L'intérêt d'utiliser une liste, pour moi quand même, c'est que c'est O (1) insérer/enlever. La seule façon d'avoir une suppression O (1) est d'avoir un itérateur pour erase(). La seule façon d'obtenir un itérateur est de le conserver depuis l'insertion initiale() ou de le trouver par itération.
Alors, que faire passer? un itérateur ou un pointeur?
Il semblerait que s'il est important d'avoir une suppression rapide, comme une sorte de grande liste qui change très fréquemment, vous devriez faire circuler un itérateur, et si vous n'êtes pas inquiet du temps nécessaire pour trouver l'article dans la liste, puis passez le pointeur.
Voici un exemple de dénudation typique:
Dans cet exemple, nous avons un certain type appelé Foo. Foo est susceptible d'être un pointeur de classe de base, mais ce n'est pas ici pour la simplicité.
Ensuite, nous avons FooManger, qui contient une liste de shared_ptr, FooPtr. Le gestionnaire est responsable de la durée de vie de l'objet une fois qu'il lui a été transmis.
Maintenant, que retourner de addFoo()? Si je retourne un FooPtr alors je ne pourrai jamais le retirer de la liste dans O (1), car je devrai le trouver dans la liste. Si je retourne un std :: list :: itérateur, FooPtrListIterator, alors n'importe où je dois enlever le FooPtr je peux, juste en déréférençant l'itérateur.
Dans cet exemple, j'ai un exemple inventé d'un Foo qui peut se tuer dans certaines circonstances, Foo :: killWhenConditionMet(). Imaginez un certain Foo qui a une minuterie qui descend jusqu'à 0, à quel point il doit demander au gestionnaire de se supprimer lui-même. Le problème est que 'ceci' est un Foo nu *, donc la seule façon de se supprimer est d'appeler FooManager :: eraseFoo() avec un pointeur brut. Le gestionnaire doit maintenant rechercher le pointeur d'objet pour obtenir un itérateur afin qu'il puisse être effacé de la liste et détruit.
La seule solution consiste à stocker l'itérateur dans l'objet. i.e Foo a un FooPtrListIterator en tant que variable membre.
struct Foo;
typedef boost::shared_ptr<Foo> FooPtr;
typedef std::list<FooPtr> FooPtrList;
typedef FooPtrList::iterator FooPtrListIterator;
struct FooManager
{
FooPtrList l;
FooPtrListIterator addFoo(Foo *foo) {
return l.insert(l.begin(), FooPtr(foo));
}
void eraseFoo(FooPtrListIterator foo) {
l.erase(foo);
}
void eraseFoo(Foo *foo) {
for (FooPtrListIterator it=l.begin(), ite=l.end(); it!=ite; ++it) {
if ((*it).get()==foo){
eraseFoo(it);
return;
}
}
assert("foo not found!");
}
};
FooManager g_fm;
struct Foo
{
int _v;
Foo(int v):_v(v) {
}
~Foo() {
printf("~Foo %d\n", _v);
}
void print() {
printf("%d\n", _v);
}
void killWhenConditionMet() {
// Do something that will eventually kill this object, like a timer
g_fm.eraseFoo(this);
}
};
void printList(FooPtrList &l)
{
printf("-\n");
for (FooPtrListIterator it=l.begin(), ite=l.end(); it!=ite; ++it) {
(*it)->print();
}
}
void test2()
{
FooPtrListIterator it1=g_fm.addFoo(new Foo(1));
printList(g_fm.l);
FooPtrListIterator it2=g_fm.addFoo(new Foo(2));
printList(g_fm.l);
FooPtrListIterator it3=g_fm.addFoo(new Foo(3));
printList(g_fm.l);
(*it2)->killWhenConditionMet();
printList(g_fm.l);
}
Ainsi, les questions que j'ai sont: 1. Si un objet doit se supprimer, ou avoir un autre système supprimer, en O (1), dois-je stocker un itérateur à l'objet, à l'intérieur de l'objet? Si oui, y a-t-il des problèmes avec les itérateurs qui deviennent invalides à cause d'autres itérations de conteneurs?
Existe-t-il simplement une autre façon de procéder? En guise de question complémentaire, quelqu'un sait-il pourquoi et les opérations du conteneur stl 'push *' ne renvoient pas l'itérateur résultant, ce qui signifie qu'il faut recourir à 'insert *'.
S'il vous plaît, pas de réponses qui disent "ne pas pré-optimize", il me rend fou. ;) Ceci est une question d'architecture.
La condition «lorsque la minuterie descend jusqu'à 0» est une solution élégante: trier la liste par heure restante jusqu'à 0. De cette façon, vous supprimerez toujours le premier/dernier élément. – Dark
@Dark, la file d'attente prioritaire serait un meilleur conteneur. –
@Pavel Shved, les mains vers le bas ce serait. – Dark