STL types

STL can be categorized into the following groupings:

• Container classes:
  • Sequences:
    • vector: (this tutorial) Dynamic array of variables, struct or objects. Insert data at the end.
      (also see the YoLinux.com tutorial on using and STL list and boost ptr_list to manage pointers.)
    • deque: Array which supports insertion/removal of elements at beginning or end of array
    • list: (this tutorial) Linked list of variables, struct or objects. Insert/remove anywhere.
  • Associative Containers:
    • set (duplicate data not allowed in set), multiset (duplication allowed): Collection of ordered data in a balanced binary tree structure. Fast search.
    • map (unique keys), multimap (duplicate keys allowed): Associative key-value pair held in balanced binary tree structure.
  • Container adapters:
    • stack LIFO
    • queue FIFO
    • priority_queue returns element with highest priority.
  • String:
    • string: Character strings and manipulation
    • rope: String storage and manipulation
  • bitset: Contains a more intuitive method of storing and manipulating bits.
• Operations/Utilities:
  • iterator: (examples in this tutorial) STL class to represent position in an STL container. An iterator is declared to be associated with a single container class type.
  • algorithm: Routines to find, count, sort, search, ... elements in container classes
  • auto_ptr: Class to manage memory pointers and avoid memory leaks.

Sample code for C++ STL and expmle showing segmentation faults

#include <iostream> 02 #include <vector> 03 #include <string> 04   05 using namespace std; 06   07 main() 08 { 09    vector<string> SS; 10   11    SS.push_back("The number is 10"); 12    SS.push_back("The number is 20"); 13    SS.push_back("The number is 30"); 14   15    cout << "Loop by index:" << endl; 16   17    int ii; 18    for(ii=0; ii < SS.size(); ii++) 19    { 20       cout << SS[ii] << endl; 21    } 22   23    cout << endl << "Constant Iterator:" << endl; 24   25    vector<string>::const_iterator cii; 26    for(cii=SS.begin(); cii!=SS.end(); cii++) 27    { 28       cout << *cii << endl; 29    } 30   31    cout << endl << "Reverse Iterator:" << endl; 32   33    vector<string>::reverse_iterator rii; 34    for(rii=SS.rbegin(); rii!=SS.rend(); ++rii) 35    { 36       cout << *rii << endl; 37    } 38   39    cout << endl << "Sample Output:" << endl; 40   41    cout << SS.size() << endl; 42    cout << SS[2] << endl; 43   44    swap(SS[0], SS[2]); 45    cout << SS[2] << endl; 46 }

Compile: g++ exampleVector.cpp

Run: ./a.out

Output:

Loop by index:
The number is 10
The number is 20
The number is 30

Constant Iterator:
The number is 10
The number is 20
The number is 30

Reverse Iterator:
The number is 30
The number is 20
The number is 10

Sample Output:
3
The number is 30
The number is 10
        

---

Two / Three / Multi Dimensioned arrays using vector:

A two dimensional array is a vector of vectors. The vector contructor can initialize the length of the array and set the initial value.

Example of a vector of vectors to represent a two dimensional array:

01 #include <iostream> 02 #include <vector> 03   04 using namespace std; 05   06 main() 07 { 08    // Declare size of two dimensional array and initialize. 09    vector< vector<int> > vI2Matrix(3, vector<int>(2,0));    10   11    vI2Matrix[0][0] = 0; 12    vI2Matrix[0][1] = 1; 13    vI2Matrix[1][0] = 10; 14    vI2Matrix[1][1] = 11; 15    vI2Matrix[2][0] = 20; 16    vI2Matrix[2][1] = 21; 17   18    cout << "Loop by index:" << endl; 19   20    int ii, jj; 21    for(ii=0; ii < 3; ii++) 22    { 23       for(jj=0; jj < 2; jj++) 24       { 25          cout << vI2Matrix[ii][jj] << endl; 26       } 27    } 28 }

Compile: g++ exampleVector2.cpp

Run: ./a.out

Loop by index:
0
1
10
11
20
21

---

A three dimensional vector would be declared as:

01 #include <iostream> 02 #include <vector> 03   04 using namespace std; 05   06 main() 07 { 08                                // Vector length of 3 initialized to 0 09    vector<int> vI1Matrix(3,0); 10   11                                // Vector length of 4 initialized to hold another 12                                // vector vI1Matrix which has been initialized to 0 13    vector< vector<int> > vI2Matrix(4, vI1Matrix); 14   15                                // Vector of length 5 containing two dimensional vectors 16    vector< vector< vector<int> > > vI3Matrix(5, vI2Matrix); 17   18    ...

or declare all in one statement:

01 #include <iostream> 02 #include <vector> 03   04 using namespace std; 05   06 main() 07 { 08    vector< vector< vector<int> > > vI3Matrix(2, vector< vector<int> > (3, vector<int>(4,0)) ); 09   10    for(int kk=0; kk<4; kk++) 11    { 12       for(int jj=0; jj<3; jj++) 13       { 14          for(int ii=0; ii<2; ii++) 15          { 16             cout << vI3Matrix[ii][jj][kk] << endl; 17          } 18       } 19    } 20 }

---

Using an iterator:

Example of iterators used with a two dimensional vector.

01 #include <iostream> 02 #include <vector> 03   04 using namespace std; 05   06 main() 07 { 08    vector< vector<int> > vI2Matrix;    // Declare two dimensional array 09    vector<int> A, B; 10    vector< vector<int> >::iterator iter_ii; 11    vector<int>::iterator                 iter_jj; 12   13    A.push_back(10); 14    A.push_back(20); 15    A.push_back(30); 16    B.push_back(100); 17    B.push_back(200); 18    B.push_back(300); 19   20    vI2Matrix.push_back(A); 21    vI2Matrix.push_back(B); 22   23    cout << endl << "Using Iterator:" << endl; 24   25    for(iter_ii=vI2Matrix.begin(); iter_ii!=vI2Matrix.end(); iter_ii++) 26    { 27       for(iter_jj=(*iter_ii).begin(); iter_jj!=(*iter_ii).end(); iter_jj++) 28       { 29          cout << *iter_jj << endl; 30       } 31    } 32 }

Compile: g++ exampleVector2.cpp

Run: ./a.out

Using Iterator:
10
20
30
100
200
300
         

[Potential Pitfall]: Note that "end()" points to a position after the last element and thus can NOT be used to point to the last element.

iter_jj = SS.end();
cout << *iter_jj << endl;

This will result in a "Segmentation fault" error.