Map的使用

删除

可以根据目标键值对位于 map 容器中的位置，实现删除该键值对的目的。erase() 方法的语法格式如下：

//删除 map 容器中指定位置的键值对
iterator erase (const_iterator position);
其中，position 为迭代器，指向要删除的键值对。同时该方法会返回一个 iterator 迭代器，其指向的是删除键值对之后的那个键值对。
注意，如果删除的键值对位于 map 容器中最后的位置，则该方法返回的迭代器指向的是最后一个键值对之后的位置（等同于 end() 成员方法返回的迭代器）

//删除 map 容器中指定位置的键值对
iterator erase (const_iterator position);
//删除 map 容器中键为 k 的键值对
size_type erase (const key_type& k);

除了向 erase() 传入目标键值对位于 map 容器中的位置外，还可以传入目标键值对的键的值，该方法会自行根据指定的键找到目标键值对，并将其删除。erase() 方法的语法格式如下：

//删除 map 容器中键为 k 的键值对
size_type erase (const key_type& k);
其中，参数 k 为要删除键值对的键的值，该方法的返回值为成功删除的键值对的个数。

在某些实际场景中，可能需要删除某个指定区域内的所有键值对，也可以通过 erase() 方法实现，其语法格式如下：

//删除 map 容器中位于 [first，last) 区域内的所有键值对
iterator erase (const_iterator first, const_iterator last);
其中，参数 first 和 last 都是迭代器，它们的组合 [first, last) 就表示 map 容器中的某个范围，该方法会删除此范围内的所有键值对，并返回一个迭代器，其指向删除范围之后的第一个键值对。
注意，如果 [fist,last) 范围之后，不再有任何键值对，则 erase() 方法返回的迭代器将指向 map 容器最后一个键值对之后的位置（等同于 end() 成员方法返回的迭代器）。

查找

find函数

count函数

map<string,int>:: iterator ii=m.find("uuu");
if(ii==m.end()){
    cout<<"没有查找到uuu"<<endl;
}
else{
    cout<<"查找uuu成功，并且它的值="<<ii->second<<endl;
}
int ii=m.count("uuu");
if(ii==1){
    cout<<"查找成功"<<endl;
}
else{
    cout<<"查找失败"<<endl;
}

遍历

map<int,int>_map;
map<int,int>::iterator iter;
while(iter!=_map.end()){
	cout << iter->first << ":" << iter->second<<endl;
    iter++;
}
for(iter = _map.begin(); iter != _map.end(); iter++) {
        cout << iter->first << " : " << iter->second << endl;
}

重复

对于map的插入，可以使用insert或者[]的形式。

insert插入非重复的值，如果插入的值重复出现了，则丢弃要插入的值，对原map不作处理

1
2
3

long long x = viewSumMap.find(creators[i])->second;
viewSumMap.erase(creators[i]);
viewSumMap.insert({creators[i], views[i] + x});

[]用来插入值，如果没有出现过，则成功插入，如果插入的值重复出现了，则覆盖原map中已经有的值

viewSumMap[creators[i]] += views[i];
if (viewSumMap[creators[i]]>maxView){
    maxView = viewSumMap[creators[i]];
}

时间复杂度

一. map、set、multimap、multiset
上述四种容器采用红黑树实现，红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为:

插入: O(logN)
查看: O(logN)
删除: O(logN)

二. unordered_map、unordered_set、unordered_multimap、 unordered_multiset
上述四种容器采用哈希表实现，不同操作的时间复杂度为：

插入: O(1)，最坏情况O(N)
查看: O(1)，最坏情况O(N)
删除: O(1)，最坏情况O(N)

搭配`pair`使用

很多时候，映射关系往往不止一个，但是，会关键的key又只有一个，因此我们可以利用pair

使用

pair是将2个数据组合成一组数据，当需要这样的需求时就可以使用pair，如stl中的map就是将key和value放在一起来保存。另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。 pair的实现是一个结构体，主要的两个成员变量是first second 因为是使用struct不是class，所以可以直接使用pair的成员变量。
其标准库类型–pair类型定义在#include <utility>头文件中，定义如下：
类模板：template<class T1,class T2> struct pair
参数：T1是第一个值的数据类型，T2是第二个值的数据类型。
功能：pair将一对值(T1和T2)组合成一个值，这一对值可以具有不同的数据类型（T1和T2），两个值可以分别用pair的两个公有函数first和second访问。

pair<T1, T2> p1;            //创建一个空的pair对象（使用默认构造），它的两个元素分别是T1和T2类型，采用值初始化。
pair<T1, T2> p1(v1, v2);    //创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2。
make_pair(v1, v2);          // 以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型。
p1 < p2;                    // 两个pair对象间的小于运算，其定义遵循字典次序：如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回true。
p1 == p2；                  // 如果两个对象的first和second依次相等，则这两个对象相等；该运算使用元素的==操作符。
p1.first;                   // 返回对象p1中名为first的公有数据成员
p1.second;                 // 返回对象p1中名为second的公有数据成员

创建

typedef pair<string,string> Author;
Author proust("March","Proust");
Author Joy("James","Joy");
// 
pair<string, string> anon;        // 创建一个空对象anon，两个元素类型都是string
pair<string, int> word_count;     // 创建一个空对象 word_count, 两个元素类型分别是string和int类型
pair<string, vector<int> > line;  // 创建一个空对象line，两个元素类型分别是string和vector类型

接收`pair`

std::pair<std::string, int> getPreson() {
    return std::make_pair("Sven", 25);
}
 
int main(int argc, char **argv) {
    std::string name;
    int ages;
 
    std::tie(name, ages) = getPreson();
 
    std::cout << "name: " << name << ", ages: " << ages << std::endl;
 
    return 0;
}

删除

查找

遍历

重复

时间复杂度

搭配pair使用

使用

创建

接收pair

搭配`pair`使用

接收`pair`