当前位置：极客教程 > C++语言 > C++ 问答 > C++ 如何反向遍历 STL map

C++ 如何反向遍历 STL map

C++ 如何反向遍历 STL map

Map 将元素以键的排序顺序存储。现在，如果我们想要反向遍历它，则需要使用 map 的 reverse_iterator。

语法：

map::reverse_iterator iterator_name;

map 的反向迭代器在递增方向上向后移动。因此，我们将把反向迭代器指向 map 的最后一个元素，然后不断递增它，直到它到达第一个元素。为此，我们将使用 std::map 的 2 个成员函数。

1. rbegin()：它返回指向 map 的最后一个元素的反向迭代器。

2. rend()：它返回指向 map 的第一个元素的反向迭代器。

现在，为了反向遍历，我们将使用反向迭代器迭代 rbegin() 和 rend() 之间的范围。

在 map 中进行反向迭代：

示例：
输入：(10, “geeks”), (20, “practice”), (5, “contribute”)
输出：(20, “practice”), (10, “geeks”), (5, “contribute”)

// C++程序构造map以迭代
// 在反向顺序下的元素。
#include 
using namespace std;

int main()
{
    // 创建并初始化 String 和 Int 的 map
    map mymap;

    // 逐个插入元素
    mymap.insert(make_pair(10, "geeks"));
    mymap.insert(make_pair(20, "practice"));
    mymap.insert(make_pair(5, "contribute"));

    // 创建 map 的反向迭代器
    map::reverse_iterator it;

    // rbegin() 返回 map 的最后一个值
    for (it = mymap.rbegin(); it != mymap.rend(); it++) {
        cout << "(" << it->first << ", "
             << it->second << ")" << endl;
    }

    return 0;
}

输出：

(20, practice)
(10, geeks)
(5, contribute)

我们还可以使用 auto 来避免记住复杂的语法。

// C++ 程序使用更简单的语法反向迭代map。
#include 
using namespace std;

int main()
{
    // 创建并初始化 String 和 Int 的 map
    map mymap;

    // 逐个插入元素
    mymap.insert(make_pair(10, "geeks"));
    mymap.insert(make_pair(20, "practice"));
    mymap.insert(make_pair(5, "contribute"));

    // rbegin() 返回 map 的最后一个值
    for (auto it = mymap.rbegin(); it != mymap.rend(); it++) {
        cout << "(" << it->first << ", "
             << it->second << ")" << endl;
    }

    return 0;
}

输出：

(20, practice)
(10, geeks)
(5, contribute)

有关复杂度分析，请参见 end。

使用 map 的 key_type 范围进行反向迭代：

另一种反向遍历 map 的方法是使用 map 的 key_type 范围，并以反向顺序遍历键。

示例：

输入：(15, "Geeks"), (25, "GFG"), (10, "GeeksForGeeks")
输出：(25, "GFG"), (15, "Geeks"), (10, "GeeksForGeeks")

下面是实现代码：

// C++程序创建一个映射，以迭代
//元素的反向顺序
//使用map的键类型 range
#include 
using namespace std;

int main()
{
    // 创建和初始化一个Ints和Strings的map
    map mymap;

    //逐个插入元素
    mymap.insert(make_pair(15, "Geeks"));
    mymap.insert(make_pair(25, "GFG"));
    mymap.insert(make_pair(10, "GeeksForGeeks"));

    //以相反顺序打印map的内容
    for (auto it = mymap.rbegin()->first;
        it >= mymap.begin()->first; --it) {
        if (mymap.count(it))
            cout << "(" << it << ", " << mymap[it] << ")"
                 << endl;
    }
    return 0;
}

输出

(25，GFG)
（15，Geeks）
（10，GeeksForGeeks）

请参阅复杂性分析的结尾。

在multimap中进行反向迭代：

Multimap类似于map，但添加了多个元素可以具有相同的键。 在这种情况下，键值和映射值对必须是唯一的，而不是每个元素都是唯一的。

例子:

输入：（10，“geeks”），（20，“practice”），（5，“contribute”），
         （20，“van”），（20，“watch”），（5，“joker”）
输出：（20，“watch”），（20，“van”），（20，“practice”），
         （10，“geeks”），（5，“joker”），（5，“contribute”）

// C++程序创建一个multimap以存储
//元素按降序排列。
# include
using namespace std;

