Cpp浅析系列-STL之map

前言

CPP

map 是有序的键值对容器，元素的键是唯一的，值允许重复。用比较函数 Compare 排序键。搜索、移除和插入操作拥有对数复杂度，即O(logn)。 底层实现为红黑树。

Map定义

需要包含模板类头文件，需要关键字和存储对象两个模板参数。

这样就定义了一个用int作为索引，并拥有相关联的指向string的指针.

#include <map> 
using namespace std;
 
void init() {
    map<int, string> m1;//空对象
    //自带初值
    map<int, string> m2(
            {
                    {1, "A"},
                    {3, "C"},
                    {2, "B"}
            }
    );
    //默认按照索引less递增输出为
    // 1 A
    // 2 B
    // 3 C
    map<int, string,greater<int>> m3(
            {
                    {1, "A"},
                    {3, "C"},
                    {2, "B"}
            }
    );
    // 3 C
    // 2 B
    // 1 A
}

有时候为了使用方便，可以对模板类以及指针定义成为更简单的名字。

typedef map<int,string> istrmap;
typedef map<int,string>::iterator IT;
 
istrmap map1;
IT iter

Map常规操作

成员函数

C++中文在线手册：https://zh.cppreference.com/

增加元素

总共有三种插入方式。

void add1() {
    map<int, string> m(
            {
                    {1, "A"},
                    {3, "C"},
                    {2, "B"}
            }
    );
 
    // 当索引是不存在的值，成功插入；当索引已经存在，则不进行操作
    //调用make_pair函数模板，好处是构造对象不需要参数，用起来更方便
    m.insert(pair<int, string>(24, "Z"));
    m.insert(map<int, string>::value_type(23, "Y"));
    m.insert(make_pair(1, "Z"));
 
    // 索引是原先没有的，直接插入；索引已经存在直接修改
    m[22] = "X";
    m[3] = "X";
 
    // 当索引是不存在的值，成功插入；当索引已经存在，则不进行操作
    m.emplace(pair<int, string>(21, "W"));
    m.emplace(pair<int, string>(1, "W"));
 
    map<int, string>::iterator iter;
    for (iter = m.begin(); iter != m.end(); iter++) {
        cout << iter->first << ' ' << iter->second << endl;
    }
}
//1 A
// 2 B
// 3 X
// 21 W
// 22 X
// 23 Y
// 24 Z

以上三种用法，虽然都可以实现数据的插入，但是它们是有区别的:

用insert函数和emplace函数插入数据，在数据的插入上涉及到集合的唯一性这个概念，即当map中有这个关键字时，insert操作是插入数据不了的。

用索引[]方式就不同了，它可以覆盖对应的值。

遍历元素

强烈建议使用迭代器遍历集合！

void search1() {
    map<int, string> m(
            {
                    {1, "A"},
                    {3, "C"},
                    {2, "B"}
            }
    );
 
    map<int, string>::iterator iter;
    for (iter = m.begin(); iter != m.end(); iter++) {
        cout << iter->first << ' ' << iter->second << endl;
    }
}
//1 A
// 2 B
// 3 C

下面介绍一个反面例子，看看直接使用索引去遍历而产生的结果。

void search2() {
    map<int, string> m(
            {
                    {1, "A"},
                    {3, "C"},
                    {5, "B"}
            }
    );
    cout << "遍历前元素的个数：" << m.size() << endl;
    for (int i = 0; i < m.size(); i++) {
        cout << i << ' ' << m[i] << endl;
    }
    cout << "遍历后元素的个数：" << m.size();
 
}
//遍历前元素的个数：3
// 0
// 1 A
// 2
// 3 C
// 4
// 5 B
// 遍历后元素的个数：6

很明显，因为没有判定是否存在而是直接无脑使用，原意是遍历一遍集合，结果却是修改了集合！

删除元素

直接删除元素

可以清空，也可以用迭代器删除指定范围元素或者单个元素。

但是在遍历的时候要注意，使用迭代器删除元素后，迭代器可能会变成类似野指针的存在！

/*
 * 删除有两种方式，
 * clear是直接清空
 * erase是删除指定迭代器范围内的数字
 * 也可以用来删除指定的单个元素
 * */
void del1() {
    map<int, string> m(
            {
                    {1, "A"},
                    {2, "B"},
                    {3, "C"}
            }
    );
    //清空
    m.clear();//{}
    if (m.empty()) {//判断Vector为空则返回true
        m.insert(pair<int, string>(4, "D"));
        m.insert(pair<int, string>(5, "E"));
        m.insert(pair<int, string>(6, "F"));
 
        //用迭代器删除单个元素，注意指针被删除后就失效了
        map<int, string>::iterator iter = m.begin();
        m.erase(iter);//所剩元素{5,E},{6,F}，此时的iter仍然是{4,D}
        cout << "错误的迭代器内容：" << iter->first << ' ' << iter->second << endl;
 
        //删除一个范围， 只保留最后一个
        m.erase(m.begin(), ++m.end()); //{6,F}
 
        //通过关键字索引的数据存在就删除，并返回1；如果关键字索引的数据不存在就不操作，并返回0
        m.erase(2);
 
    }
    map<int, string>::iterator iter;
    for (iter = m.begin(); iter != m.end(); iter++) {
        cout << iter->first << ' ' << iter->second << endl;
    }
}

遍历集合并删除元素

如果想要遍历整个map，并删除所有满足指定数值的应该如下：

/*
 * 遍历集合以删除指定条件的元素
 * */
