C++中反向遍历map时怎样删除元素

- 日理万妓 2022-11-12 01:50 451阅读 0赞

### 文章目录 ###

*  前言
 *  map的正向遍历
 *  map 遍历时删除元素
 *  map 的反向遍历
 *  map 反向遍历时删除元素
 *  总结

# 前言 #

今天在解决一个问题 [《5710. 积压订单中的订单总数》][5710.] 时用到了map的反向遍历，看到问题时首先想到了优先队列，但是需要维护一个大根堆和一个小根堆，感觉操作起来比较麻烦，突发奇想使用map就能够解决。map本身就是有序的，正向遍历可以得到从小到大的序列，而反向遍历就可以得到从大到小的序列，这个思路本身没有错，但是解题时卡在了反向遍历时如何删除元素的知识点上，特此记录一下。

# map的正向遍历 #

map的正向遍历是一个基础知识点了，先简单复习一下，不管是用 for 还是 while，只要控制迭代器持续前进就可以了。

map<int, string> mp{ { 1, "A"}, { 2, "E"}, { 3, "I"}, { 4, "O"}, { 6, "U"}};
    
    for (map<int, string>::iterator it = mp.begin(); it != mp.end(); ++it) { 
        cout << it->first << " " << it->second << endl;
    }
    
    /* 输出内容 1 A 2 E 3 I 4 O 6 U */

引入 `auto` 关键字以后，定义表示式的时候会更加方便一点

map<int, string> mp{ { 1, "A"}, { 2, "E"}, { 3, "I"}, { 4, "O"}, { 6, "U"}};
    
    for (auto it = mp.begin(); it != mp.end(); ++it) { 
        cout << it->first << " " << it->second << endl;
    }

引入冒号以后表达式更加简短，要注意的是这里的 `it` 已经不是指针了，而是 `value_type` 类型，所以需要是用 `.` 来访问

map<int, string> mp{ { 1, "A"}, { 2, "E"}, { 3, "I"}, { 4, "O"}, { 6, "U"}};
    
    for (auto it : mp) { 
        cout << it.first << " " << it.second << endl;
    }

引入了结构化绑定声明之后，遍历方式还可以写成下面这样

map<int, string> mp{ { 1, "A"}, { 2, "E"}, { 3, "I"}, { 4, "O"}, { 6, "U"}};
    
    for (auto& [a, b] : mp) { 
        cout << a << " " << b << endl;
    }

# map 遍历时删除元素 #

map 遍历时删除需要注意迭代器失效问题，常用的有下面两种写法

it = mp.erase(it);

或者

mp.erase(it++);

遍历删除时的例子：

map<int, string> mp{ { 1, "A"}, { 2, "E"}, { 3, "I"}, { 4, "O"}, { 6, "U"}};
    
    for (auto it = mp.begin(); it != mp.end();) { 
        if (it->second == "I")
            mp.erase(it++);
        else
            it++;
    }
    
    for (auto it : mp) cout << it.first << " " << it.second << endl;
    
    /* 输出内容 1 A 2 E 4 O 6 U */

# map 的反向遍历 #

map 反向遍历时可以使用 [reverse\_iterator][reverse_iterator] 迭代器，配合 `rbegin()` 和 `rend()` 方法就可以完成反向遍历

map<int, string> mp{ { 1, "A"}, { 2, "E"}, { 3, "I"}, { 4, "O"}, { 6, "U"}};
    
    for (auto it = mp.rbegin(); it != mp.rend(); it++) { 
        cout << it->first << " " << it->second << endl;
    }
    /* 输出内容 6 U 4 O 3 I 2 E 1 A */

# map 反向遍历时删除元素 #

一开始也是用 `erase` 函数来删除元素，但是会报下面的编译错误

error: no matching function for call to ‘std::map<int, std::__cxx11::basic_string<char> >::erase(
        std::reverse_iterator<std::_Rb_tree_iterator<std::pair<const int, std::__cxx11::basic_string<char> > > >)’
        mp.erase(it++);

查询文档发现，`erase` 函数重载只有下面几种实现:

void erase( iterator pos );                                     (until C++11)
    iterator erase( const_iterator pos );                           (since C++11)
    iterator erase( iterator pos );                                 (since C++17)
    
    void erase( iterator first, iterator last );                    (until C++11)
    iterator erase( const_iterator first, const_iterator last );    (since C++11)
    
    size_type erase( const key_type& key );

参数是迭代器的函数并不支持 `reverse_iterator`，需要将 `reverse_iterator` 转化成 `iterator` 才可以，这时就需要用到 `base` 函数，对 `reverse_iterator` 类型的迭代器使用 `base` 函数得到的是上一个元素“原始指针”，这一点比较有意思，具体的解释可以参考 [《std::reverse\_iterator::base》][std_reverse_iterator_base]，这种操作决定了我们遍历删除的写法，应该是先自增再调用 `base` 函数，代码如下；

map<int, string> mp{ { 1, "A"}, { 2, "E"}, { 3, "I"}, { 4, "O"}, { 6, "U"}};
    
    for (auto it = mp.rbegin(); it != mp.rend();) { 
        if (it->second == "I") mp.erase((++it).base());
        else it++;
    }
    
    for (auto it = mp.rbegin(); it != mp.rend(); it++)
        cout << it->first << " " << it->second << endl;
    
    /* 输出内容 6 U 4 O 2 E 1 A */

# 总结 #

*  map 默认会按照 key 排序，是一个常用的有序容器
 *  配合使用 `rbegin()` 和 `rend()` 函数可以完成 map 的反向遍历
 *  对 `reverse_iterator` 类型迭代器使用 `base()` 函数，可以转化成 `iterator` 相关类型，然后进行删除操作

--------------------

[ ==>> 反爬链接，请勿点击，原地爆炸，概不负责！<<== ][_ _]

--------------------

> 搬起砖，我抱不了你，放下砖 … 我尽力！

[5710.]: https://leetcode-cn.com/problems/number-of-orders-in-the-backlog/
[reverse_iterator]: https://en.cppreference.com/w/cpp/iterator/reverse_iterator
[std_reverse_iterator_base]: https://en.cppreference.com/w/cpp/iterator/reverse_iterator/base
[_ _]: https://blog.csdn.net/albertsh/article/details/114806994