编程技术开发和娱乐网址导航

网站首页 > 技术文章 正文

Cpp浅析系列-STL之map stl中map

luoxia7 2024-10-13 06:46:58 技术文章 1 ℃ 0 评论

前言

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<Key>

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排序

感谢现在努力的自己。

Tags:

本文暂时没有评论,来添加一个吧(●'◡'●)

欢迎 发表评论:

最近发表
标签列表