STL III
Agenda
1. Associative containers
○ Associative Properties
○ Prerequisite: Pair
○ Set
○ Multiset
○ Map
○ Multimap
2. Important methods
3. Unordered containers
1. Associative containers
● Associative containers are special containers that keep their elements
sorted at all times.
● When we add a new element, the container automatically finds the best
place to put it in to maintain the sorted order. Unlike sequence containers,
we cannot specify exactly where the new element should go, as the
container has its own way of organizing the elements. Instead, we wait
for the container to do its job and return an iterator pointing to the new
element's position.
● One big advantage of associative containers is their fast search
complexity, which is O(𝑙𝑜𝑔(𝑛)). This means that even with a large
number of elements, searching for a specific element is much faster than
with sequence containers, which have a search complexity of O(𝑛).
● Additionally, insertions and deletions are also efficient, with a complexity
of O(𝑙𝑜𝑔(𝑛)), while still maintaining dynamic properties. However, we
lose the ability to access elements randomly based on their original order.
a. Associative Properties
Property Associative
Size Dynamic
Random Access No
Search O(log n)
Insert O(log n)
Erase O(log n)
Before we dive into associative containers, let's first discuss a simple
container called pair. As its name suggests, it holds a pair of values. When
we create a pair, we specify two types for it - one for the first value and one
for the second value. Let's look at an example to understand it better.
b. Pair
pair<type of first, type of second> p;
pair<string, int> p;
p.first = "ahmed";
p.second = 20;
p = {"ahmed", 20}; // C++ 11 or more
p = make_pair("ahmed", 20);
Associative Containers are divided into:
● Set
● Multiset
● Map
● Multimap
c. Set
#include <set>
set <type> name;
set <int> s;
● Set is a container that organizes its
elements in a particular order.
● It never contains any duplicates. This
means that every element inside a set
is unique.
● Set automatically sorts its elements as we insert them, ensuring that
they remain in a specific order.
Let's take a closer look to understand how it works.
i. Set insert
set<int> s;
/* insert function returns a pair, where the first is the
value to be inserted and the second is boolean indicating
whether the value is added or was already exist
*/
s.insert(2);
s.insert(0);
s.insert(1);
s.insert(0);
auto ins = s.insert(5);
cout << *(ins.first) << " " << ins.second; // 5 1
ins = s.insert(2);
cout << *(ins.first) << " " << ins.second; // 2 0
ii. Set erase
set<int> s = {1, 2, 3, 4, 5, 6, 7};
// erase function returns an integer which is the number of
items erased
s.erase(4);
int cnt = s.erase(9);
// cnt = 0
cnt = s.erase(5); // cnt = 1
// erase can work with iterators too
s.erase(s.begin());
auto it1 = s.begin(), it2 =
s.end();
it1++, it2--;
s.erase(it1, it2); /* O(log(n)+ NO. of
erased elements)
also erase works with ranges but the
range must be iterators range
[start,end[ (start included, end excluded)*/
iii. Set find
auto it = s.find(10);
if(it!= s.end())
cout << "Found" << endl;
else
cout << "Not Found" << endl;
if(s.count(10))
cout << "Found" << endl;
else
cout << "Not Found" << endl;
iv. Set Traversing
// forward iterator method
for(auto it = s.begin(); it != s.end(); it++)
cout << *it << " "; // asterisk to get the value
// range-based method
for(auto it: s)
cout << it << " ";
v. Set Use Cases
● Finding distinct elements: You may be given a list of numbers or
strings and be asked to find the number of distinct elements in the
list. This can be easily achieved by inserting each element into a
set, as Sets only store unique elements. Here’s an example:
int countDistinct(vector<element> v) {
set<element> st;
for (auto elem : v)
st.insert(elem);
return st.size();
}
● Removing duplicates: Sets are very useful when it comes to
removing duplicates from an array or vector. Suppose you have an
array of integers and you want to remove duplicates from it. You
can simply insert all the elements of the array into a set, which will
automatically remove duplicates. Here's an example:
void removeDuplicates(vector<element> v) {
set<element> st;
for (auto elem: v)
st.insert(elem);
for(auto elem : st)
cout << elem << " ";
}
Overall, Set is an important data structure in computer science, providing
efficient access, insertion, and deletion of elements, while maintaining the
ordering and uniqueness of the elements.
d. Multiset
#include <set>
multiset <type> name;
multiset <int> ms;
Multisets are just a version of Sets that
allow duplicate values and almost have
the same operations as Sets.
i. Multiset Common Operations
multiset<int> ms;
ms.insert(2);
ms.insert(0);
ms.insert(0);
ms.insert(2);
// the erase removes all
occurrences of a value
ms.erase(0);
// to remove exactly one occurrence we would need an
iterator pointing to the value which is returned from the
.find() function
ms.erase(ms.find(2));
Do not use the count function if u just need to check whether the
element exist or not.
ii. Multiset Use Cases
● Finding kth smallest/largest element: We can use a multiset to
store the elements and then use the nth_element algorithm to find
the kth smallest/largest element efficiently. For example, given an
array of integers and an integer k, we can find the kth smallest
element using the following code:
int kthSmallest(vector<int> v, int k) {
multiset<int> ms;
for (int i = 0; i < (int) v.size(); i++)
ms.insert(v[i]);
auto it = ms.begin();
advance(it, k - 1);
return *it;
}
● Sliding window problems: In some problems, we need to
maintain a sliding window of elements and perform operations on
that window, such as finding the minimum or maximum element in
the window. We can use a multiset to store the elements in the
window and perform these operations efficiently. For example,
given an array of integers and a window size k, we can find the
maximum element in each window using the following code:
vector<int> maxInWindow(vector<int> v, int k) {
vector<int> window;
multiset<int> ms;
for (auto it : v)
ms.insert(it);
for (int i = k - 1; i < v.size(); i++) {
window.push_back(*ms.rbegin());
ms.erase(ms.find(v[i - k]));
ms.insert(v[i]);
}
return window;
}
Overall, multisets can be a powerful tool in competitive programming,
allowing us to efficiently store and manipulate a collection of elements,
including duplicates.
e. Map
#include <map>
map <key_type,value_type> name;
map <string, int> mp;
● Maps enable us to store pairs of values that
are associated with each other.
● We can access the second value in each pair
by using the first value as a key.
● Maps are ordered (sorted) and do not contain
duplicates (According to keys).
i. Map Common Operations
// key is string and value is int
map<string, int> fruits;
fruits["Apple"] = 10;
fruits["Orange"] = 2;
// another way to add value to map
fruits.insert({"Banana", 6});
cout << fruits["Apple"]; //prints 10
// if we tried to access a key which does not exist the map
will create a pair with that key and a default value for int
cout << fruits["Avocado"]; //prints 0
fruits.erase("orange");
fruits["Apple"] = 9;
auto it = fruits.find("Apple");
if (it != fruits.end())
cout << (*it).first << " " << it->second << endl;
//prints Ahmed 9
ii. Map Traversing
// forward iterator method
for(auto it = mp.begin(); it != s.end(); it++)
cout << (*it).first << " " << it->second << endl;
// range-based method
for(auto it : mp)
cout << it.first << " " << it.second << endl;
iii. Map Use Cases
● Counting the frequency of elements: A map can be used to count
the frequency of elements in an array or sequence. We can iterate
over the sequence, insert each element as a key in the map, and
increment its value each time we encounter it. Here's an example:
void countFrequency(vector<element> v) {
map<element, int> freq;
for (int i = 0; i < (int)v.size(); i++)
freq[v[i]]++;
for (auto elem: freq)
cout << elem.first << " occurs " << elem.second
<< " times" << endl;
}
● Finding nearest elements: A map can be used to find the nearest
elements to a given value. For example, we can use a map to store
the positions of elements in an array, where the keys are the
elements themselves and the values are their positions. Then, given
a value x, we can find the nearest elements to x by finding the
lower and upper bounds of x in the map. Here's an example:
int nearest(vector<int> v, int target) {
map<int, int> pos;
for (int i = 0; i < (int) v.size(); i++)
pos[v[i]] = i;
auto it = pos.lower_bound(target);
if (it == pos.begin())
cout << v[it->second] << endl;
else if (it == pos.end()) {
it--;
cout << v[it->second] << endl;
} else {
auto it2 = it--;
cout << ((target - it->first < it2->first -
target) ? v[it->second] : v[it2->second]) << endl;
}
}
Overall, maps are very versatile and can be used in many different types
of problems in competitive programming.
f. Multimap
#include <map>
multimap<key_type,value_type> name;
multimap <string, int> mp;
Multimaps are just a version of Maps that allow
duplicate values and almost have the same
operations as Maps.
i. Multimap Common Operations
// key is string and value is int
multimap<string, int> fruits;
// the only way to insert into map
fruits.insert({"Apple", 2});
fruits.insert({"Apple", 4});
fruits.insert({"Apple", 6});
fruits.insert({"Banana", 10});
// this method is not available in
multimap
cout << fruits["Apple"];
cout << fruits.count("Apple"); // prints 3
fruits.erase("Apple");
// removes all occurrences of key
🞿 Do not use the count function if u just need to check whether the
element exist or not.
2. Important methods
Priority
Vector Deque Stack Queue Set Map
Queue
size size size size size size size
swap swap swap swap swap swap swap
push_back push_back push push push insert insert
pop_back pop_back pop pop pop erase erase
insert push_front top front top find find
erase pop_front count count
(multi) (multi)
clear clear clear clear
insert
erase
3. Unordered containers
Unordered containers are associative containers that were introduced in
C++11. They use a concept called hashing to optimize the average
complexity of search, insertion, and deletion operations to O(1). However, in
the worst case, the complexity can still be O(n). While we are not always
interested in using unordered containers for competitive programming, they
can be useful in real-life applications and in some cases in competitions
when we are confident that our algorithm will not encounter worst-case
scenarios.
Unordered Containers are divided into:
● unordered_set
● unordered_multiset
● unordered_map
● unordered_multimap
