Validate contents of std::initializer_list at compile time

Question

I am attempting to determine at compile time if all the values in a std::initializer_list are unique. I was able to locate a solution to valiate the size of a list but have been unable to apply it to the contents. I have tried with both free functions and in constructors but both approaches have resulted in the following errors with GCC 4.7.2.

error: non-constant condition for static assertion
error: 'begin' is not a constant expression

I realize the members of std::initializer_list are not declared constexpr but I'm hoping there is a solution like the size validation. Is it possible to validate the contents at compile time using something like the following?

#include <initializer_list>

template<typename InputIterator>
constexpr bool Validate(InputIterator begin, InputIterator end)
{
    static_assert(*begin == *end, "begin and end are the same");
    //  The actual implemetnation is a single line recursive check.
    return true;
}

template<typename InputType>
constexpr bool Validate(const std::initializer_list<InputType>& input)
{
    // "-1" removed to simplify and eliminate potential cause of error
    return Validate(input.begin(), input.end() /* - 1 */);
}

int main()
{
    Validate({1, 2, 1});
}

According to the current proposal for [C++14](http://isocpp.org/files/papers/N3690.pdf), `begin()` and `end()` of `std::initializer_list` will be `constexpr` in the future (see 18.9/1). That removes one obstacle, but I am not sure whether dereferencing the iterator values will ever be possible at compile time. — jogojapan, May 25 '13 at 06:46
@jogojapan: The "iterators" of an `std::initializer_list` are just `T*` - guaranteed. — Xeo, May 25 '13 at 07:42
@Xeo Yes, and I assumed that dereferencing such a pointer would not be allowed in a constant expression. — jogojapan, May 25 '13 at 08:15
@jogojapan: I'm pretty sure that, if you manage to get a pointer in constexpr code, dereferencing it is legal. — Nicol Bolas, May 25 '13 at 09:14
@NicolBolas Yes, the Standard says (in 5.19) that you can have an lvalue-to-rvalue conversion in a constant expression if the lvalue is of integral type with a preceding initialization, initialized with a constant expression. I've always assumed this isn't the case with something passed as a function argument, but perhaps I am wrong. — jogojapan, May 25 '13 at 09:18

Captain Obvlious · Accepted Answer · 2013-05-25T14:14:17.000

After some digging it looks like using std::initializer_list is not possible in GCC 4.7 due to the lack of constexpr in it's declaration. It should work with GCC 4.8 as <initializer_list> has been updated to include constexpr. Unfortunately using GCC 4.8 is not an option at the moment.

It is possible to access elements of an array if the decayed pointer is passed by reference though. This allows the validation to occur as desired but still isn't quite the solution I am hoping for. The following code is a workable solution for arrays. It still requires that the size of the array be supplied to the validation function but that it easy enough to correct.

#include <initializer_list>

template<typename T>
constexpr bool Compare(T& data, int size, int needleIndex, int haystackIndex)
{
    return
        needleIndex == haystackIndex ?
            Compare(data, size, needleIndex + 1, haystackIndex)
        :   needleIndex == size ?
                false
            :   data[needleIndex] == data[haystackIndex] ?
                    true
                :   Compare(data, size, needleIndex + 1, haystackIndex);
}

template<typename T>
constexpr bool Compare(T& data, int size, int index)
{
    return
        index == size ?
            false
        :   Compare(data, size, index + 1) ?
                true
            :   Compare(data, size, 0, index);
}


template<typename T, int ArraySize>
constexpr bool Validate(T(&input)[ArraySize], int size)
{
    return !Compare(input, size, 0);
}

int main()
{
    constexpr int initData0[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    constexpr int initData1[] = {1, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    constexpr int initData2[] = {2, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    constexpr int initData3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 8};
    constexpr int initData4[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 7};
    constexpr int initData5[] = {0, 1, 0, 3, 4, 5, 6, 7, 8, 9};
    constexpr int initData6[] = {0, 1, 2, 3, 4, 5, 6, 9, 8, 9};

    static_assert(Validate(initData0, 10), "set 0 failed"); // <-- PASS
    static_assert(Validate(initData1, 10), "set 1 failed"); // <-- (and below) FAIL
    static_assert(Validate(initData2, 10), "set 2 failed");
    static_assert(Validate(initData3, 10), "set 3 failed");
    static_assert(Validate(initData4, 10), "set 4 failed");
    static_assert(Validate(initData5, 10), "set 5 failed");
    static_assert(Validate(initData6, 10), "set 6 failed");
}

.

Build log:

C:\Source\SwitchCaseString\main.cpp: In function 'int main()':
C:\Source\SwitchCaseString\main.cpp:198:2: error: static assertion failed: set 1 failed
C:\Source\SwitchCaseString\main.cpp:199:2: error: static assertion failed: set 2 failed
C:\Source\SwitchCaseString\main.cpp:200:2: error: static assertion failed: set 3 failed
C:\Source\SwitchCaseString\main.cpp:201:2: error: static assertion failed: set 4 failed
C:\Source\SwitchCaseString\main.cpp:202:2: error: static assertion failed: set 5 failed
C:\Source\SwitchCaseString\main.cpp:203:2: error: static assertion failed: set 6 failed

Validate contents of std::initializer_list at compile time

1 Answers1

.