int main()
{

    //创建和初始化Ints和String的multimap
    multimap mymap;

    //逐个插入元素
    mymap.insert(make_pair(10, "geeks"));
    mymap.insert(make_pair(20, "practice"));
    mymap.insert(make_pair(5, "contribute"));

    //允许重复
    mymap.insert(make_pair(20, "van"));

    mymap.insert(make_pair(20, "watch"));
    mymap.insert(make_pair(5, "joker"));

    for (auto it = mymap.rbegin(); it != mymap.rend(); it++) {
        cout << "(" << it->first << ", "
            << it->second << ")" << endl;
    }

    return 0;
}

输出：

(20，“watch”)
（20，“van”）
（20，“practice”）
（10，“geeks”）
（5，“joker”）
（5，“contribute”）

请参阅复杂性分析的结尾。

在不使用rbegin()或rend()函数的情况下，对映射进行反向迭代：

我们可以使用普通的 begin() 和 end() 函数以相反的顺序迭代映射。
例子:

输入：（15，“Geeks”），（25，“GFG”），（10，“GeeksForGeeks”）
输出：（25，“GFG”），（15，“Geeks”），（10，“GeeksForGeeks”）

以下是实现方式:

// C++程序，制作一个映射以倒序迭代元素，
// 不使用map.rbegin()和map.rend()函数
# include <bits/stdc++.h>
using namespace std;
 
int main()
{
    // 创建和初始化一个Ints和Strings的map
    map<int, string> mymap;
 
    // 逐个插入元素
    mymap.insert(make_pair(15, "Geeks"));
    mymap.insert(make_pair(25, "GFG"));
    mymap.insert(make_pair(10, "GeeksForGeeks"));
 
    // 将迭代器it设置为end()，返回结果为map的最后一个值
    auto it = mymap.end();
    it--;
 
    // 倒序打印map的内容
    while (it != mymap.begin()) {
        cout << "(" << it->first << ", " << it->second
             << ")" << endl;
        it--;
        if (it == mymap.begin())
            cout << "(" << it->first << ", " << it->second
                 << ")" << endl;
    }
    return 0; 
}

输出

(25, GFG)
(15, Geeks)
(10, GeeksForGeeks)

参见复杂分析终点。

使用向量在map中进行翻转迭代：

我们可以创建一个具有map中所有元素的向量，然后使用std::reverse算法来翻转向量中的元素顺序，然后通过向量迭代访问倒序元素。

输入:  (15, "Geeks"), (25, "GFG"),  (10, "GeeksForGeeks")
输出 : (25, "GFG"),  (15, "Geeks"), (10, "GeeksForGeeks")

以下是实现方式：

// C++程序，创建一个映射，使用向量迭代倒序元素
 
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    // 创建和初始化一个Ints和Strings的map
    map<int, string> mymap;
 
    // 逐个插入元素
    mymap.insert(make_pair(15, "Geeks"));
    mymap.insert(make_pair(25, "GFG"));
    mymap.insert(make_pair(10, "GeeksForGeeks"));
 
    //创建一个具有map中所有元素的向量
    vector<pair<int, string> > v(mymap.begin(), mymap.end());
 
    //翻转向量中的元素
    reverse(v.begin(), v.end());
 
    //通过向量迭代访问倒序元素
      for (auto it : v) {
        cout << "(" << it.first << ", " << it.second << ")" << endl;
    }
    return 0; 
}

输出

(25, GFG)
(15, Geeks)
(10, GeeksForGeeks)

参见复杂分析终点。

使用cbegin()和cend()在map中进行翻转迭代：

cend()和cbegin()是C++标准模板库中map容器的成员函数。cbegin()返回指向容器中第一个元素的迭代器，而cend()返回指向容器中最后一个元素后面的位置的迭代器。通过使用这些函数，我们可以倒序遍历map的元素。

输入: (15, “Geeks”), (25, “GFG”), (10, “GeeksForGeeks”)
输出: (25, “GFG”), (15, “Geeks”), (10, “GeeksForGeeks”)

以下是实现方式：

// C++程序实现了一个使用cbegin()和cend()函数
// 遍历地图以逆序方式迭代元素
 
# include <iostream>
# include <map>
 
using namespace std;
 
int main()
{
    // 创建并初始化一张整数和字符串的地图
    map<int, string> my_map;
 
    // 逐个插入元素
    my_map.insert(make_pair(15, "Geeks"));
    my_map.insert(make_pair(25, "GFG"));
    my_map.insert(make_pair(10, "GeeksForGeeks"));
 
    // 逆序遍历地图
    for (auto it = my_map.cend(); it != my_map.cbegin();
         it--) {
        auto itr = it;
        itr--;
        cout << itr->first << " -> " << itr->second << endl;
    }
 
    return 0;
}

