Brief Introduction to the STL Containers - Sequence Containers
(Page 2 of 4 )
1) Vector:
Declaration:
Header: vector<T, Alloc>
In code:
vector<int> aVector;
Representation:
The vector is the most commonly used type. It can be reduced on a theoretical level to an array of continuous elements in the memory. It will stay this way even after you add a new element.
If it is placed in the memory continuously, it will extend the current allocation or else it will reserve space in a new memory segment and copy the entire sequence data plus the new element to it. This way, you will always have a continuous data structure and you can refer to the nth member using the location of the first item + n size of the item.
Cons/Pros:
The memory management is dynamic and automatic. This construction allows random access to elements. It has constant time for insertion and deletion at the end (complexity 1), and linear time for the rest (complexity n). All iterators that point to a member are invalidated if the integrity of the block is changed (removing/inserting elements).
Some usage:
aVector.reserve(10); // Reserve memory for 10 items
aVector.resize(10,1); // Resize the vector with 10 1
aVector.push_back(item); // add another item to the end, note that the vector will be extended and a reserve will be called for it
aVector.insert(aVector.begin() + 3, 5); // Using the random //access iterator
aVector.clear(); // Removes all elements from vector
2) String:
Declaration:
Header: basic_string<charT, traits, Alloc>
typedef basic_string<char, char_traits<char>, allocator<char> > string;
In code:
string aString;
Representation:
Despite its complicated look and the long typedef string, it is nothing more than a vector<char> with a few extended functions that are specific to strings, such as search. So the usage of it is very much like the vector, just as it relates to char member types:
const char* text = "Lavigne";
aString.assign("Avril "); // Assign some data
aString += aString; // Double the same content
aString += text; // Add Lavigne
aString.find_last_of("A"); // Returns 6, the pos of last A
Related types:
wstring -> Same as the string, but this is the Unicode version. However, pay attention because here we have an exception. The corresponding header isn't wstring, it's xstring.
rope -> rope has a different design compared to the string and its use is recommended for very long sequences of chars. However, in contrast to the string, which, in matters of complexity, is similar to the vector, a rope has a logarithmic complexity most of the time.
3) Deque:
Declaration:
Header: deque<T, Alloc>
In code:
deque<char> aDeque;
Representation:
This is also a container that is very much like the vector and has most of the same cons and pros. However, we do have a difference. A deque, unlike a vector, also supports constant time of insertion and removal from the beginning of the sequence. Of course, we have to pay a price for this. And the price is that the deque lacks functions like capacity() and reserve() and it can't guarantee the validity of an iterator associated with those member functions. It's up to you to decide whether you can pay this price for the extra insertion efficiency.
aDeque.assign(2, 'A'); // Set two A's
aDeque.pop_front(); // Remove a A
aDeque.push_front('V');// Add at start a V
aDeque.insert(aDeque.begin(), 1, 'R'); //Add at start a R all //this done in constant time
4) List:
Declaration:
Header:
In code:
list<int> aVector;
Representation:
Here we have, as the name suggests, a list. A list for which the allocation in a block isn't a option. Here, each piece of data can be at any memory location. It's linked together using pointers. The basic list is double linked, so you can iterate through it in both ways/directions.
Cons/Pros:
It has constant time insertion/removal to the end, beginning, and middle. However, the directly affected item's iterator is deemed invalid whenever you modify the structure of the list. It is highly recommended when you have a long sequence with many elements. This way, memory reallocation can be avoided.
Related types:
slist -> Here we have a list that is only single linked in one direction. This is done in order to gain some efficiency when you are absolutely sure that you don't need to do any backward traversing through the list.
aList.push_back("Avril"); // Push at the end
aList.insert( aList.end() -1, "Lavigne");
// Insert at the last valid position that is end()-1
aList.empty(); // Will return false
aList.erase(aList.begin()); // Delete the Avril
aList.clear();
aList.empty(); // Will return true
5) Stack:
Declaration:
Header: stack<T, Sequence>
In code:
stack<int> aVector;
Representation:
Stack is an adaptor, which is a container that provides a restricted container that behaves just like a stack in real life. This means it follows the LIFO (Last In, First Out) principle. So you can only see the data at the top of a stack and you can only remove the top item from a stack. Whatever you add will be added to the top.
Stack is, by default, constructed on a deque, however, you can specify what restrictions you want to impose so that it behaves as a stack for the second argument in the template (Sequence). You can select whatever you want if the default doesn't satisfies your needs.
aStack.empty(); // observe if it's empty
aStack.push(2); // add 2 to the stack
aStack.top(); // returns the item at the top
aStack.pop(); // remove the top/last added element
aStack.size(); // returns the size of the stack
6) Queue:
Declaration:
Header: queue<T, Sequence>
In code:
queue <int> aVector;
Representation:
If you read the information I presented earlier about stacks, then you won't be surprised at all. Here, we have the same capabilities for a different principle. Namely, it's about the FIFO (First In, First Out), so what you add first will be, and can only be, removed first. Think of it as though you are in a queue/line waiting to buy a ticket to the cinema. The first people who arrive are the first served, and, hence, the first removed from the line.
std::queue<string,list<string>> aQueue;
string text_1 = "Hilary";
string text_2 = "Duff";
aQueue.push(text_1);
aQueue.push(text_2);
aQueue.front(); // retrieve mutable reference to first pushed //item
aQueue.back(); // Mutable reference to the last pushed item
aQueue.pop(); // Eliminate the first element
Next: Associative Containers >>
More C++ Articles
More By Gabor Bernat
