Comment accéder à un certain élément dans std::list<string> ?

Question

   list<string>&  whichList = theLists[ myhash( x, theLists.size( ) ) ];

Je me demandais comment accéder à une certaine position, disons "i", et voir si elle était vide à cette position.

Je le faisais comme ça :

if(whichList[i] == 0)

mais cela ne semble pas fonctionner.

Je réalise que c'est une erreur. Avez-vous des suggestions ?

Answer 1

Vous pourriez essayer quelque chose comme :

list<string> iterator it = whichList.begin();
std::advance(it, i);
if(*it == "") { /* ... */ }

Mais je pense que vous devez définir clairement ce que vous entendez par "vide" ici - vous ne pouvez pas comparer des chaînes à 0.

Le point essentiel est que list ne supporte pas l'accès aléatoire - à cause de son implémentation (une liste doublement liée), supporter l'accès aléatoire serait une erreur de programmation. O(n) c'est-à-dire linéaire dans la longueur de la liste dans le pire des cas. C'est inefficace, et c'est pourquoi l'interface ne le supporte pas.

Comme d'autres l'ont souligné, si vous voulez un accès aléatoire, il est préférable d'utiliser quelque chose comme un fichier de type vector o deque . En règle générale, vous utiliserez un vector si vous n'avez besoin d'une insertion/désinsertion rapide qu'à la fin du conteneur, une deque si vous avez également besoin d'une insertion/extraction rapide à l'avant du conteneur, et d'une list seulement si vous avez besoin d'une insertion/extraction rapide au milieu du conteneur. Afin de supporter ce dernier type d'opération, list finit par sacrifier l'accès aléatoire aux éléments.

Voir ici pour la définition de advance d'ailleurs :

http://www.sgi.com/tech/stl/advance.html

EDIT : Comme Alf l'a souligné, il est possible, dans une certaine mesure, d'obtenir une insertion/suppression rapide au milieu d'un vecteur en utilisant la technique du gap buffer (voir http://en.wikipedia.org/wiki/Gap_buffer ), bien qu'une opération individuelle puisse être coûteuse si vous comblez le vide (l'idée est d'amortir le coût sur de nombreuses opérations, ce qui rend une séquence d'opérations comparativement bon marché).

Answer 2

En C++, std::list ne supporte pas la recherche par accès aléatoire via operator [] . Si vous continuez à utiliser une liste, vous devriez examiner les éléments suivants std::advance fonction.

list<string>::iterator itr = whichList.begin();
std::advance(itr, i);
if (itr->empty())
{
 /* ... assuming that you're testing for an empty string */
}

Si possible, vous pouvez envisager d'autres conteneurs standard, tels que std::vector o std::deque qui fournissent tous deux un accès aléatoire à la recherche par l'intermédiaire de operator [] .

Answer 3

La manière standard de trouver le premier élément de liste dont la valeur est la chaîne vide est d'utiliser std::find :

std::list<std::string>::iterator it = std::find(whichList.begin(), whichlist.end(), "");

Sa position peut être calculée (de manière coûteuse) comme suit std::distance(whichList.begin(), it) mais il est peu probable que vous ayez besoin de l'indice numérique réel, en supposant que vous ayez pris la décision consciente de ne pas utiliser l'indice numérique. std::list était le bon type de conteneur pour votre application.

Answer 4

Je pense que vous devriez utiliser un vecteur pour ce problème.