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)