void del2() {
    map<int, string> m(
            {
                    {1, "A"},
                    {2, "B"},
                    {3, "C"}
            }
    );
    map<int, string>::iterator iter;
 
    // 删除元素后，期望iter指针是继续指向{3,C}的，
    // 但是经过iter++后，竟然又到了上一个元素！
    // 很明显，删除元素后的迭代器变成了类似野指针的存在！
    // for (iter = m.begin(); iter != m.end(); iter++) {
    //     if (iter->first == 2 || iter->second == "B") {
    //         m.erase(iter);
    //     }
    //     cout << iter->first << ' ' << iter->second << endl;
    // }
    //结果是：
    // 1 A
    // 2 B
    // 1 A
    // 3 C
 
    // 正确做法应该是先复制出来一个临时迭代器
    // 接着将原来的迭代器后移一位指向正常的元素
    // 最后用临时迭代器删除指定元素！
    // 第二步和第三步不能反了，否则也会影响到原来正常的迭代器！
    for (iter = m.begin(); iter != m.end();) {
        if (iter->first == 2) {
            map<int, string>::iterator iterTemp = iter;
            ++iter;
            m.erase(iterTemp);
        } else {
            cout << iter->first << ' ' << iter->second << endl;
            ++iter;
        }
    }
    // 结果是
    // 1 A
    // 3 C
}

用迭代器删除元素，先是断言确定迭代器不是尾迭代器，接着将当前迭代器复制到一个新对象，最后返回的就是这个新的迭代器对象。调用_M_erase_aux方法删除迭代器指向的元素，并且节点数目减一。

void _M_erase_aux(const_iterator __position)
    {
      _Link_type __y =
 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
    (const_cast<_Base_ptr>(__position._M_node),
     this->_M_impl._M_header));
      _M_drop_node(__y);
      --_M_impl._M_node_count;
    }

查找函数

count统计元素个数

count函数是用来统计一个元素在当前容器内的个数。由于Map的特性，所以只能返回1或者0。

/*
 * 用count函数寻找元素，
 * */
void find1(set<int> s ){
    if (s.count(4) == 1) {
        cout << "元素4存在"<<endl;
    }
    if (s.count(8) == 0) {
        cout << "元素8不存在";
    }
}

追查源码，我发现他是用的find方法，将结果跟尾迭代器比较，如果不等于尾迭代器就是找到了，返回1；反之就是没找到，返回0。

    find(const _Key& __k) const
    {
      const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
      return (__j == end()
       || _M_impl._M_key_compare(__k,
     _S_key(__j._M_node))) ? end() : __j;
    }

find获取元素迭代器

/*
 * 用find函数寻找元素，
 * */
void find2(set<int> s ){
 
    if (s.find(4)!= s.end() ) {
        cout << "元素4存在"<<endl;
    }else{
        cout << "元素4不存在";
    }
    if (s.find(8)!= s.end() ) {
        cout << "元素8存在"<<endl;
    }else{
        cout << "元素8不存在";
    }
}

而底层是调用的不带const标的find函数，函数体是一样的！而其中的核心逻辑就是用_M_lower_bound函数查找来确定位置。

    _M_lower_bound(_Link_type __x, _Base_ptr __y, const _Key &__k){
        while (__x != 0) {
            if (!_M_impl._M_key_compare(_S_key(__x), __k))
                __y = __x, __x = _S_left(__x);
            else
                __x = _S_right(__x);
        }
        return iterator(__y);
    }

比较函数

key排序

map中默认就是使用key排序的，自动按照key的大小，增序存储，这也是作为key的类型必须能够进行 < 运算比

较的原因。

首先看一眼map模板的定义，重点看下第三个参数： class Compare = less 。

template < class Key， class T， class Compare = less<Key>，
           class Allocator = allocator<pair<const Key，T> > > class map;

与less相对的还有greater，都是STL里面的一个函数对象，那么什么是函数对象呢？

函数对象：即调用操作符的类，其对象常称为函数对象（function object），它们是行为类似函数的对象。表现出一个函数的特征，就是通过“对象名+(参数列表)”的方式使用一个 类，其实质是对operator()操作符的重载。

具体的例子可以去看另一篇文章：Cpp浅析系列-STL之set，这里就不赘述了。

value排序

逻辑上是先转为vector数组，接着将数组用指定的规则重新排序得到排序好的结果。至于是否用排序好的数组去转换为map对象则是看要求了。

bool Special(pair<string, int> a, pair<string, int> b) {
    return a.second < b.second;//从小到大排序
}
 
void specialCompare() {
    // 初始map集合
    map<string, int> m;
    m["a"] = 2;
    m["b"] = 3;
    m["c"] = 1;
 
    // 转为vector集合
    vector<pair<string, int> > demo(m.begin(), m.end());
 
    for (auto it = demo.begin(); it != demo.end(); ++it) {
        cout << (*it).first << " " << (*it).second << endl;
    }
    cout << endl;
 
    // 排序后查看效果
    sort(demo.begin(), demo.end(), Special);
 
    for (auto it = demo.begin(); it != demo.end(); ++it) {
        cout << (*it).first << " " << (*it).second << endl;
    }
    cout << endl;
 
    // 转换为新的map集合，区别就是前后类型反了。
    map<int, string> m2;
    for (vector<pair<string, int> >::iterator it = demo.begin(); it != demo.end(); ++it){
        m2[(*it).second]=(*it).first;
    }
 
    map<int, string>::iterator iter;
    for (iter = m2.begin(); iter != m2.end(); iter++) {
        cout << iter->first << ' ' << iter->second << endl;
    }
}
//a 2
// b 3
// c 1
//
// c 1
// a 2
// b 3
//
// 1 c
// 2 a
// 3 b

感谢

C++中的STL中map用法详解

C++ STL中Map的按Key排序和按Value排序

感谢现在努力的自己。