输出

25 -> GFG
15 -> Geeks
10 -> GeeksForGeeks

复杂度分析见下文。

使用crbegin()和crend()在映射中进行反向迭代：

crbegin()和crend()是C++标准模板库中映射容器的成员函数。它们返回常量迭代器，分别指向容器的最后一个元素和第一个元素。通过使用这些函数，我们可以以反向顺序遍历映射的元素。
输入：(15, “Geeks”), (25, “GFG”), (10, “GeeksForGeeks”)
输出：(25, “GFG”), (15, “Geeks”), (10, “GeeksForGeeks”)

下面是实现方式：

// C++程序实现了一个使用crbegin()和crend()函数
// 以逆序方式遍历地图迭代元素
 
#include <iostream>
#include <map>
 
using namespace std;
 
int main()
{
    // 创建并初始化一张整数和字符串的地图
    map<int, string> my_map;
 
    // 逐个插入元素
    my_map.insert(make_pair(15, "Geeks"));
    my_map.insert(make_pair(25, "GFG"));
    my_map.insert(make_pair(10, "GeeksForGeeks"));
 
    // 以反向迭代器遍历地图
    for (auto it = my_map.crbegin(); it != my_map.crend();
         ++it) {
        cout << it->first << " -> " << it->second << endl;
    }
 
    return 0;
}

输出

25 -> GFG
15 -> Geeks
10 -> GeeksForGeeks

复杂度分析见下文。

复杂度分析：

方法 时间复杂度 辅助空间
在映射中使用反向迭代 O(N) O(1)
使用map的key_type Range O(N) O(1)
在multimap中 O(N) O(1)
不使用rbegin()或rend()函数 O(N) O(1)
使用vector O(N) O(N)
使用cbegin()和cend() O(N) O(1)
使用crbegin()和crend() O(N) O(1)

Python教程

Python 教程

Python 教程
Tkinter 教程

Tkinter 教程
Pandas 教程

Pandas 教程
NumPy 教程

NumPy 教程
Flask 教程

Flask 教程
Django 教程

Django 教程
PySpark 教程

PySpark 教程
wxPython 教程

wxPython 教程
SymPy 教程

SymPy 教程
Seaborn 教程

Seaborn 教程
SciPy 教程

SciPy 教程
RxPY 教程

RxPY 教程
Pycharm 教程

Pycharm 教程
Pygame 教程

Pygame 教程
PyGTK 教程

PyGTK 教程
PyQt 教程

PyQt 教程
PyQt5 教程

PyQt5 教程
PyTorch 教程

PyTorch 教程
Matplotlib 教程

Matplotlib 教程
Web2py 教程

Web2py 教程
BeautifulSoup 教程

BeautifulSoup 教程

Java教程

Java 教程

Java 教程

Web教程

HTML 教程

HTML 教程
CSS 教程

CSS 教程
CSS3 教程

CSS3 教程
jQuery 教程

jQuery 教程
Ajax 教程

Ajax 教程
AngularJS 教程

AngularJS 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程
Laravel 教程

Laravel 教程
Next.js 教程

Next.js 教程
PhantomJS 教程

PhantomJS 教程
Three.js 教程

Three.js 教程
Underscore.JS 教程

Underscore.JS 教程
WebGL 教程

WebGL 教程
WebRTC 教程

WebRTC 教程
VueJS 教程

VueJS 教程

数据库教程

SQL 教程

SQL 教程
MySQL 教程

MySQL 教程
MongoDB 教程

MongoDB 教程
PostgreSQL 教程

PostgreSQL 教程
SQLite 教程

SQLite 教程
Redis 教程

Redis 教程
MariaDB 教程

MariaDB 教程

图形图像教程

Vulkan 教程

Vulkan 教程
OpenCV 教程

OpenCV 教程

大数据教程

R语言 教程

R语言 教程

开发工具教程

Git 教程

Git 教程
VSCode 教程

VSCode 教程
Docker 教程

Docker 教程
Gerrit 教程

Gerrit 教程
Excel 教程

Excel 教程

计算机教程

Go语言 教程

Go语言 教程
C++ 教程

C++ 教程

C++ 精品教程