deque :: insert () à l’index?

Il existe une fonction deque::insert(iterator pos, const T&x) prenant la position pos tant que deque::iterator et un seul élément. En utilisant cette méthode, vous pouvez insérer tous les éléments un par un. pos peut être facilement obtenu (si vous avez un index avant lequel vous souhaitez insérer l’élément) avec deque.begin()+index . La méthode insert retourne un iterator pour le nouvel élément inséré, incrémentez simplement cet iterator renvoyé pour obtenir la position suivante:

 deque::iterator it = myDeque.begin()+index; while(n--) { it = myDeque.insert(it, currentElement); it++; currentElement = ... // However you get your next element ... } 

Cependant, cela ne prend pas un temps O(n*k) , car l’insertion d’un seul élément est (iirc) une opération temporelle linéaire iirc.

La deuxième surcharge est deque::insert(iterator pos, InputIterator f, InputIterator l) : souvenez-vous que de simples pointeurs remplissent également les conditions requirejses pour un iterator d’entrée STL. vos éléments, vous pouvez insérer tous les éléments de ce tableau avec

 d.insert(pos, array, array+n); 

Cette opération peut être effectuée en temps linéaire, soit O(n+k) . Je ne sais pas si cela est garanti par la norme, mais je suppose que la plupart des implémentations le feront efficacement.

MODIFIER

J’ai rapidement vérifié avec l’implémentation de Microsoft: ils l’ont fait en push_front une séquence push_back ou push_front , ce qui est plus proche de pos , puis en faisant pivoter les éléments à leur position finale, ce qui garantit la complexité O(n+k) susmentionnée. Bien sûr, cela pourrait aussi être fait “à la main” comme:

 size_type _Off = pos - d.begin(); size_type _Oldsize = d.size(); if (_Off <= d.size() / 2) { // closer to front, push to front then rotate while (hasMoreElements()) push_front(nextElement()); // prepend flipped size_type _Num = d.size() - _Oldsize; std::reverse(d.begin(), d.begin() + _Num); // flip new stuff in place std::rotate(d.begin(), d.begin() + _Num, begin() + _Num + _Off); } else { // closer to back while (hasMoreElements()) push_front(nextElement()); // prepend flipped std::rotate(begin() + _Off, begin() + _Oldsize, end()); } 

(J'ai copié le code de l'implémentation Microsofts de deque::insert , en supprimant le code de débogage et la gestion des exceptions,

Appelez la méthode insert qui prend une séquence d’éléments à insérer, voir la 3ème méthode répertoriée ici:

http://msdn.microsoft.com/en-us/library/zcww84w5(v=vs.71).aspx

Et créez votre propre iterator de style STL pour accéder aux éléments que vous souhaitez insérer. Voir:

Itérateur personnalisé en C ++

Consortingbution:

Deque: lengtl = l,

Nouveaux éléments (m = nombre de nouveaux éléments)

Algo:

créer une nouvelle deque (1)

Copiez tous les éléments du deque original jusqu’à l’endroit où vous souhaitez insérer les nouveaux (p)

Ajouter de nouveaux éléments (m)

Ajouter des articles de old deque (mp)

Peut-être que vous pouvez simplement utiliser le nouveau deque mais au pire:

Copiez le nouveau deque sur l’ancien (après un effacement complet:):

Coût (l + m)

Le coût le plus bas est donc: origine * 2 + nouveautés, ce qui est linéaire.

Le «jeu dégagé» n’est pas compté ici, mais il est également linéaire (au pire).

Ajoutez tous les éléments après le point d’insertion à un vecteur.
Supprimer tous les éléments après le point d’insertion.
Ajouter une nouvelle gamme à deque.
Ajouter le vecteur à deque.

C’est le pire cas O (2n), au lieu de O (n ^ 2).