#include <iostream>
#include<map>
#include<iterator>
#include<utility>
using namespace std;

void printMap(map<string,int> &fm){
	cout << "size = " << fm.size() << endl;
	//map<string,int>::iterator it;
	for(auto it = fm.begin();it != fm.end();++it){
		//cout << (*it).first << "-" << (*it).second << endl;
		cout << it->first << "-" << it->second << endl;
	}
	cout << endl;
}
int main() {
	//basic initialization.
	map<string,int> m1;
	m1["date"] = 22; //O(log(n));n = current size.
	m1["month"] = 05;
	m1["year"] = 2004;
	printMap(m1);

	//initializing a map using pair,using insert():
	map<string,int> m2;
	m2.insert(make_pair("date",22));
	m2.insert({"month",05});
	printMap(m2);
	m2["day"]; //inserts an empty string to "day" key.
	printMap(m2);

	//find(key):returns the iterator for a specific key in the map.
	//if the key doesnt exist, it will return the iterator for end().
	auto it2 = m2.find("date");
	cout << (*it2).second << endl;
	auto it3 = m2.find("month");
	if(it3 == m2.end())
		cout << "no such key\n";
	else
		cout << it3->second << endl; //-> works only for iterators.
    
    //erase():erases a key. Can take the key or associated iterator as input.
    m2.erase("month"); //O(log(n)
    printMap(m2);
    //passing as iterator.
    auto it4 = m2.find("day");
    m2.erase(it4);
    printMap(m2);
    //passing an iterator that doesnt have a key.
    auto it5 = m2.find("arif"); //points to m2.end()
    
    if (it5 != m2.end())
    	m2.erase(it5);//a non-existent iterator cannot be passed to erase().
    printMap(m2);
    
    //clear(): Clears the whole container.
    m2.clear();
    printMap(m2);
    
    /*insert()'s TC also depends on the key. In a Red Black Tree, when a value is newly
    inserted, its key initially goes through comparison with existent keys and then finds
    the appropiate location to get inserted into.
    	*int -> O(log(n))
    	*string -> O(log(n) + s.size())
    */
    
    
    /*
    Problem: Given N strings, print unique strings in lexicographical order with their frequency.
    N <= 10^5
    |S| <= 100
    */
    map<string,int> m;
    int N;
    cin >> N;
    for(int i=0;i<N;i++){
    	string s;
    	cin >> s;
    	m[s];//m[s] initialized to zero, this line is just for illustration.
    	m[s] = m[s] + 1;//updating frequency of all unique s.
    }
    printMap(m);
    //
    
	return 0;
}
/*
Here’s the updated summary of our chat about maps, including the handling of value overwriting with `insert()` and other methods:

### Summary of Our Chat About Maps

1. **Normal Maps with String Keys**:
   - Keys in maps (dictionaries) can be strings, allowing for dynamic access and organization of values.
   - Accessing values is done using string keys, which can be dynamically assigned.

   ```cpp
   #include <iostream>
   #include <map>
   #include <string>

   int main() {
       std::map<std::string, int> myMap;
       myMap["apple"] = 1;
       myMap["banana"] = 2;
       myMap["cherry"] = 3;

       for (const auto& pair : myMap) {
           std::cout << pair.first << " " << pair.second << std::endl;
       }
       return 0;
   }
   ```

   **Output**:
   ```
   apple 1
   banana 2
   cherry 3
   ```

2. **Sorting Behavior**:
   - In **`std::map`**, keys are automatically sorted in ascending lexicographical order.
   - In **`std::unordered_map`**, there is no guaranteed order for the keys, and their order can appear random.

   ```cpp
   #include <iostream>
   #include <unordered_map>
   #include <string>

   int main() {
       std::unordered_map<std::string, int> myMap;
       myMap["banana"] = 2;
       myMap["apple"] = 1;
       myMap["cherry"] = 3;

       for (const auto& pair : myMap) {
           std::cout << pair.first << " " << pair.second << std::endl;
       }
       return 0;
   }
   ```

   **Output** (order may vary):
   ```
   banana 2
   cherry 3
   apple 1
   ```

3. **Lexicographical Sorting**:
   - Lexicographical order sorts keys based on alphabetical character comparison, similar to how words are arranged in a dictionary.
   - The sorting process considers only the keys, independent of their associated values.

4. **Sorting by Values**:
   - To sort by values instead of keys, extract key-value pairs, sort them based on values, and print them.

   ```cpp
   #include <iostream>
   #include <unordered_map>
   #include <vector>
   #include <algorithm>
   #include <string>

   int main() {
       std::unordered_map<std::string, int> myMap;
       myMap["banana"] = 2;
       myMap["apple"] = 1;
       myMap["cherry"] = 3;

       // Extract key-value pairs into a vector
       std::vector<std::pair<std::string, int>> vec(myMap.begin(), myMap.end());

       // Sort by value
       std::sort(vec.begin(), vec.end(), [](const auto& a, const auto& b) {
           return a.second < b.second; // Compare based on the second element (value)
       });

       // Print sorted key-value pairs
       for (const auto& pair : vec) {
           std::cout << pair.first << " " << pair.second << std::endl;
       }

       return 0;
   }
   ```

   **Output of Sorting by Values**:
   ```
   apple 1
   banana 2
   cherry 3
   ```

5. **Handling Value Overwrites**:
   - If you want to insert a value in a map but might overwrite an existing value, you can use different methods:

   **Using `operator[]`**:
   ```cpp
   myMap["banana"] = 5; // Overwriting the value of "banana"
   ```
   **insert() doesnt allow overwriting.
   **Using `insert_or_assign()` (C++17 and later)**:
   ```cpp
   myMap.insert_or_assign("banana", 5); // Overwriting or inserting
   ```

   **Using `find()` to Check Before Inserting**:
   ```cpp
   auto it = myMap.find(keyToUpdate);
   if (it != myMap.end()) {
       it->second = newValue; // Overwrite
   } else {
       myMap[keyToUpdate] = newValue; // Insert
   }
   ```

6. **Real-World Analogy**:
   - The concept of sorting keys in maps is analogous to looking up words in a dictionary, where words are arranged alphabetically, making them easy to find.

If you have any more questions or need further clarification, feel free to ask!
*/