STL

Library of standard patterns (STL — Standard Template Library) — it is a set of generalized algorithms, iterators and containers, intended for accessing to the contents of these containers and accompanying support functions.

The library of standard patterns contains set of basic classes for C++ language, such as containers and associative arrays (maps), which can be used for any built-in and users’ data types. All classes included to the library are implemented by means of patterns.

The library consists of four key elements:

1. Containers and adapters
2. Iterators
3. Algorithms
4. Functors

Containers and adapters

Containers can be represented as storage-objects for other objects. They are realized in the view of pattern’s classes, which allows adapting containers for storing objects of any type. Containers contain all required functional for accessing to the stored information. Such functional is represented in the form of methods-containers or by way of iterators.

Containers are divided into four categories:

• Containers for storing sequences. These include arrays and Linked Lists.
• Containers-adapters. These include stack and queue.
• Associative containers. These include sets and maps.
• Pseudocontainers.

Containers for storing sequences

Adapters

Associative containers

Pseudocontainers

By adding any element to the container copying of the original element occurs. Then the copy comes to the container. If copying is not welcome then the container with pointers on the elements is being used.

Iterators

Iterators in the STL are used by way of intermediaries for accessing to the containers’ content. Each container uses concrete iterator, which is recognized taking into account container’s specifics and contains set of required methods to access to the container’s content. Conditionally, iterators in the STL can be divided into following groups:

• Unidirectional iterators. They provide access to reading in one direction.
• Bidirectional iterators. Ensure access to writing in one direction.
• Input iterators. Provide access to reading and writing in one direction.
• Output iterators. Ensure access to reading and writing in both directions.
• Iterators for random access. They are equivalent to the regular pointers: they support pointers’ arithmetic, arrays indexation syntaxes and all forms of comparison.

Iterators contain main functional required for working with containers: search, reading, writing and navigation among containers’ stored objects. But part of operations is performed faster by means of containers’ methods due to some of them specific structure. For example, search among associative containers is conducted faster with methods of associative containers, because these methods are more optimized for the internal structure of such containers.

Algorithms

STL contains numerous algorithms, which provides users with sorting and search functions. Each of these algorithms is optimized for working with different iterators and also with containers, which are represented through appropriate interfaces for working with iterators.

Functional objects (functors)

STL includes classes, which overload call operators of function operator(). Instances of such classes are called functional objects. Such approach to the objects creation allows using object as a function. Generators are great example of such functions; using them it is possible to fill in any sequence with some values.

Templated list with own hands

Before starting talking more precisely about basic containers of STL, let us make simple container. Let us create dynamic array, analogue of container vector, but with minimal functionality.

So what is necessary to employ? Let us create a class, which object will store a sequence of objects of an arbitrary type and which will be represented in the view of an array with possibility of changing its dimension. Also it is required to implement methods for elements’ addition at the end of the array and removal of the last element.

Class prototype will look in the following way:

#ifndef CUSTOM_VECTOR_H
#define CUSTOM_VECTOR_H

#include <iostream>
#include <cstdlib>

class OutOfMemoryException {};
class EmptyContainerException {};

template <class Type>
class CustomVector {    
  private:        
    Type *array;
    size_t capacity; 
    size_t current;  
    static double multiplier; 
  public:
    CustomVector();    
    ~CustomVector(); 
   
    size_t max_size() const;   
    size_t size() const;    
    
    void push_back(const Type& elem);
    Type pop_back();   

    const Type& operator[](size_t index) const;
 };

template <class Type>
double CustomVector<Type>::multiplier = 1.05;
   
  #endif //CUSTOM_VECTOR_H

Attribute multiplier is required in order to avoid over-allocation of the memory per one element. Memory over-allocation is quite resource-intensive operation; therefore its usage during addition of each element is an unaffordable luxury. A far more logical is to increase volume of the memory used for storing sequence for several percents of total amount of enabled memory. In our case, if necessary to increase array’s dimension, the amount of memory allocated for this array will be increased for five percents.

Let us get down to the realization. To begin with let us realize constructor and destructor.

CustomVector() : capacity(100), current(0) {
    array = (Type*)malloc(capacity*sizeof(Type));
    if ( array == NULL ) {
        throw new OutOfMemoryException();
    }
}
~CustomVector() {
    free(array);
}

Now let us implement getters and overload operator[]:

size_t max_size() const {
    return capacity;
}
size_t size() const {
    return size;
}
const Type& operator[](size_t index) const {
    return array[index];
}

Before realization of elements’ addition to the end of the list, it is necessary to recall, that memory is being allocated dynamically. It implies, that we may not acquire required amount of memory in one piece. In its turn, it means, we need to take care of safety of already existing attributes and ensure their correct changing. Let us proceed.

