Basic set for solving problems on LeetCode/Codeforces, part 2 Associative Containers C++
There will be 5 articles on topics:
Sequential containers
Associative containers(YOU HERE)
Stacks and queues – they are adapters
Function objects
Basic algorithms – the latter will sometimes slip through all the articles above
Content of the article about associative containers:
1) Sets
-std::set
-std::unordered_set
-std::multiset
2) Dictionaries (HASH-MAPS)
-std::map
-std::unordered_map
-std::multimap
Foreword:
Starting a dialogue about associative containers, first you need to discuss what associativity is in general – if you played “Associations” as a child, then everything is almost obvious to you, because for each object discussed during the game – you need to find something related to this object .
The compiler is not going to play anything with you and stores key-value pairs, but there is a slight difference between std::set And std::map.
IN std::set we store unique values and therefore these values, that is, your objects – numbers, strings, letters, objects of their own types – inside std::set are both keys and values. AND std::set guarantees us that all values are unique, then there is nothing to stop you from making your UNIQUE an object – KEY And VALUE.
IN std::map does not provide a guarantee that all objects are unique and just there all your objects are numbered under some indices, usually from zero to n. This gives you insanely fast access to elements.
std::unordered_map, std::map, std::unordered_set – one of the most frequently encountered in solving problems on LeetCode. Using them greatly simplifies your life and you don’t have to poke around in std::vector every time and add some functions for removing identical elements, which still work slower than associative containers.
Skip this passage to {1) Starting a dialogue about sets} and don’t look at him Attention, if you just need a summary for solving problems – this will not help you in any way in solving problems.
If you have already advanced in C ++, then you are aware of the existence std::multisetwhere the same elements can be stored, although in std::set this cannot be, but how then can a red-black tree be built on the basis of this.
Of course, you cannot add the same elements to the red-black tree, but inside std::multiset for identical elements, a vector is created where your identical elements are added. That is, when you call the count() function, it will find your value in the red-black tree, and if your_vector_with_copies is greater than 1, you will get the length of this vector. Everything is cool, logical and does not violate the red-black tree!
Disclaimer: if you do not know what a red-black tree is, then represent it as a binary search tree, if you do not know what a binary search tree is, then represent it like this:
– forget the colors
– forget about insertion and removal, there will need rotations for balancing
– you can take an even number of elements, but then you will have branches that are not completely filled (in the red-black tree they would be marked as NIL)
And so, you have an ordered set of numbers [от 1 … до 7] inclusive
How would we stack this into a tree in the most efficient way possible?
1) The set of numbers is sorted in ascending order and all we need is to take the element in the middle {1,2,3,4,5,6,7} – found it 4. Therefore, we put it at the very top.
2) After that, we store the numbers to the left 4 to vector {1,2,3} and to the right of the number 4 in the vector {4, 5, 6}.
3) Sort both resulting vectors in ascending or descending order.
4) In each of these vectors, we separately find a number with an average index – 2 And 5.
5) A number less than our top node 4namely 2 put in the left node, and 5 in the right.
6) Compose two vectors {1,3} And {4,6} – the average index cannot be obtained, therefore, relatively 2 distribute 1 And 3and relatively 5 distribute 4 And 6.
Congratulations, you got your first binary tree and you can try to encode it as a 2D array of vectors, try making it with an even number of elements:
A little hint to those who try to do this – in the first example, the number of elements was specially chosen so as not to fall into uncertainty (7 items), that is, at every step except the last of the two elements, the total number of elements was odd. But in the example above, you will get into such uncertainty at the first split, where you will need among {4,5} – choose the largest.
Accordingly, choosing 5, you will get two vectors {1,2,3,4} And {6,7,8}.
In the first vector {1,2,3,4} from {2,3} – again choose 3 and get a balanced tree.
If you are careful enough, then such uncertainty is not tied to the total even number of numbers and you will meet with it even in such a vector where the total number of numbers is 9 == {1,2,3,4,5,6,7,8,9}
In principle, if you understand the essence, then you will not need a drawing, but it’s better to play it safe.
Do not take this passage as a tree guide – it is by no means it, you just need to realize the principle of designing this tree.
1) Unique and sorting – std::set
Brief description: An ordered set of unique elements. It is based on a red-black tree structure and sorts all elements in ascending order after each addition/removal of an element. Due to the absence of unique elements and constant sortings, the elements are arranged strictly monotonously.
Since it constantly sorts itself in ascending order – there are no indices in it, since it is not clear where which element is located, but set guarantees us that the first element is guaranteed to be less [n + C]where C < set.size() - 1, and vice versa.
Function memo:
insert() – adds an element to set if there is no absolute copy of it
erase(key_number) – removes an element from set‘a, since there is no access by index, then erase searches by value and removes the element, then the red-black tree is rebuilt.
find(key_number) – performs a search by value in set‘e if key_number not found – find() will return set end()otherwise *find(key_number) == key_number.
range searches in a sorted set:
lower_bound(key_number) – returns an iterator to a value that is less than lower_bound(key_number).
upper_bound() – returns an iterator to a value that is greater than upper_bound(key_number).
count(key_number) – Returns the number of elements equal to key_number.
I don’t see the point in inserting a code example, the functions are quite obvious, below will be examples with those that you should pay attention to when working with std::set and almost similar ones.
Operations on sets:
(1) Crossing or S*T=I:
Finds identical elements in the specified intervals of two sets and leaves one unique element in the new set I. Result{20, 30}.
set_intersection( S.begin(), S.end(), T.begin(), T.end(), inserter(I, I.begin()));
set<int> set1 = {10, 20, 30};
set<int> set2 = {40, 50};
set<int> exposition;
set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), inserter(exposition, exposition.begin()));
(2) Consolidation or S+T=I:
2 sets are taken and all elements from two sets are added, then duplicates are removed. Result{10, 20, 30, 40, 50}.
set_union( S.begin(), S.end(), T.begin(), T.end(), inserter(I, I.begin()));
//Тут set1 и set2 остались при своих элементах
set<int> set1 = {10, 20, 30};
set<int> set2 = {40, 50};
set<int> exposition;
set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), inserter(exposition, exposition.begin()));
// Более красивый вариант, если позволяет реализация - он быстрее
set<int> set1 = {10, 20, 30};
set<int> set2 = {40, 50};
set1.merge(set2); // после этой операции set2 пустой 2) We have copies, but we are still on a red-black tree and, perhaps, with copy vectors – std::multiset
Short description: Thanks to the miracle of engineering technology, we have been able to store copies in std::multisetwhich is impossible in std::set. Honestly, I have never seen it in other people’s solutions on LeetCode and have never used it anywhere, it seems to me that it exists only as an implementation of storing copies in a red-black tree, and if you sit and think, then in some situations it will be better than just std::map.
If you use it and you need to get the number of identical elements, then use count(key_number) – this is the best.
you can get the span with:
pair equal_range(const key_type& x) const – it will return {i, j} range of values
std::multiset<int> mySet = {1, 2, 3, 3, 3, 4};
//вы пробежитесь по дереву и найдете вектор с вашими числами
//собственно, это метод как получить числа из этого вектора
//count() - вернет вам количество этих чисел
auto range = mySet.equal_range(3);
//выводить так
for (auto it = range.first; it != range.second; ++it) {
if (it != range.first) {
std::cout << ", ";
}
cout << *it;
}
cout<<endl; 3) Now we are not on a red-black tree, but in a hash map – std::unordered_set
Short description: V std::set we got a constantly sorted collection of elements, but in the unordered version we were left without sorting and this is for the better, because we do not always need to sort the elements – the underlying red-black tree std::set constantly balancing and sorting elements to avoid sorting at base std::unordered_set there is a hash table with keys and values, where the key and value are the same, only now we do not have to sort our container in ascending order. Copies are missing here – not to be confused with std::multiset.
I warmly welcome those who lived to see dictionaries or simply rewound here in search of the functions they need.
Foreword: stores if you solved the problem 1.Two Sum on LeetCode, then one of the fastest solutions lies through std::unordered_map and with the naked eye you can see that there is some kind of game of values and iterators:
Given a vector of integers nums and an integer targetreturn the indices of two numbers that add up to give target.
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> mp;
for (int i = 0; i < nums.size(); i++) {
int required = target - nums[i];
if (mp.find(required) != mp.end()) {
return {i, mp[required]};
}
mp[nums[i]] = i;//совсем не типичная инициализация
}
return {-1, -1};
}
mp[nums[i]]= i; – In this version, the following happens inside unordered_mapnums[i] – becomes the key of this mp element. i – becomes a value.
WARNING: nums[i] is the key, and i is the value, if we find the key, then we return the index – since this is required by the task, and it makes no sense to do the opposite, since you will not find the key by value. Reread the condition of the problem if you are confused.
function find() – performs a search by key, namely not by the current index i – value, and nums[i] added as a key.
if you ask for a value mp[nums[i]] – we will get an iterator of a number when added to any other number – we will get the desired target.
I think there are people who don’t know why the return value is in {}.
Remember the initialization of the vector from the first part {1,2,3} – this is what it is, only local and not the fact that it is a vector.
C++ has a class like this std::pair – a pair of values and such a call {1,2} – can be considered as a pair, so you need to look at the return type of the function. There cannot be a pair of 3 values, but there can be such a signature pair<int, pair<int, int>>then the return value will look like this {int, {int, int}};
By the way, if you want to return a two-dimensional vector in this form or read it, then you will get something like this {{1,2,3}}, that is, you will get 1 row and 3 columns, but it all depends on how it is output .
Actually, that’s all you need to know about this type of associative containers, I’ll tell you the rest later.
1) I want to store, delete, insert and find – quickly and immediately: std::map
Short description: It is based on a binary tree, where the elements lying in this tree are keys (Parse the same as with std::set I consider it inappropriate). stores key-value pairs where the keys are unique and sorted in ascending order. Thanks to this system, it allows you to insert and remove elements very quickly by searching by key.
Keys in std::map are unique and the elements are sorted by key.
Function memo:
3 options insert() – adds an element:
1)insert(std::make_pair(ключ, значение))
2)insert({ключ, значение})
3)map[ключ] = значение;
erase(key) – removes element by key
find(key) – performs a search by key, if you forgot, then re-read the analysis of the first task in the preface
In case the element is not found, it returns an iterator to map.end():if (mp.find(required) != mp.end()) – here there is a check for the presence of an element by key, namely, a check for the presence of the difference target – nums[i] in our map.
size() – returns the actual size
the keys are by no means the size of the vector, yes you can number them from zero to n, but that’s not the size.
count(key) – performs a search for the presence of an element with a given key.
if the number exists, then returns 1, if not, then 0.if (map.count(1000) > 0) – this is how a regular check for the presence of an element looks like
2) Now, by one key, we can store multiple values by one key – std::multimap
Short description: A binary tree is created and a vector of values is created for the same key. Keys in std::map are unique and the elements are sorted by key.
The functions are exactly the same, but the question remains how to get multiple values from one key?
multimap<int, int> multimap;
multimap.insert({1, 100});
multimap.insert({1, 200});
multimap.insert({1, 300});
multimap.insert({1, 400});
multimap.insert({1, 500});
// Получаем диапазон с ключом 1
pair<std::multimap<int, int>::iterator, std::multimap<int, int>::iterator> range = multimap.equal_range(1);
// Вывод
for (auto it = range.first; it != range.second; ++it) {
cout << it->second << endl;
}With function equal_range() we already met when we talked about std::multiset
3) The keys are unique, but they are not sorted, although it is more correct to say – std::unordered_map
Short description: met since there is no sorting of keys, then they lie there in the order in which you fill it in and depends on how you delete them, that is, direct hashing and there are no binary trees inside it. The keys are completely unique and the function call equal_range(key) – will return one value.
Thanks to those who read.
