Iterating over a container bidirectionally

Question

Is there a better way than the below code, to iterate over a container in either direction, using the same iterators?

#include <iostream>
#include <map>

int main()
{
    const bool descend = false;

    std::map<int, int> mapp;
    mapp[1] = 1;
    mapp[2] = 2;
    mapp[3] = 3;
    mapp[4] = 4;

    std::map<int, int>::iterator startIter = descend ? --(mapp.end()) : mapp.begin();
    std::map<int, int>::iterator endIter = descend ? --(mapp.begin()) : mapp.end();

    while (startIter != endIter)
    {
        std::cout << startIter->first << std::endl;
        descend ? --startIter : ++startIter;
    }
}

Any working way would be better as this is UB: `--(mapp.begin())` — Slava, Aug 09 '18 at 17:50
@Slava Is it really? What would `rend` point to if not one before the beginning? — NathanOliver, Aug 09 '18 at 17:52
@NathanOliver `rend()` whould be reverse iterator created from `begin()` the same way `rbegin()` is created from `end()` not `end() - 1` — Slava, Aug 09 '18 at 17:56
@Slava `rbegin` is `end() - 1`. If it was `end()` then `*container.rbegin();` would be illegal. — NathanOliver, Aug 09 '18 at 17:58
@NathanOliver no you are wrong - https://en.cppreference.com/w/cpp/iterator/reverse_iterator/operator* "Returns a reference or pointer to the element **previous** to current." — Slava, Aug 09 '18 at 17:59
In general reverse iterators would not work with C array if they would be implemented the way you described, as pointer behind last element is valid, one before first is not. — Slava, Aug 09 '18 at 18:02

JeJo · Answer 1 · 2018-08-10T16:53:09.560

2

Is there a better way than the below code, to iterate over a container in either direction, using the same iterators?

Yes. Use std::map::reverse_iterator. It will be a better way than the code you posted, but that will not be using the same iterators anymore, which was one of your requirements.

However, this will be less error-prone than the code you have written. In addition to that, you do not need to re-invent the wheel, if that is already in C++.

See output here

#include <iostream>
#include <map>

template<typename Iterator>
void print(const Iterator Begin, const Iterator End)
{
    for(Iterator iter = Begin; iter != End; ++iter)
       std::cout << iter->first << "\n";
}

int main()
{
    const bool descend = true;

    std::map<int, int> mapp;
    mapp[1] = 1;
    mapp[2] = 2;
    mapp[3] = 3;
    mapp[4] = 4;

    descend ?
        print(mapp.crbegin(), mapp.crend()):
        print(mapp.cbegin(), mapp.cend());
    return 0;
}

The image from cppreference.com will explain graphically, how does it work.

edited Aug 10 '18 at 16:53

answered Aug 09 '18 at 18:05

JeJo

30,635
6
49
88

1

This code does not satisfy OP's requirement "using **the same** iterators" – Slava Aug 09 '18 at 21:04
@Slava True. I didn't think about making it, rather wanna show an alternative, which lacks OPs requirement. Well, now he has the correct answer(from you) and an alternative(from me) ;) – JeJo Aug 10 '18 at 16:48
Is there a way to extend this so that I can erase the iterator within the loop and continue looping? The problem is the code required is different because erase() is for forward iterators, therefore getting compiler errors due to the templating. – user997112 Aug 13 '18 at 15:15
@user997112 True. You need to pass the `std::map` to the template then, because `std::map::erse` need to know the map. Iterators will not work. The best solutions what I found are: [remove_if equivalent for std::map](https://stackoverflow.com/questions/800955/remove-if-equivalent-for-stdmap) and [How to call erase with a reverse iterator](https://stackoverflow.com/questions/1830158/how-to-call-erase-with-a-reverse-iterator) – JeJo Aug 13 '18 at 18:06
@JeJo your first link doesn't reference reverse iterators and your second link doesn't reference forward iterators, hence my current problem :) – user997112 Aug 14 '18 at 14:11
@JeJo this one also shows erase on reverse iterators using a different approach https://stackoverflow.com/questions/37005449/how-to-call-erase-with-a-reverse-iterator-using-a-for-loop – user997112 Aug 14 '18 at 14:14

score 2 · Accepted Answer · answered Aug 09 '18 at 18:16

Your code is invalid as this statement --(mapp.begin()) leads to UB. I would write a thin wrapper:

template<class Iter, class F>
void apply( Iter begin, Iter end, F f, bool forward )
{
    while( begin != end ) 
        f( forward ? *begin++ : *--end );
}

live example

or just simply rewrite your loop into:

auto begin = mapp.begin();
auto end = mapp.end();
while ( begin != end)
{
    const auto &p = forward ? *begin++ : *--end;
    std::cout << p.first << std::endl;
}

score -1 · Answer 3 · edited Aug 09 '18 at 21:49

Write self-documenting code and it becomes simple. Break that loop out into its own function and call it with the appropriate iterators.

This is why we have "reverse iterators" they can be used to go backwards through a container by using the normal forward semantics.

#include <iostream>
#include <map>

template<typename I>
void printMapContainer(I begin, I end)
{
    for (;begin != end; ++begin)
    {
        std::cout << begin->first << "\n";
    }
}
int main()
{
    const bool descend = false;

    std::map<int, int> mapp;
    mapp[1] = 1;
    mapp[2] = 2;
    mapp[3] = 3;
    mapp[4] = 4;

    if (descend) {
        printMapContainer(mapp.rbegin(), mapp.rend());
    }
    else {
        printMapContainer(mapp.begin(), mapp.end());
    }
}

Iterating over a container bidirectionally

3 Answers3

Linked