关联容器

关联容器

map

1. map类型通常被称为关联数组，关联数组下标不必是整数
2. map下标运算符都支持一个索引，如果关键字不在map中，会为他创建一个元素并插入到map中，关联值进行值初始化
3. 关联容器也是模板，定义map必须指定关键字和值的类型
4. 定义map时，使用map的key需要定义operator<
5. map不允许两个元素拥有同样的键值

6. map的所有元素都会根据键值自动排序，map的所有元素都是pair，从map中提取一个元素时，得到一个pair类型的对象，pair是一个模板类型，保存两个名为first和second的共有数据成员，map使用的pair用first保存关键字，second保存对应的值

   //经典的使用关联数组的例子是单词计数程序
   map<string,size_t> word_count; //map word_count关键字类型是string，值得类型是size_t
   string word;
   while(cin>>word)
       ++word_count[word];//提取word的计数器，并将其+1，使用string作为下标
   for(const suto &w:word_count)//遍历map中的每个元素
       cout<<w.first<<"occurs"<<w.second
           <<((w.second>1)?"times":"time")<<endl;

7. map底层是以红黑树数据结构实现的，根据中序遍历得到有序遍历

8. 插入操作insert函数，调用红黑树的insert_unique函数，函数返回值类型pair<iterator,bool>，迭代器指向被插入的元素bool表明插入与否
9. 不重复容器find和count差不多
10. 对于包含不重复关键字的容器，添加单一元素的insert和emplace版本返回一个pair
11. 递增计数器：++ret.first->second//等价于++((ret.first)->second)
12. 通过传递给erase一个迭代器或者一个迭代器对来删除一个元素和一个元素范围，另一种erase操作，接受一个key_type参数，删除所有匹配给定关键字的元素，返回实际删除的元素的数量
13. 对于保存不重复关键字的容器，erase的返回值总是0或者1，若返回值为0，表示想要删除的元素不在容器内，对于允许重复关键字的容器，删除元素可能大于1
14. 允许重复的容器multimap，equal_range接受一个关键字，返回一个迭代器pair，first指向第一个元素，second指向最后一个匹配元素之后的位置（和lower_bond和upper_bond作用一样）

set

1. set所有元素会根据元素的键值自动排序
2. set键值就是实值，实值就是键值，set类型不支持下标
3. set不允许两个元素有两个相同的键值
4. 标准的STL set是以红黑树为低层机制
5. set的关键字也是const，使用set迭代器不能修改元素的值
6. multiset允许多个元素具有相同的关键字
7. 允许重复的容器使用count计数，如果不需要计数用find

   //扩展单词计数程序，忽略常见单词
   map<string,size_t> word_count;
   set<string> exclude={"The","But","And","Or","An","A","the","but","and","or","an","a"};
   string word;
   while (cin>>word)
        if(exclude.find(word)==exclude.end())//检查单词是否在忽略列表内
           ++word_count[word];

vector<int> ivec;
for(vector<int>::size_type i=0;i!=10;++i){
    ivec.push_back(i);
    ivec.push_back(i);
}
set<int> iset(ivec.cbegin(),ivec.cend());//不重复元素
multiset<int> miset(ivec.cbegin(),ivec.cend());//重复元素
cout<<ivec.size()<<endl;
cout<<iset.size()<<endl;
cout<<miset.size()<<endl;

unordered_map

1. 无序映射的关联容器
2. 记录元素的hash值，根据key的hash值判断元素是否相同
3. 需要定义hash_value函数并且重载operator==
4. leetcode49

   #include <iostream>
   #include <string>
   #include <vector>
   #include <unordered_map>
   #include <utility>
   using namespace std;
   
   vector<vector<string>> groupAnagrams(vector<string>& strs);
   
   int main() {
       vector<string> strs({"ate","eat","tea","tan","nat","bat"});
       auto res=groupAnagrams(strs);
       for(auto c:res)
       {
           for(auto& s:c)
               cout<<s<<" ";
           cout<<endl;
       }
   }
   
   vector<vector<string>> groupAnagrams(vector<string>& strs) {
       vector<vector<string>> res;
       unordered_map<string,vector<string>> m;
       for(auto s:strs)
       {
           string tmp=s;
           sort(tmp.begin(), tmp.end());
           m[tmp].push_back(s);
       }
       for(auto c:m)
           res.push_back(c.second);
       return res;
   }