The mechanism of templates is built into the C++ compiler to allow programmers to make their code shorter through generalized programming. Naturally, there are also standard libraries that implement this mechanism. STL is the most efficient C++ library today.

Now there are many of its implementations, each of which, though created within the framework of the standard, has its own extensions. This approach has one disadvantage: the code will not always work the same way with different compilers. That’s why we strongly recommend you to stick to traditional methods as much as possible, no matter how well you understand a particular library implementation.

First acquaintance

To begin with, let’s look at the most popular collections from the library. Each of them has its own set of template parameters in order to be as convenient as possible for as wide a range of tasks as possible.

Collections

To use a collection in your code, use the following directive:

include ,

where T is the name of the collection

So, the most commonly used ones are:

  • vector — коллекция элементов, сохраненных в массиве, изменяющегося по мере необходимости размера (обычно, увеличивающегося);
  • list — коллекция, хранящая элементы в виде двунаправленного связанного списка;
  • map — коллекция, сохраняющая пары вида , т.е. каждый элемент — это пара вида <ключ, значение>, при этом однозначная (каждому ключу соответствует единственное значение), где ключ — некоторая характеризующая значение величина, для которой применима операция сравнения; пары хранятся в отсортированном виде, что позволяет осуществлять быстрый поиск по ключу, но за это, естественно, придется заплатить: придется так реализовывать вставку, чтобы условие отсортированности не нарушилось;
  • set — это отсортированная коллекция одних только ключей, т.е. значений, для которых применима операция сравнения, при этом уникальных — каждый ключ может встретиться во множестве (от англ. set — множество) только один раз;
  • multimap — map, в котором отсутствует условие уникальности ключа, т.е. если вы произведете поиск по ключу, то получите не единственное значение, а набор элементов с одинаковым значением ключа; для использования в коде используется #include ;
  • multiset – a collection with the same difference from set as multimap from map, i.e. with the absence of the key uniqueness condition; for connection: #include .

Strings

Any serious library has its own classes for representing strings. In STL strings are represented in both ASCII and Unicode formats:
string – a collection of single-byte characters in ASCII format;
wstring – a collection of two-byte characters in Unicode format; included by the #include command.

Iterators

A very important concept in the implementation of dynamic data structures is an iterator. Informally, an iterator can be defined as an abstraction that behaves like a pointer, perhaps with some restrictions. Strictly speaking, an iterator is a more general concept, and is an object wrapper for a pointer, so a pointer is an iterator.

Collection methods

The main methods present in almost all collections are the following:

  • empty – determines if the collection is empty;
  • size – returns the size of the collection;
  • begin – returns a direct iterator pointing to the beginning of the collection;
  • end – returns a direct iterator pointing to the end of the collection, i.e. to a nonexistent element after the last one;
  • rbegin – returns the back iterator to the beginning of the collection;
  • rend – returns the back iterator to the end of the collection;
  • clear – clears the collection, i.e. deletes all its elements;
  • erase – removes certain elements from the collection;
  • capacity – returns the capacity of the collection, i.e. the number of elements this collection can hold (actually, how much memory is allocated for the collection).

The capacity of the collection, as it was said in the beginning, changes as needed, i.e. if the memory allocated for the collection is already full, then when adding a new element, the capacity of the collection will be increased, and all the values that were in it before the increase will be copied to the new memory area – this is a rather “expensive” operation.

Vector

The most frequently used collection is a vector. It is very convenient that this collection has the same operator [] as a regular array. The map, deque, string and wstring collections have the same operator.

It is important to realize that the capacity of a vector changes dynamically. Usually a multiplicative approach is used to increase the size: the memory allocated for a vector is increased by a constant number of times if necessary, i.e. if adding a new element will cause the array size to exceed the capacity, the operating system will allocate a new memory location for the program, for example, twice as large, into which all values from the old memory location will be copied and a new value will be added to it.

By Programming languages