Visszacsatolás
Az előző cikkben bennmaradt egy pontatlanság, amit gondolom néhányan észre is vettek. A deque implementációja fix méretű lefoglalt pufferekből áll. Egy deque lehetséges állapotát az első ábra szemlélteti.
 
1. ábra
 
2. ábra

A deque-ban középen elhelyezkedő pufferek mindig teljesen fel vannak töltve, így a pointer aritmetika gyors lehet. Ha a végére vagy az elejére kell új elemeket hozzáadni, akkor legrosszabb esetben is csak egy új puffert kell lefoglalni, és a pointer táblában kell másolást végrehajtani. Ha törlési műveletet végzünk a legelején, illetve legvégén, akkor legrosszabb esetben el kell dobni a legutolsó, illetve legelső blokkot. Ha pedig se nem az elejére, se nem a végére vonatkozik a művelet, akkor a meglévő adat egy részét kell másolni a közelebb lévő végéhez, amit a második ábra szemléltet. Látható, hogy a törlés után a piros színű adat "előtt" lévő adatok "feljebb" másolódtak, míg a sárga színű adat esetén a "mögötte" lévő adatokat "lejjebb" másolódtak.
Ebből is látható, hogy optimálisabb lehet a deque használata a legtöbb esetben, a vector osztály helyett. Sőt a memória allokáció / sebesség viszonya is kedvezőbb lehet, mivel a vector vagy duplázza mindig a méretét, vagy fix mérettel növeli. Ha duplázza, akkor elég nagy adatterület mehet veszendőbe, ha már nagy méretű a vector, ha pedig fix mérettel növeli, akkor pedig lassú lehet a folyamatos növelése a vectornak a sok másolás miatt. Az STL-val foglalkozó dokumentációk általában megemlítik, hogy ha nincs igény arra, hogy az iterátor castolható legyen egy mutatóra, akkor mindig a deque-t célszerű használni a vector helyett. Előnyként jelentkezik, hogy a deque iterátora nem válik érvénytelenné akkor, ha csak az elején illetve a végén végzünk műveleteket, és nem töröljük az iterátor által címzett adatot, míg a vector a memória újrafoglalás miatt ezt nem tudja biztosítani.

list
A list template egy kétirányú láncolt listás adatábrázolást valósít meg. Ebből adódnak az előnyei és a hátrányai is. Az elemeket csak szekvenciálisan lehet elérni, azaz ha szükség van az n-edik elemre, akkor ehhez először le kell kérjük az elsőt, majd n-1-szer a következőre kell lépnünk, hogy elérjük az n-ediket. A törlés és a beszúrás költsége konstans, mivel nincs szükség soha a listában szereplő értékek másolására, csak a mutatók átállítására. Egy list elemének járulékos memóriaigénye két mutató - egy a lista előző és egy a következő elemére. Ennek az adatszerkezetnek megvan az az előnye, hogy az iterátorok nem válnak érvénytelenné a beszúrás/törlés hatására, nem úgy, mint a vector illetve a deque esetén. A STL tartalmaz egy sort metódust is a listhez, mivel a generikus sort algoritmus véletlen elérésű iterátort vár, illetve néhány hasznos függvényt rendezett listákra.  A vectoros példaprogram list alapú implementációja:
#include <iostream> #include <list> #include <algorithm> #include <functional> using namespace std; const char HW[] = "Hello world!\n"; main() { // üres list list<char> lc1; // lista a Hello world! -al list<char> lc2(HW+0, HW+sizeof(HW)/sizeof(HW[0])); // kiírás copy(lc2.begin(), lc2.end(),    ostream_iterator<char,char>(cout," "));   cout<<endl; // sorbarendezése lc2.sort(); // kiírás copy(lc2.begin(), lc2.end(),    ostream_iterator<char,char>(cout," ")); // " !Hdellloorw"   cout<<endl; // keresés rendezett list-ben >= -re (nem kisebbre) list<char>::iterator pc; pc = find_if(lc2.begin(), lc2.end(),    bind1st(less<char>(), 'm')); if (pc!=lc2.end())   cout<<"Found:'"<<*pc<<"'"<<endl; else   cout<<"Not found"<<endl; // 5 méret? list list<int> li(5), li1;   list<int>::iterator pi; // feltöltése   pi=li.begin(); for (unsigned int i=0; i<li.size(); i++, pi++)   *pi = 9-i;   pi = li.end(); pi--; // hozzáadás for (int i=5; i<10; i++)   li.push_back(9-i); copy(li.begin(), li.end(),   ostream_iterator<int,char>(cout," ")); // "9876543210"   cout<<endl; // egy részének sorbarendezése // 1. kivágom a sorbarendezendő részt   li1.splice(li1.end(), li, ++pi, li.end()); copy(li.begin(), li.end(),    ostream_iterator<int,char>(cout," ")); // "98765"   cout<<endl; copy(li1.begin(), li1.end(),    ostream_iterator<int,char>(cout," ")); // "43210"   cout<<endl; // 2. sorbarendezem a kivágottat li1.sort(); copy(li1.begin(), li1.end(),    ostream_iterator<int,char>(cout," ")); // "01234"   cout<<endl; // 3. visszaillesztem a végére   li.splice(li.end(), li1); copy(li.begin(), li.end(),    ostream_iterator<int,char>(cout," ")); // "9876501234"   cout<<endl; }

