C++, about map, set
Tags: map, set, unordered, complexity
Published: 2023-12-21 05:13:24

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

```cpp
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

```cpp
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

```cpp
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;
}


```