std::map and std::set ( std::unordered_map and std::unordered_set) share similar time complexity for their basic operations
Big O of map and set
- Building : O(n* log n)
- Find : O(log n)
- Insert : O(log n)
- Erase : O(log n) At default all items are sorted as ascending order.
Example of map
int main() { // default order (ascending) map<int, bool> m_map = { {5,true},{4,false},{8,true},{2,false} }; // descending order map<int, bool, std::greater<int>> des_map = { {5,true},{4,false},{8,true},{2,false} }; des_map.insert({ 10,true });// insert des_map.insert(pair<int, bool>(3, false));//insert pair des_map.insert(make_pair(9, true));// make_pair des_map.erase(5);// erase a key auto f_it = des_map.find(123); // just find item if (f_it != des_map.end()) { cout << "found in map" << endl; } else cout << "not found" << endl; if (des_map[123]) // create if not exist { cout << "found in map" << endl; } else cout << "not found" << endl; cout << "=========== items in map ========" << endl; for (auto it : des_map) { cout << " " << it.first << " " << std::boolalpha<<it.second << endl; } return 0; } Custom key map
struct People { int age; string name; People(int a = 0, string s = "") { age = a; name = s; } // overload operator to compare bool operator< (const People& p) const { return age < p.age || (age == p.age && name < p.name); } // need for std::greater<People> bool operator> (const People& p) const // use People with other STL function { return age > p.age || (age == p.age && name > p.name); } bool operator== (const People& p) const // use People with other STL function { return (age == p.age && name == p.name); } }; void custom_key_map() { // Creating a map with People as keys and string as values std::map<People, std::string, greater<People>> peopleMap; // Create instances of People People person1{ 25, "Alice" }; People person2{ 30, "Bob" }; People person3{ 21, "Charlie" }; // Inserting values into the map peopleMap[person1] = "Engineer"; peopleMap[person2] = "Doctor"; peopleMap[person3] = "Artist"; // Iterating through the map for (const auto& pair : peopleMap) { std::cout << "Age: " << pair.first.age << ", Name: " << pair.first.name << ", Profession: " << pair.second << std::endl; } // Creating a People object for Bob People bob{ 30, "Bob" }; // Using find to check if Bob exists in the map auto it = peopleMap.find(bob); if (it != peopleMap.end()) { std::cout << "Bob exists in the map. Profession: " << it->second << std::endl; } else { std::cout << "Bob doesn't exist in the map." << std::endl; } } Example of set
int main() { map<int, int> i_map;// ascending order map<int, int, std::greater<int>> des_map;//desending order unordered_map<int, int> u_map;// unordered_map vector<int> iV = { 5,2,8,4,3,5,8,16 }; set<int> i_s(iV.begin(),iV.end());// ascending order if (i_s.insert(5).second == false) { cout << " already in set" << endl; } else cout << " inserted" << endl; auto fit =i_s.find(123);// find if (fit != i_s.end()) { cout << " in set" << endl; } else cout << " not found" << endl; i_s.erase(5);// erase set<int, std::greater<int>> des_set(iV.begin(),iV.end());// descending order unordered_set<int> u_set; cout << "====== ascending set=====" << endl; for (auto i : i_s) cout << " " << i << endl; cout << "======= descending set=====" << endl; for (auto i : des_set) cout << " " << i << endl; return 0; }
Top comments (0)