Amint látható ez a megoldás már egy fokkal bonyolultabb, és kevésbé hatékony, mint a vector alapú implementáció. Például az 'm' betűnél nagyobb egyenlő keresése itt lineáris kereséssel működik, szemben a lower_bound-ban implementált bináris kereséssel. Kevés elemszám esetén e kettő sebessége között azonban minimális a különbség. Ezért is fontos, hogy ismerjük a lehetőségeket, és azok közül ki tudjuk választani, a célnak leginkább megfelelőt. Nincs általánosan jó megoldás. Ha például egy olyan struktúrát akarunk tárolni, aminek a copy constructora időigényes művelet, és nem biztosítható, hogy nem kell törölni illetve beszúrni a tároló közepére, akkor célszerűbb lehet kerülni a vector és a deque tárolót. Azonban ha kevés elem van, akkor célszerűbb lehet az egyszerűbb, rövidebben kódolható, ergo hibamentesebb megoldást választani, függetlenül esetleg az implementáló adatszerkezet bonyolultságára.

stack, queue

A stack (LIFO), queue (FIFO) nem külön adatszerkezetek, hanem csak egy viselkedés implementálása más adatszerkezetek segítségével. Alapértelmezett esetben mindkettő a deque-t használja az implementáció során, azonban el lehet ettől térni. A queue esetén nem célszerű használni a vectort, mivel utóbbi használata esetén nem túl hatékony a pop művelet, ami a vector elejéről töröl elemet, és ennek hatására a vector teljes tartalma másolásra kerül.

A stack illetve a queue főbb műveletei:
 
 

Művelet jelentés stack esetén jelentése queue esetén
bool empty() const üres-e üres-e
unsigned size() const hány elem van benne hány elem van benne
T& top() a legutoljára beletett elem referenciáját adja vissza -
push(const T&) egy új elemet helyez el egy új elemet helyez el
void pop() a legutoljára beletett elemet eltávolítja a legrégebben beletett elemet eltávolítja
T& front() - a legrégebben beletett elem referenciáját adja vissza
T& back() - a legutoljára beletett elem referenciáját adja vissza

Az alábbi egyszerű kifejezés kiértékelő szemlélteti a stack egy lehetséges használatát (lásd még Cikkek - Prog.Hu):

#include <iostream> #include <vector> #include <deque> #include <stack> #include <Exception> using namespace std; class ExprEvalError : public exception { private:   vector<char> Error; public:   ExprEvalError(const char *in_Error)   {     while (*in_Error)       Error.push_back(*in_Error++);     Error.push_back('\0');   }   const char * what () const   {     return Error.begin();   } }; class ExprEval { private:   enum TOperations   {     opAdd,     opSub,     opMul,     opDiv,     opNeg,     opValue   };   deque<long int> Values;   deque<TOperations> Ops;   void Expr(const char* &expr, const int Level);   void skipspaces(const char* &expr)   {     while (*expr==' ' || *expr=='\n' ||            *expr=='\r' || *expr=='\t')       expr++;   } public:   ExprEval(const char* expr);   long int operator() () const; }; // a Level jelzi a precedenciát void ExprEval::Expr(const char* &expr, const int Level) {   skipspaces(expr);   switch (Level)   {     case 0: // '+' '-'       Expr(expr, Level+1);       while (*expr=='+' || *expr=='-')       {         TOperations op = (*expr++=='+' ? opAdd : opSub);         Expr(expr, Level+1);         Ops.push_back(op);       }       break;     case 1: // '*' '/'       Expr(expr, Level+1);       while (*expr=='/' || *expr=='*')       {         TOperations op = (*expr++=='/' ? opDiv : opMul);         Expr(expr, Level+1);         Ops.push_back(op);       }       break;     case 2: // '-'       if (*expr=='-')       {         expr++;         Expr(expr, Level+1);         Ops.push_back(opNeg);       }       else         Expr(expr, Level+1);       break;     case 3: // '(' Expr ')', ertek       if (*expr=='(')       {         Expr(++expr, 0);         if (*expr++!=')')           throw ExprEvalError("')' missing in expression");       }       else // parse number only [0..9]+ form       {         if (*expr=='\0')           throw ExprEvalError("Not terminated correctly,"                               " or empty expression");         long int Value = 0;         while (*expr>='0' && *expr<='9') // not too perfect           Value = Value*10 + (*expr++ - '0');         Values.push_back(Value);         Ops.push_back(opValue);       }       break;   }   skipspaces(expr); } ExprEval::ExprEval(const char* expr) {   Expr(expr, 0);   if (*expr!='\0')   {     char * ErrorStr = "Unexpected character ' ' in expression.";     char * c = ErrorStr;     while (*c!='\'') c++; c++; *c = *expr;     throw ExprEvalError(ErrorStr);   } } long int ExprEval::operator()() const {   stack<long int> EvalStack;   long int V2;   deque<long int>::const_iterator vi = Values.begin();   for (deque<TOperations>::const_iterator opi = Ops.begin();         opi != Ops.end(); opi++)   {     switch (*opi)     {       case opAdd:         V2 = EvalStack.top(); EvalStack.pop();         EvalStack.top() += V2;         break;       case opSub:         V2 = EvalStack.top(); EvalStack.pop();         EvalStack.top() -= V2;         break;       case opMul:         V2 = EvalStack.top(); EvalStack.pop();         EvalStack.top() *= V2;         break;       case opDiv:         V2 = EvalStack.top(); EvalStack.pop();         EvalStack.top() /= V2;         break;       case opNeg:         EvalStack.top() *= -1;         break;       case opValue:         EvalStack.push(*vi++);         break;     }   }   return EvalStack.top(); } main() {   try {     cout << ExprEval("1 + 20 / 3 + -(60 - 59) * 7")() << endl;   } catch (ExprEvalError &e) {     cerr << e.what() << endl;   }   cout << endl; }

A következő fejezetben az asszociatív tárolókat fogom bemutatni, és azok segítségével kibővítem a fenti kifejezés kiértékelőt, változók-függvények kezelésével.