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)