The basics of programming in c++ for beginners

STL associative containers. Part 6

All previous types of containers (discussed in detail or mentioned: vector, list, and) - A consistent collection, in which the elements are arranged sequentially one after another, but they differ with each other way to access the elements.

Another large category of containers are so-called associative containers, which are, actually, table, search for values ​​which made for some keys.

But before detailing associative containers, pay attention to such a class template (composed of STL) how pair<>. This is a fairly simple design. Each object represents a connected pair of fields first and second. In constructing tables (in STL or in your own classes) These fields may be the key, and the value. But we will not rush - a class template pair<> and may itself be of interest regardless of containers.

We can, for example, determine class 2D representation of points in the plane for a wide class of geometrical problems (file point.h):

point p(*this); means, that creates a new variable (an object) class point, and called its copy constructor. To initialize value is taken of the current object *this – as indicated by the pointer this. That is. a new variable point p created, as a copy of the current object. The rest of you all is to be understood.

Result:

c ++ beginners, Standard Template Library, associative containers STL C ++, pair<> c++

Now, when we see, what a class template pair<>, we can go to the overview of, what are the basic associative STL containers.

In contrast to the previously discussed consecutive containers, where the location of the element is determined by its position among other elements, associative containers are stored as a pair of elements (pair<>) <key, value>. To find the values ​​of the element you want to search its key, which may be the most diverse types.

Note: It could be considered, what in array or vector Search is the key index, which always has integer value. Similarly, generic type table (hashtable) map<>, from which we will start associative type, can be viewed, as an array or vector (for ease of understanding ). It can be indexed by any (but always only one) random key type, type: title[ ‘a’ ], or pay[ “Ivanov” ].

One of the most commonly used is STL associative containers map<> - table, an array of pairs <key, value>, in which the search is performed on a key element.

The key can be any type of complex, on condition, that exists for this type of operation comparison (less - more), or such an operation implemented by the user and is specified when creating a table. To illustrate the simple application map<> We use the already discussed earlier example with a base of students of the Faculty of Information:

Result:

c ++ beginners, Standard Template Library, associative containers STL C ++, pair c++, map<> c++

Even a superficial example (until we went deep into the details of the associative containers) It allows you to see and draw some conclusions:

  • elements, placed in the table, It is not placed in order of their premises (as with vector or list), and in sorted order by key value (FIRST and LAST NAME);

  • That is why the data type key must exist or comparison operation, or it must be created by the user;

For search (by key) associative containers do not use a serial search of all the elements, a highly efficient and sophisticated algorithms, worked for years (and even decades) the existence of the STL . Generally, to implement map<> used technique of red-black trees ... but the details of that are not fundamental. An important conclusion from this fact should be the, that the search for associative containers is very fast, and it is much better, than if you tried to implement it manually.

5 thoughts on “STL associative containers. Part 6

  1. map, set, multiset, multimap – NOT implemented through hash table, and through the red-black trees, at least so in gcc. After the hash table implemented with the prefix containers unordered_. It is very strange that the author with 40 years of experience and such an impressive list of achievements does not know about it.

  2. Почему в примере point в функциях несколько return, если они без ветвлений?

Leave a Reply to Paul Cancel reply

Your email address will not be published. Required fields are marked *