Summary
In this post, I will introduce the map and priority_queue in c++ STL.
Why Ordered Containers
Unlike the easy version unordered_map, in map, key values are generally used to sort. Thanks to the binary search tree, map has good performance in search and erase elements $(log(n))$.
Constructor
The following codes are self-explained.
// Example of usage of priority_queue
// override < is a easy solution
struct T {
int t, x, y;
T(int a, int b, int c) : t (a), x (b), y (c){}
bool operator< (const T &d) const {return t > d.t;}
};
void temp(vector<vector<int>> & grid) {
int N = grid.size (), res = 0;
priority_queue pq;
pq.push(T(grid[0][0], 0, 0));
}
#include <iostream>
#include <map>
#include <set>
class Compare {
public:
bool operator() (int const & a, int const &b) const {
return a > b;
}
};
int main(){
// class based
Compare compare_instance;
// lambda based
auto comp = [](int i, int j){return i > j;};
map<int, std::string, decltype(comp)> int2Str(comp);
// map<int, std::string, Compare> int2Str(compare_instance);
multiset<int, decltype(comp)> int_set(comp);
unordered_map<int, string> int2str_no_order = {{5, "five"}, {1, "one"}, {4, "four"}, {3, "three"},
{2, "two"}, {7, "seven"}, {6, "six"} };
for (auto k_v : int2str_no_order) {
int2Str[k_v.first] = k_v.second;
int_set.insert(k_v.first);
}
// can repeat
int2Str.insert(make_pair(7, "seven"));
int_set.insert(7);
for (auto p : int2Str) {
cout << "{" << p.first << "," << p.second << "} ";
}
// {7,seven} {6,six} {5,five} {4,four} {3,three} {2,two} {1,one}
cout << endl;
for (auto p : int_set) {
cout << p << " ";
}
// 7 7 6 5 4 3 2 1
return 0;
}Search Funcitons
Ordered containers are optimized for searching in $(log(n))$.
| Functions | |
|---|---|
| ordAssCont.count(key) | Returns the number of values with the key. |
| ordAssCont.find(key) | Returns the iterator of key in ordAssCont. If there is no key in ordAssCont it returns ordAssCont.end(). |
| ordAssCont.lower_bound(key) | Returns the iterator to the first key in ordAssCont in which key would be inserted. |
| ordAssCont.upper_bound(key) | Returns the iterator to the last position of key in ordAssCont in which key would be inserted. |
| ordAssCont.equal_range(key) | Returns the range ordAssCont.lower bound(key) and ordAssCont.upper_bound(key) in a std::pair. |
The following codes are self-explained.
#include <iostream>
#include <set>
int main(){
std::multiset<int> mySet{3, 1, 5, 3, 4, 5, 1, 4, 4, 3, 2, 2, 7, 6, 4, 3, 6};
for (auto s: mySet) std::cout << s << " "; // 1 1 2 2 3 3 3 3 4 4 4 4 5 5 6 6 7
std::cout<<"\n";
mySet.erase(mySet.lower_bound(4), mySet.upper_bound(4));
for (auto s: mySet) std::cout << s << " "; // 1 1 2 2 3 3 3 3 5 5 6 6 7
std::cout<<"\n";
std::cout << mySet.count(3) << std::endl; // 4
std::cout << *mySet.find(3) << std::endl; // 3
std::cout << *mySet.lower_bound(3) << std::endl; // 3
std::cout << *mySet.upper_bound(3) << std::endl; // 5
auto pair= mySet.equal_range(3);
std::cout << "(" << *pair.first << "," << *pair.second << ")"; // (3,5)
return 0;
}