Iterate over a Map in Reverse Order in C++

In this article, we will discuss different ways to iterate over a map in reverse order.

Introduction

Map store the elements in sorted order of keys. For example, if you store following elements in map i.e.

{"aaa", 10},
{"ddd", 11},
{"bbb", 12},
{"ccc", 13}

It will internally store the elements in sorted order of keys i.e.

{"aaa", 10},
{"bbb", 12},
{"ccc", 13},
{"ddd", 11},

Iterating over a map will result in above order i.e. sorted order of keys. Now what if we want to iterate a map in reverse direction ? Let’s see two different ways to do that

Using Range Library from C++20

To loop over a map in reverse order, we can leverage the std::ranges::views::reverse to create a reversed view of map and then we can iterate over it using structural bindings in a for-loop. During iteration, we can key & value from each pair in the map. For if you are using a range based for-loop the you car directly use the std::views::reverse for same.

Checkout complete example

#include <iostream>
#include <map>
#include <ranges>

int main()
{

    // Creating & Initializing a map of String & Ints
    std::map<std::string, int> wordFreq = {
        {"aaa", 10},
        {"ddd", 11},
        {"bbb", 12},
        {"ccc", 13}};

    // Loop over key-value pairs in map using reverse view
    for (const auto &[key, value] : wordFreq | std::views::reverse)
    {
        std::cout << key << ": " << value << std::endl;
    }

    return 0;
}

To compile the above code on linux. Use following command,

g++-10 --std=c++20 reverse.cpp

Using Reverse Iterator

To Iterate a map in reverse order we will use reverse_iterator of map i.e.

Reverse Iterator

std::map<std::string, int>::reverse_iterator it = wordFreq.rbegin();

Reverse Iterator of map moves in backward direction on increment. So, we will point the reverse_iterator to the last element of map and then keep on incrementing it until it reaches the first element. To do this we will use two member functions of std::map i.e.

std::map::rbegin()

reverse_iterator rbegin();

It returns the reverse_iterator pointing to last element of map.

std::map::rend()

reverse_iterator rend();

It returns the reverse_iterator pointing to first element of map.

Now, to loop back in reverse direction on a map. Iterate over the range b/w rbegin() & rend() using reverse_iterator.

Checkout complete example as follows,

#include <iostream>
#include <map>
#include <string>
#include <iterator>

int main() {

	// Creating & Initializing a map of String & Ints
	std::map<std::string, int> wordFreq = {
                                        { "aaa", 10 },
                                        { "ddd", 11 },
                                        { "bbb", 12 },
                                        { "ccc", 13 } };

	// Create a map iterator and point to the end of map
	std::map<std::string, int>::reverse_iterator it = wordFreq.rbegin();

	// Iterate over the map using Iterator till beginning.
	while (it != wordFreq.rend()) {

        std::cout << it->first
                  << " :: "
                  << it->second
                  << std::endl;

		// Increment the Iterator to point to next entry
		it++;
	}

	return 0;
}

Output:

ddd :: 11
ccc :: 13
bbb :: 12
aaa :: 10

Summary

We learned about two ways to iterate over a map in reverse order in C++.

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Scroll to Top