The Standard Template Library - Looking Inside the Library
(Page 3 of 4 )
For the sole purpose of better understanding the presentation of the containers, I feel like we should first look at some source code. Therefore, I have chosen the vector because it is one of the most used containers and most efficient/best fitting data structures for daily programming. Check out the code snippet attached below (I have removed some lines and added “…” in their place because they were just too confusing for a beginner):
template<class _Ty,
class _Ax>
class vector
: public _Vector_val<_Ty, _Ax>
{ // varying size array of values
…
vector()
: _Mybase()
{ // construct empty vector
_Buy(0);
}
…
void pop_back()
{ // erase element at end
if (!empty())
{ // erase last element
_Destroy(_Mylast - 1, _Mylast);
--_Mylast;
}
}
…
protected:
void _Assign_n(size_type _Count, const _Ty& _Val)
{ // assign _Count * _Val
_Ty _Tmp = _Val; // in case _Val is in sequence
erase(begin(), end());
insert(begin(), _Count, _Tmp);
}
…
pointer _Myfirst; // pointer to beginning of array
pointer _Mylast; // pointer to current end of sequence
pointer _Myend; // pointer to end of array
};
That should be enough to review the main ideas. No wonder it is all based on templates -- a template that gets to parameters. The first template is for the type of data that will be held in the container, while the second is the allocation type to use for allocating members. This has the following options:
1. alloc:
This is the default allocator. It is thread-safe and usually has the best performance characteristics.
2. pthread_alloc:
This has different memory pools for each existing thread. Although this is typically faster than the default, you shouldn’t forget the memory fragmentation.
3. single_client_alloc:
Even though this is fast, it is unsafe for single threaded programs.
4. malloc_alloc:
This should sound familiar because it uses the existing library function for C, which is malloc.
Vector in itself is a class that contains an array of _Ty elements. It is derived from _Vector_val, which is itself from _Container_base -- the base of all containers. _Vector_val just holds the allocator value. The main implementation of the vector is written in the vector class.
The default constructor is quite easy to comprehend because it just constructs an empty vector, or in other words, “buys” 0 members for it. There are three pointer type values: one pointing to the start of the data structure in the memory, one at the end of the currently allocated member sequence, and one pointing to the end of the current sequence.
This is because, for example, you may have memory allocated, let’s say, for 10 members, but you aren’t required to fill all of them with data. You may only use four items in the memory. You can easily conclude from here that whenever _Myend reaches _Mylast and you want to add another member, the class has to reallocate extra space. Space allocation in STL is done via the principle of double or nothing. It starts from a basic value (around 15, but depends on the implementation) and each time it needs more, it just doubles the currently allocated size.
However, when you are adding many members, it can kill your process because the allocation will be called many times. For this reason, it is a good idea to pre-allocate the final memory size right when you know the number of members to be added.
Next: Iterators >>
More C++ Articles
More By Gabor Bernat
/ 4 
