Why Was Pair Range Access Removed from C++11

Why was pair range access removed from C++11?

I think the 2009 paper "Pairs do not make good ranges" by Alisdair Meredith is at least part of the answer. Basically, many algorithms return pairs of iterators that are actually not guaranteed to be valid ranges. It seems they removed the support for pair<iterator,iterator> from the for-range loop for this reason. However, the proposed solution has not been fully adopted.

If you know for certain that some pair of iterators really represents a valid range then you could wrap them into a custom type which offers begin()/end() member functions:

template<class Iter>
struct iter_pair_range : std::pair<Iter,Iter> {
    iter_pair_range(std::pair<Iter,Iter> const& x)
    : std::pair<Iter,Iter>(x)
    {}
    Iter begin() const {return this->first;}
    Iter end()   const {return this->second;}
};

template<class Iter>
inline iter_pair_range<Iter> as_range(std::pair<Iter,Iter> const& x)
{ return iter_pair_range<Iter>(x); }

int main() {
    multimap<int,int> mm;
    ...
    for (auto& p : as_range(mm.equal_range(42))) {
       ...
    }
}

(untested)

I agree this is a bit of a wart. Functions which return valid ranges (like equal_range) should say so using an appropriate return type. It's a bit embarrasing that we have to manually confirm this via something like as_range above.

Can range based for loop work over a range

As per Why was pair range access removed from C++11? you can use an adaptor e.g. the as_range at the accepted answer, boost::make_iterator_range, or write your own:

template<typename It> struct range {
   It begin_, end_;
   It begin() const { return begin_; }
   It end() const { return end_; }
};
template<typename It> range<It> as_range(const std::pair<It, It> &p) {
   return {p.first, p.second};
}

auto rng = std::equal_range(v.begin(),v.end(),1984);
for(const auto& elem: as_range(rng))
    ...

The reason this isn't applicable in general is that per Alastair Meredith's paper, of the algorithms,

