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):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include <iostream> using namespace std; // класс point наследуется от класса pair<float, float> class point : protected pair<float, float> { public: // конструкторы point(void) { first = second = 0; } point(float x, float y) { first = x; second = y; } point operator -(const point& sub) { point p(*this); p.first -= sub.first; p.second -= sub.second; return p; // разница по координатам } float abs(void) { return sqrt(first * first + second * second); return 0; } inline friend ostream& operator <<(ostream& out, const point& obj) { return out << "<" << obj.first << "," << obj.second << ">"; return out; } }; int main(int argc, char *argv[]) { point p1(1, 3), p2(3, 1); cout << "the distance between two points " << p1 << " & " << p2 << " is " << (p1 - p2).abs() << endl; } |
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:
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include <iostream> #include <string> #include <map> using namespace std; struct data1 { int group, age, scholarship; // группа, возраст, стипендия data1(void) { group = age = scholarship = 0; } data1(int group, int age, int scholarship = 0) : group(group), age(age), scholarship(scholarship) {} data1(const data1& d) : group(d.group), age(d.age), scholarship(d.scholarship) {} inline friend ostream& operator <<(ostream& out, const data1& obj) { return out << "[" << obj.group << " : " << obj.age << " : " << obj.scholarship << " ]"; } }; // это и есть наша таблица, журнал деканата, ФИО здесь - ключ: typedef map< string, data1 > faculty; int main(void) { setlocale(LC_ALL, "rus"); faculty filology; // заполняем поочерёдно 3 записи в журнал: filology.insert(pair< string, data1 >("Сидоров С.С.", data1(13, 19, 1500))); filology.insert(pair< string, data1 >("Иванов И.И.", data1(13, 20))); filology.insert(pair< string, data1 >("Петров П.П.", data1(11, 21))); // вывод на экран ФИО и учётных данных for (auto i = filology.begin(); i != filology.end(); i++) { cout << i->first << " : " << i->second << endl; } data1 d1(filology["Иванов И.И."]); data1 d2 = filology["Иванов И.И."]; cout << d2 << endl; } |
Result:
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.
Author, you asshole, shkolota fucking. At that time I spent?
Examples of bulky code, newcomer are quite difficult to catch!
It feels, that write comments here mentally retarded.
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.
Почему в примере point в функциях несколько return, если они без ветвлений?