#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!
*/