void push_back(const Type& elem) {
    size_t newCurrent = current + 1;

    if ( newCurrent == capacity ) {
        size_t newCapacity = capacity * multiplier;
        Type* newArray = (Type*)realloc(array, newCapacity*sizeof(Type));

        if ( array == NULL ) {
            throw new OutOfMemoryException();
        }
        capacity = newCapacity;
        array = newArray;
    }    
    array[current] = elem;
    current = newCurrent;
    }

Business for small is to implement method for deleting certain elements. It remains to find out whether it is necessary to exempt the memory after each element being removed? Apparently, there is no need. Everything is needed to be done is to reduce attribute’s value, which is responsible for pointing at the last significant element of the array. Wherein, the memory is not going to be exempted in order to avoid repeated allocation in case of element’s addition. But in case if any necessity to exempt some portion of the memory appears it will be required to write another separate method. Let us make method for deleting an element.

Type pop_back() {
    if ( current == 0 ) {
        throw new EmptyContainerException();
    }
    current -= 1;
   return array[current];
}

Why does method pop_back() have type Type and return an element? It is made in order to let us remember the value of deleted element and if necessary to use it or get back to the array. Basically, our container is finished. Let us check its correctness.

#include <iostream>
#include "CustomVector.cpp"

int main() {
    CustomVector<std::string>* lst = newCustomVector<std::string>();
    lst->push_back("alpha");
    lst->push_back("bravo");
    lst->push_back("charlie");
    lst->push_back("delta");

    for ( int i = 0; i < lst->size(); i++ ) {
        std::cout << (*lst)[i] << std::endl;
    }

    std::cout << "--------" << std::endl;

    lst->pop_back();
    lst->pop_back();

    for ( int i = 0; i < lst->size(); i++ ) {
        std::cout << (*lst)[i] << std::endl;
    }

    delete lst;

    return 0;}

As the result we receive next:

alpha
bravo
charlie
delta
--------
alpha
bravo

Our simple template container works properly. As shown by practice such container is uncomplicated in realization and requires little time consumption, basic understanding of dynamic memory allocation and object-oriented approach. Now, after acquaintance with creation of patterned container it is high time to start working with standard library of patterns.

Templated list: vector

Container is represented in view of dynamical array, destined for storing elements of an arbitrary type. Array’s dimension is being changed automatically during addition or removal of the elements.

As any array, vector, places stored elements in the memory in a sequence one after another. Access to the elements occurs by means of usage of an indent from the array’s beginning pointer. Vector uses memory, which is being allocated dynamically.

More in detail of container functionality vector

Using this container is quite simple. Let us remember dynamic array we have created and use it for the next example, but instead of CustomVector we will take std::vector and create an instance of the container by means of its constructor.

#include <iostream>
#include <vector>

int main() {
    std::vector<std::string>* lst = new std::vector<std::string>();

    lst->push_back("alpha");
    lst->push_back("bravo");
    lst->push_back("charlie");
    lst->push_back("delta");

    for ( int i = 0; i < lst->size(); i++ ) {
        std::cout << (*lst)[i] << std::endl;
    }

    std::cout << "--------" << std::endl;

    lst->pop_back();
    lst->pop_back();

    for ( int i = 0; i < lst->size(); i++ ) {
        std::cout << (*lst)[i] << std::endl;
    }
    delete lst;
    return 0;
}

The result, when applying vector, will be identical to what we have received before:

alpha
bravo
charlie
delta
--------
alpha
bravo

As it comes out from practice the usage of container vector from the library of standard patterns is extremely complex task.

Linked List with own hands

Now let us have the next step. Especially, since we are already familiar to container vector, and could even write our own version of it. The next, immensely difficult task, will be to come up with linked list.

What is linked list? Essentially, linked list can be considered as a container, though it will be more correct to consider linked list as an objects’ sequence linked to each other.

For realization of this task we need to implement several classes: class responsible for storing sequence element (Item), processing-class for sequence (List), iterator for navigation along sequence (Iterator). Let us write the basic realization with minimal functionality.

To start with, let us begin with realization of container. So what such container is supposed to do? Apparently, required minimum will conclude in possibility of its creation, options of addition and removal of container’s objects and it deleting with all stored information. Another key point our container has to possess with is being able to be polymorph and find the last element of stored sequence in order to transfer this information to iterator. Processing-class (container) can be expressed in the following view:

#ifndef LIST_CPP
#define LIST_CPP

#include <iostream>
#include "Item.cpp"
#include "Iterator.cpp"

template<class Type>
class List {
    public:
        Item<Type>* last;
        size_t size;