• mismatch and partition_copy return a pair of iterators from different ranges;
• minmax returns a pair of objects that may not be iterators at all, and if they are there's no guarantee they form a range;
• minmax_element can return a range, but it can also return a reversed range (e.g. on a reverse-sorted range minmax_element will return {prev(last), first};
• equal_range is guaranteed to return a range.

std::multimap equal _range and C++20 std::views::values do not work nicely together

The problem is that equal_range returns a pair<It, It>, which is (unfortunately) not itself a range. This is one of the more unfortunate legacy API decisions in my opinion - since we have this excellent name but it does something... less than great.

You used to be able to take a pair<It, It> and easily convert it to a subrange, but that's not necessarily valid and was removed (first in LWG3281 and then the rest in LWG3404). Not all pairs of iterators are actually ranges (several algorithms return two iterators that are not - like minmax_element or mismatch).

But that's okay, we can just write our own explicit one:

struct pair_to_range_t {
    template <typename I>
    friend constexpr auto operator|(std::pair<I, I> const& pr, pair_to_range_t) {
        return std::ranges::subrange(pr.first, pr.second);
    }
};

inline constexpr pair_to_range_t pair_to_range{};

And then you can write:

oddness.equal_range(true) | pair_to_range | std::views::values;

What is member interpretation in Range-based for loop (since C++11)?

The "member interpretation" refers to begin_expr and end_expr using members of the iterated type in contrast to using plain offsets for arrays or begin and end free functions.

The array interpretation is off the table, because it is only used for arrays. Next consider that there is std::begin and std::end:

Custom overloads of begin may be provided for classes and enumerations that do not expose a suitable begin() member function, yet can be iterated.

Now consider this example:

#include <iostream>
#include <vector>

class meow { 
    enum { begin = 1, end = 2}; 
    public:
    std::vector<int> data;
};

// non-const iterators
auto begin(meow& m){ return m.data.begin(); }
auto end(meow& m) { return m.data.end(); }
// const iterators
auto begin(const meow& m){ return m.data.begin(); }
auto end(const meow& m) { return m.data.end(); }

int main() {
    meow m;
    for (const auto& e : m) {}
}

We want to iterate the meows data. But it does not work. The member interpratation is choosen, even though meow::begin and mewo::end are private and the begin and end functions could be used. Hence the error:

<source>: In function 'int main()':
<source>:17:26: error: 'meow::<unnamed enum> begin' is private within this context
     for (const auto& e : m) {}
                          ^
<source>:5:12: note: declared private here
     enum { begin = 1, end = 2};
            ^~~~~
<source>:17:26: error: 'begin' cannot be used as a function
     for (const auto& e : m) {}
                          ^
<source>:17:26: error: 'meow::<unnamed enum> end' is private within this context
<source>:5:23: note: declared private here
     enum { begin = 1, end = 2};
                       ^~~
<source>:17:26: error: 'end' cannot be used as a function
     for (const auto& e : m) {}
                          ^

The example works fine when we remove the private enum:

#include <iostream>
#include <vector>

class meow { 
    //enum { begin = 1, end = 2}; 
    public:
    std::vector<int> data;
};

// non-const iterators
auto begin(meow& m){ return m.data.begin(); }
auto end(meow& m) { return m.data.end(); }
// const iterators
auto begin(const meow& m){ return m.data.begin(); }
auto end(const meow& m) { return m.data.end(); }

int main() {
    meow m;
    for (const auto& e : m) {}
}

Live Demo

Range-based for statement definition redundancy

This avoids a corner-case with ADL:

namespace other {
  struct T {};
  int begin(T*) { return 42; }
}

other::T a[3];
for (auto v : a) {}

Because ADL finds other::begin when calling begin(a), the equivalent code would break causing a confusing compile error (along the lines of "can't compare int to other::T*" as end(a) would return a T*) or different behavior (if other::end was defined and did something likewise unexpected).

Range based for with pairIterator,Iterator

In a range-based for loop, name lookup for non-member begin() and end() uses ADL only. It doesn't perform ordinary unqualified lookup. §6.5.4 [stmt.ranged]/p1.3:

• if _RangeT is a class type, the unqualified-ids begin and end are looked up in the scope of class _RangeT as if by class member access
  lookup (3.4.5), and if either (or both) finds at least one
  declaration, [...]

• otherwise, begin-expr and end-expr are begin(__range) and
  end(__range), respectively, where begin and end are looked up in the
  associated namespaces (3.4.2). [ Note: Ordinary unqualified lookup
  (3.4.1) is not performed. —end note ]

Hence, your begin() and end() overloads are not found.

Finding pair values in a given range

As you need to handle three cases - starting, happening or ending in the given range, we can split it into three parts.

1. starting: v1 lies in [L,R].
2. ending: v2 lies in [L,R].

The third case can be formulated as v1 <= R and L <= v2, but the first two cases partially cover this case, so we will use different formulation to avoid collisions:

3. happening: v1 < L and R < v2

Well, it is easy to handle the first case in logarithmic plus number of reported events time if we can sort the array of events by v1. The same trick works for the second case.

The third case is trickier. Let's draw:

The pink area represents all intervals L <= R. The red dot is an interval and greenish area represents all possible events we want to capture. To do such a capture one can use k2-tree.

STL algorithms: Why no additional interface for containers (additional to iterator pairs)?

They do introduce ambiguity for many algorithms. A lot of <algorithm> looks like

template<class iterator>
void do_something(iterator, iterator);

template<class iterator, class funct>
void do_something(iterator, iterator, funct);

If you add additional overloads

template<class container, class funct>
void do_something(container, funct);

the compiler will have some trouble figuring out what do_something(x, y) means. If x and y are of the same type, it will match both iterator = type and container = type, funct = type.^*)

C++11 tried to solve this with "concepts" that could recognize the difference between a container and an iterator. However, these "concepts" turned out to be too complicated to make it into the standard, so neither did these overloads.

^*) compilers disagree here, the Comeau compiler claims that it is ambiguous, g++ 4.5 and MSVC 10 calls the first function.

---

After an extremely long discussion in the comments, here is one example where it doesn't work as expected - using a container adapter that can also double as a predicate.

#include <iostream>
#include <vector>

template<class iterator>
void test(iterator, iterator)
{
   std::cout << "test iterator\n";
}

template<class iterator, class predicate>
void test(iterator, iterator, predicate)
{
   std::cout << "test iterator, predicate\n";
}

template<class container, class predicate>
void test(const container& cont, predicate compare)
{
   std::cout << "test container, predicate\n";

   test(cont.begin(), cont.end(), compare);
}

template<class container>
class adapter
{
public:
   typedef typename container::iterator   iterator;

   adapter(container* cont) : cont(cont)
   { }

   iterator begin() const
   { return cont->begin(); }

   iterator end() const
   { return cont->end(); }

   bool operator()(const iterator& one, const iterator& two)
   { return *one < *two; }

private:
   container* cont;
};

int main()
{
   std::vector<int>   v;

   adapter<std::vector<int>>   a(&v);

   test(a, a);

}

Output:

test iterator

http://ideone.com/wps2tZ

---

Related Topics