Loop over all (unordered) pairs of elements in a vector

Question

I have a std::vector of some data (Points in my case) and I want to loop over all distinct pairs of elements. The order of the pair is not important (as I am only interested in the distance of the points). With a classic for loop what I would want to do would be something like:

std::vector<double> vec{-1., 3., 5., -8., 123., ...};

for (std::vector<double>::size_type first = 0; first < vec.size(); ++first) {
    for (std::vector<double>::size_type second = first+1; second < vec.size();
         ++second) {
        // Compute something using std::fabs(vec.at(first)-vec.at(second))
    }
}

My question is now if one can achieve this more elegantly using range based loops.

Answer 1

I wouldn't attempt to coerce it into a range based loop (since contriving the start of the inner loop will be tricky), but I would work directly with the iterators to clarify the loop body and to make the code less dependent on the specific container you're using:

for (auto first = vec.begin(); first != vec.end(); ++first){
    for (auto second = first + 1; second != vec.end(); ++second){
        // Your vec.at(first) is now simply *first.    
    }
}

Note that first + 1 is always valid since first is never vec.end() when first + 1 is evaluated.

std::vector::at is also required by the C++ standard to check that the supplied index is in the bounds of the vector (and throw a std::out_of_range exception if it isn't within the bounds), which is an unnecessary overhead in your case.

Answer 2

I provide this answer only because OP want a way of doing that with range based for loops. It isn't more elegant than ordinary loops.

If your vector doesn't have duplicate numbers you can use reverse iteration instead of beginning from a specific point in the second loop, so that you can use range based for in your iterations.

for reverse iteration by range based for loops you want an adapter class.

template <typename It>
class reverse_adapter
{
public:
    reverse_adapter(It rbegin, It rend)
        : _rbegin(rbegin), _rend(rend)
    {}

    It begin() const { return _rbegin; }

    It end() const { return _rend; }

private:
    It _rbegin;
    It _rend;
};

template<typename Container>
reverse_adapter<typename Container::reverse_iterator> make_reverse(Container& container)
{
    reverse_adapter<typename Container::reverse_iterator> adapter(std::rbegin(container), std::rend(container));
    return adapter;
}

And use this adapter for reverse iteration in second loop.

for(auto val : vec)
{
    for (auto second_val : make_reverse(vec)) // Start from last to current item in first loop
    {
        if (val == second_val) break; // Instead of first + 1 in second loop

        auto dif = val - second_val;
    }
}