Home arrow C++ arrow Page 3 - The Standard Template Library

The Standard Template Library

STL stands for Standard Template Library. It has been one of the most important parts of the standard library since 1999. bringing the most crucial improvements to the C++ language. It redefined the way we perceive data structures and the way we are coding right now. If you've just learned the basics of C++, then this is definitely an article that will help you gather more knowledge and progress.

Author Info:
By: Gabor Bernat
Rating: 5 stars5 stars5 stars5 stars5 stars / 7
June 24, 2008
  1. · The Standard Template Library
  2. · History Class
  3. · Looking Inside the Library
  4. · Iterators

print this article

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


: _Mybase()

{ // construct empty vector



void pop_back()

{ // erase element at end

if (!empty())

{ // erase last element

_Destroy(_Mylast - 1, _Mylast);





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.

blog comments powered by Disqus

- Intel Threading Building Blocks
- Threading Building Blocks with C++
- Video Memory Programming in Text Mode
- More Tricks to Gain Speed in Programming Con...
- Easy and Efficient Programming for Contests
- Preparing For Programming Contests
- Programming Contests: Why Bother?
- Polymorphism in C++
- Overview of Virtual Functions
- Inheritance in C++
- Extending the Basic Streams in C++
- Using Stringstreams in C++
- Custom Stream Manipulation in C++
- General Stream Manipulation in C++
- Serialize Your Class into Streams in C++

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 

Developer Shed Affiliates


© 2003-2018 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials