In this post, I will introduce the Unlike the easy version The following codes are self-explained.<\/p>\n Ordered containers are optimized for searching in $(log(n))$.<\/p>\n The following codes are self-explained.<\/p>\n 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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6,5],"tags":[],"class_list":["post-51","post","type-post","status-publish","format-standard","hentry","category-c","category-proglang"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/51","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=51"}],"version-history":[{"count":10,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/51\/revisions"}],"predecessor-version":[{"id":485,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/51\/revisions\/485"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=51"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=51"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=51"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}map<\/code> and priority_queue<\/code> in c++ STL.<\/p>\nWhy Ordered Containers<\/h2>\n
unordered_map<\/code>, in map<\/code>, key values are generally used to sort. Thanks to the binary search tree, map<\/code> has good performance in search and erase elements $(log(n))$.<\/p>\nConstructor<\/h2>\n
\n\/\/ Example of usage of priority_queue\n\/\/ override < is a easy solution\nstruct T {\n int t, x, y;\n T(int a, int b, int c) : t (a), x (b), y (c){}\n bool operator< (const T &d) const {return t > d.t;}\n };\n\nvoid temp(vector<vector<int>> & grid) {\n int N = grid.size (), res = 0;\n priority_queue#include <iostream>\n#include <map>\n#include <set>\n\nclass Compare {\npublic:\n bool operator() (int const & a, int const &b) const {\n return a > b;\n }\n};\n\nint main(){\n \/\/ class based\n Compare compare_instance;\n \/\/ lambda based\n auto comp = [](int i, int j){return i > j;};\n map<int, std::string, decltype(comp)> int2Str(comp);\n \/\/ map<int, std::string, Compare> int2Str(compare_instance);\n multiset<int, decltype(comp)> int_set(comp);\n unordered_map<int, string> int2str_no_order = {{5, \"five\"}, {1, \"one\"}, {4, \"four\"}, {3, \"three\"},\n {2, \"two\"}, {7, \"seven\"}, {6, \"six\"} };\n for (auto k_v : int2str_no_order) {\n int2Str[k_v.first] = k_v.second;\n int_set.insert(k_v.first);\n }\n\n \/\/ can repeat\n int2Str.insert(make_pair(7, \"seven\"));\n int_set.insert(7);\n for (auto p : int2Str) {\n cout << \"{\" << p.first << \",\" << p.second << \"} \";\n }\n \/\/ {7,seven} {6,six} {5,five} {4,four} {3,three} {2,two} {1,one}\n cout << endl;\n for (auto p : int_set) {\n cout << p << \" \";\n }\n \/\/ 7 7 6 5 4 3 2 1\n return 0;\n}<\/code><\/pre>\nSearch Funcitons<\/h2>\n
\n\n
\n \nFunctions<\/th>\n <\/th>\n<\/tr>\n<\/thead>\n \n ordAssCont.count(key)<\/td>\n Returns the number of values with the key.<\/td>\n<\/tr>\n \n ordAssCont.find(key)<\/td>\n Returns the iterator of key in ordAssCont. If there is no key in ordAssCont it returns ordAssCont.end().<\/td>\n<\/tr>\n \n ordAssCont.lower_bound(key)<\/td>\n Returns the iterator to the first key in ordAssCont in which key would be inserted.<\/td>\n<\/tr>\n \n ordAssCont.upper_bound(key)<\/td>\n Returns the iterator to the last position of key in ordAssCont in which key would be inserted.<\/td>\n<\/tr>\n \n ordAssCont.equal_range(key)<\/td>\n Returns the range ordAssCont.lower bound(key) and ordAssCont.upper_bound(key) in a std::pair.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n #include <iostream>\n#include <set>\n\nint main(){\n std::multiset<int> mySet{3, 1, 5, 3, 4, 5, 1, 4, 4, 3, 2, 2, 7, 6, 4, 3, 6};\n\n for (auto s: mySet) std::cout << s << \" \"; \/\/ 1 1 2 2 3 3 3 3 4 4 4 4 5 5 6 6 7\n std::cout<<\"\\n\";\n\n mySet.erase(mySet.lower_bound(4), mySet.upper_bound(4));\n for (auto s: mySet) std::cout << s << \" \"; \/\/ 1 1 2 2 3 3 3 3 5 5 6 6 7\n std::cout<<\"\\n\";\n\n std::cout << mySet.count(3) << std::endl; \/\/ 4\n std::cout << *mySet.find(3) << std::endl; \/\/ 3\n std::cout << *mySet.lower_bound(3) << std::endl; \/\/ 3\n std::cout << *mySet.upper_bound(3) << std::endl; \/\/ 5\n auto pair= mySet.equal_range(3);\n std::cout << \"(\" << *pair.first << \",\" << *pair.second << \")\"; \/\/ (3,5)\n\n return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"