        List() : last(NULL), size(0) {}
        ~List() {
            for ( ; last != NULL; ) {
                Item<Type>* prevItem = last->prev;

                delete last;
                last = prevItem;
                size -= 1;
            }
        }

        void append(Item<Type>* item) {
            if ( last == NULL ) {
                last = item;
            } else {
                last->next = item;
                item->prev = last;
                last = item;
            }
            size += 1;
        }
        void append(Type value) {
            Item<Type>* item = new Item<Type>(value);
            this->append(item);
        }
};

#endif // LIST_CPP

Quite difficult, isn’t it? It really required rough programming skills. Now, let us create wrapper for stored elements. But what is necessary to implement? As many as three things: some repository for values and two pointers for adjacent elements. This complex class is expressed in the next view:

#ifndef ITEM_CPP
#define ITEM_CPP

#include <iostream>

template <class Type>
class Item {
    public:
        Type value;
        Item* prev;
        Item* next;

        Item(Type value) : value(value), prev(NULL), next(NULL) {};
};

#endif // ITEM_CPP

Now it is time for iterator. Since you are familiar to the iterators logic and main working principles I will not repeat such obvious things for you. Let us just write simple class taking into consideration task’s specific, which is our primary target.

#ifndef ITERATOR_CPP
#define ITERATOR_CPP

#include <iostream>
#include "Item.cpp"

template <class Type>
class Iterator {
    private:
        Item<Type>* current;
    public:
        Iterator(Item<Type>* item) : current(item) {}

        void next() {
            if ( current->next != NULL ) {
                current = current->next;
            }
        }

        void operator++() {
            this->next();
        }

        void operator++(int) {
            this->next();
        }

        void prev() {
            if ( current->prev != NULL ) {
                current = current->prev;
            }
        }

        void operator--() {
           this->prev();
        }

        void operator--(int) {
            this->prev();
        }

        void begin() {
            for ( ; current->prev != NULL; current = current->prev );
        }

        void end() {
            for ( ; current->next != NULL; current = current->next );
        }

        Type operator*() const {
            return current->value;
        }

        bool isOver() {
            return current->next == NULL;
        }
};

#endif // ITERATOR_CPP<

Ready. So that, now it is high time to make real test. The code will not be very complex:

#include <iostream>
#include "List.cpp"

int main() {
    List<std::string>* list = new List<std::string>();
    list->append("alpha");
    list->append("bravo");
    list->append("charlie");
    list->append("delta");

    Iterator<std::string> it(list->last);

    it.begin();
    for ( ; !it.isOver(); it++ ) {
        std::cout << *it << std::endl;
    }
    std::cout << *it << std::endl;

    delete list;

    return 0;
}

Received result after compilation and running of this program should not confuse you:

alpha
bravo
charlie
delta

I suppose, none of you have any question regarding patterns’ application. Otherwise, it will be surprisingly if represented code above bred any difficulties in understanding. Conclusively, I assert that creation of either it is dynamical array or linked list is quite trivial task.

Linked List: list, stack, queue

List

Container list represents storage for keeping elements with possibility of its addition or removal during the constant time. List is similar to other containers of standard patterns library, such as vector, array and queue. The main difference of container list consists in its higher performance during addition, removal and elements’ allocation. What also should be noticed is that stored elements in container list do not border to each other in the memory.

Usage of container list is unbelievably complex:

#include <iostream>
#include <list>

int main() {
    std::list<std::string>* lst = new std::list<std::string>();

    lst->push_back("alpha");
    lst->push_back("bravo");
    lst->push_front("charlie");
    lst->push_front("delta");

    std::list<std::string>::iterator it;

    for ( it = lst->begin(); it != lst->end(); it++ ) {
        std::cout << *it << std::endl;
    }

    return 0;
}

As the result we get next:

alpha
bravo
charlie
delta

More in details regarding list container functionality.

Stack

Stack is an adapter, which is implemented particularly for representation of LIFO (Last-in first-out) sequence. Stack has fairly restricted functional and supports such operations:

• Back
• Push_back
• Pop_back

More in details regarding stack container functionality.

Queue

Queue is an adapter which is implemented for representation of FIFO (Fast-in first-out) sequence. Queue has quite restricted functional and supports such operations front

• back
• push_back
• pop_front

More in details regarding queue container functionality.

Sets

Container set is a sequence of unique elements being stored according to established order. Set implementation is based on the self-balancing tree of the binary search. Let us make realization of set:

#

Finally, we receive next result:

alpha
bravo
charlie
delta

Acquired result implies that elements in set container are being stored in order and in compliance with uniqueness of stored elements ‘values.

More in details regarding set container functionality.