STL Vectors and what inside

[dmytro]

Everybody knows how useful STL containers and how easy sometimes to use them. But what for example if you need to make your program a bit quicker. Obvious solution is to make containers quicker. From my experience container's write/read/find in average take about 1/3 of overall time spent by your program. And worse case scenario when you discover you are slow right at the middle of the project when all interfaces in place. The only way sometimes is to re-design existing container with the same interface. And even worse to come if you discover that slow part is a piece from STL. You need to understand what inside - and have you been in there? It's a hell.

This article shows what stl_vector.h has in mind and how it works in principle.

Below is a basic_vector example that will let you spend not more than 20 minutes to understand what STL vector has in mind. Note that a lot of 'safety' pieces dropped just to make it simpler to understand.

#ifndef COMPILER_H
#define COMPILER_H

#include <iostream>
#include <string>

using namespace std;
template<typename T, typename A=allocator<T> >
class basic_vector
  {    
// typedef typename A::pointer iterator;
// typedef typename A::reference reference;
1  typedef typename A::size_type size_type;

    iterator First, Last;
    A alloc;

    iterator begin()
    {
      return (First);
    }

    iterator end()
    {
      return (Last);
    }
    
//  void Destroy(iterator F, iterator L)
//  {
2     for(; F != L; ++F)
      {
        alloc.destroy(F);
      }
    }

    void insert( iterator P, size_type M, const T& X)
    {
//    iterator S = alloc.allocate(Last-First+M);
//
3     uninitialized_fill_n(S+(P-First), M, X);
 
      if (Last-First != 0)
      {
        uninitialized_copy(First, P, S);
        uninitialized_copy(P, Last, S);
  
        Destroy(First, Last);
        alloc.deallocate(First, Last-First);
      }
      Last = S+(Last-First)+M;
      First = S;
    }
    
    public:
    basic_vector() : First(0), Last(0) { }
    ~basic_vector()
    {
      Destroy(First, Last);
      alloc.deallocate(First, Last-First);
      First = 0;
      Last = 0;
    }

//  reference operator[](size_type P)
//  {
4     return (*(begin()+P));
    }

//  const T& operator+=(const T& s)
//  {
5     insert( Last, 1, s);
      return s; 
    }
  };

#endif

///1 To be accurate we want to operate with pointers and references of type that we are going to allocate memory for. In common sense A::pointer is likely to be a T* but it is not always true. Sometimes people may want to run your code on some weird platform and with least expected memory management policy. So, we want to keep even this simple code portable.

I called A::pointer as iterator because the pointer is the simplest and most effective bidirectional iterator. You can walk back and forth with a little overhead - think about char *c; and *(c+i); *(c-i).

///2 We not only want to free the memory but we want to notify the object prior that its going to die and it should free any resources it allocated. We need it because a little bit further we are using an uninitialized_copy which is using construct algorithm to copy objects, in other words its using a cloning mechanism like hypothetically if you want to clone string s1 to s2 into existing memory p you do string *s2 = new(p) string(s1->getValue()). So, at some point in time we are going to have a two identical objects and we want to destroy one of them. See template <class T1, class T2> void construct(T1* p, const T2& value) for more details.

///3 The most complicated piece in our container. The following idea is used.

1.

Allocate memory with sizeof(old_storage)+sizeof(object_to_insert)

|===============================|
2.

Insert object_to_insert into a position we required

|===============T===============|
3.

If we have something in old_storage than copy it

|TTTTTTTTTTTTTTTT===============|

|TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT|
4.

Free old_storage - we don't need it anymore
5.

Update start and end pointers. start obviously points to the start of new_storage the end pointer = start_pointer+sizeof(old_storage)+sizeof(object_to _insert).

We use uninitialized_copy instead of copy because copy uses an assignment *(result + n) = *(first + n) to copy and uninitialized_copy uses new(result) T(first). So in a example below with string if you use copy it will attempt to assign *result = *first and will think that result memory is a string object structure that is true but it will call assign that will try to free obsolete uninitialized result payload pointer and it just may fail with SIGSEGV.

uninitialized_fill_n is very similar to uninitialized_copy - it uses new(result) T(X) to copy the object.

///4 We might want to have access operator. Using [] operator we can assign values to a particular index or read contains.

///5 The STL vector's push_back uses similar concept to add the values. In insert we are specifying that we want to add a T object with size 1. Please note that we are using size in T units not in bytes - that is because when we allocate and copying we are copying T units not bytes.

So, finally after all we can test our vector.

#include "basic_vector.h"

using namespace std;

int main( )
{
  //Example 1
  basic_vector<string> cont;
  cont += "Hello";
  cont += "World";
  cont += "!";
  cont[2] = "!!!";
  
  cout << "0) " << cont[0] << endl;
  cout << "1) " << cont[1] << endl;
  cout << "2) " << cont[2] << endl;
}

When we run this we should see on the screen

#> ./my_vector
0) Hello
1) World
2) !!!

You can take source code for this article at http://www.bablinyuk.org/basic_vector/main.html

Please note that I have dropped from the code some 'safety' features like what will happen if you don't have enough room to allocate a new storage.