Range-based for with brace-initializer over non-const values?

Question

I am trying to iterate over a number of std::lists, sorting each of them. This is the naive approach:

#include<list>
using namespace std;
int main(void){
    list<int> a,b,c;
    for(auto& l:{a,b,c}) l.sort();
}

producing

aa.cpp:5:25: error: no matching member function for call to 'sort'
        for(auto& l:{a,b,c}) l.sort();
                             ~~^~~~
/usr/bin/../lib64/gcc/x86_64-linux-gnu/4.9/../../../../include/c++/4.9/bits/stl_list.h:1586:7: note: 
      candidate function not viable: 'this' argument has type 'const
      std::list<int, std::allocator<int> >', but method is not marked const
      sort();
      ^
/usr/bin/../lib64/gcc/x86_64-linux-gnu/4.9/../../../../include/c++/4.9/bits/stl_list.h:1596:9: note: 
      candidate function template not viable: requires 1 argument, but 0 were
      provided
        sort(_StrictWeakOrdering);
        ^
1 error generated.

Am I correctly guessing that brace-initializer is creating copy of those lists? And is there a way to not copy them, and make them modifiable inside the loop? (other than making list of pointers to them, which is my current workaround).

Answer 1

You are guessing correctly. std::initializer_list elements are always const (which makes sort()ing them impossible, as sort() is a non-const member function) and its elements are always copied (which would make sort()-ing them meaningless even if they weren't const). From [dcl.init.list], emphasis mine:

An object of type std::initializer_list<E> is constructed from an initializer list as if the implementation allocated a temporary array of N elements of type const E, where N is the number of elements in the initializer list. Each element of that array is copy-initialized with the corresponding element of the initializer list, and the std::initializer_list<E> object is constructed to refer to that array. [ Note: A constructor or conversion function selected for the copy shall be accessible (Clause 11) in the context of the initializer list. —end note ] If a narrowing conversion is required to initialize any of the elements, the program is ill-formed. [ Example:

struct X {
    X(std::initializer_list<double> v);
};
X x{ 1,2,3 };

The initialization will be implemented in a way roughly equivalent to this:

const double __a[3] = {double{1}, double{2}, double{3}};
X x(std::initializer_list<double>(__a, __a+3));

assuming that the implementation can construct an initializer_list object with a pair of pointers. —end example ]

There is no way to make them non-const or non-copied. The pointer solution works:

for (auto l : {&a, &b, &c}) l->sort();

because it's the pointer that's const, not the element it's pointing to. The other alternative would be to write a variadic function template:

template <typename... Lists>
void sortAll(Lists&&... lists) {
    // before C++17
    using expander = int[];
    expander{0, (void(lists.sort()), 0)...};

    // C++17 or later
    (lists.sort(), ...);
}

sortAll(a, b, c);

You could also, I guess, write a helper to wrap your lists into an array of reference_wrapper to list<int> (since you can't have an array of references), but this is probably more confusing than helpful:

template <typename List, typename... Lists>
std::array<std::reference_wrapper<List>, sizeof...(Lists) + 1>
as_array(List& x, Lists&... xs) {
    return {x, xs...}; 
}

for (list<int>& l : as_array(a, b, c)) {  // can't use auto, that deduces
    l.sort();                             // reference_wrapper<list<int>>,
}                                         // so would need l.get().sort()

Answer 2

It is possible to write a function ref_range which allows you to do this:

for(auto& l : ref_range(a,b,c)) {
    l.sort();
}

As others have said, once you write {a,b,c} you are stuck with an initializer_list, and such a list always takes copies of its arguments. The copies are const (hence your error), but even if you could get a non-const reference you would be modifying the copies of a, b and c instead of the originals.

Anyway, here is ref_range. It builds a vector of reference_wrapper.

// http://stackoverflow.com/questions/31724863/range-based-for-with-brace-initializer-over-non-const-values
#include<list>
#include<functional>
#include<array>

template<typename T, std:: size_t N>
struct hold_array_of_refs {
    using vec_type = std:: array< std:: reference_wrapper<T>, N >;
    vec_type m_v_of_refs;
    hold_array_of_refs(vec_type && v_of_refs) : m_v_of_refs(std::move(v_of_refs)) { }
    ~hold_array_of_refs() { }
    struct iterator {
        typename vec_type :: const_iterator m_it;
        iterator(typename vec_type :: const_iterator it) : m_it(it) {}
        bool operator != (const iterator &other) {
            return this->m_it != other.m_it;
        }
        iterator& operator++() { // prefix
            ++ this->m_it;
            return *this;
        }
        T& operator*() {
            return *m_it;
        }
    };

    iterator begin() const {
        return iterator(m_v_of_refs.begin());
    }
    iterator end() const {
        return iterator(m_v_of_refs.end());
    }
};

template<typename... Ts>
using getFirstTypeOfPack = typename std::tuple_element<0, std::tuple<Ts...>>::type;


template<typename ...T>
auto ref_range(T&... args) -> hold_array_of_refs< getFirstTypeOfPack<T...> , sizeof...(args)> {
    return {{{ std:: ref(args)... }}}; // Why does clang prefer three levels of {} ?
}

#include<iostream>
int main(void){
    std:: list<int> a,b,c;
    // print the addresses, so we can verify we're dealing
    // with the same objects
    std:: cout << &a << std:: endl;
    std:: cout << &b << std:: endl;
    std:: cout << &c << std:: endl;
    for(auto& l : ref_range(a,b,c)) {
        std:: cout << &l << std:: endl;
        l.sort();
    }
}

Answer 3

The {...} syntax is actually creating an std::initializer_list. As the linked page states :

A std::initializer_list object is automatically constructed when:

• [...]
• a braced-init-list is bound to auto, including in a ranged for loop

And :

An object of type std::initializer_list<T> is a lightweight proxy object that provides access to an array of objects of type const T.

Thus, you can't modify the objects accessed through this initialize_list. Your solutions with the pointers looks like the easiest one to me.

Answer 4

Direct answer to your question:

Am I correctly guessing that brace-initializer is creating copy of those lists?

Yes, this is the first problem. Your code would create copies of your lists, sort those copies, and finally forget the sorted copies.

However, that alone would just result in non-working code. The compiler error hints to a second problem: The implicit type of l is list<int> const&, rather than list<int>&. So the compiler complains that sort() tries to modify constant lists.

You can work around this second problem with a nasty const_cast:

#include <list>
#include <iostream>
using namespace std;
int main(void){
    list<int> a,b,c;
    a.push_back(2);
    a.push_back(0);
    a.push_back(1);
    for(auto& l:{a,b,c}) const_cast<list<int>&>(l).sort();
    for(auto i:a) cout << i << endl;
}

However, that will then trigger the first problem: Your list of lists contains copies, and only those copies are sorted. So the final output is not what you want:

2
0
1

The easiest workaround is to create a list of pointers to your lists:

#include <list>
#include <iostream>
using namespace std;
int main(void){
    list<int> a,b,c;
    a.push_back(2);
    a.push_back(0);
    a.push_back(1);
    for(auto l:{&a,&b,&c}) l->sort();
    for(auto i:a) cout << i << endl;
}

This will produce the desired result:

0
1
2