-->

Constexpr find for array using c++17

2020-07-22 20:10发布

问题:

I am trying to write a constexpr find function that will return the index of a std::array containing a certain value. The function below seems to work OK except when the contained type is const char*:

#include <array>

constexpr auto name1() {
    return "name1";
}

constexpr auto name2() {
    return "name2";
}

template <class X, class V>
constexpr auto find(X& x, V key) {
    std::size_t i = 0;
    while(i < x.size()) {
        if(x[i] == key) return i;
        ++i;
    }

    return i;
}


int main() {

    constexpr std::array<const char*, 2> x{{name1(), name2()}};
    constexpr auto f1 = find(x, name1()); // this compiles
    constexpr auto f2 = find(x, name2()); // this doesn't...
}

The weird thing is that find(x, name1()) compiles cleanly but find(x, name2()) fails with the error:

subexpression not valid in a constant expression
        if(x[i] == key) return i; `

How can this expression work when used with name1() but fail when used with name2()?

I have also found this answer, but the user builds the array class from scratch and I do not want to do that.

回答1:

Seems like a compiler bug. Both f1 and f2 should fail to compile in the same way.

The main issue is that it's an assumption that "name1" == "name1" and "name1" != "name2". The standard in fact provides no such guarantees, see [lex.string]/16:

Whether all string literals are distinct (that is, are stored in nonoverlapping objects) and whether successive evaluations of a string-literal yield the same or a different object is unspecified.

Even though the assumption most likely holds, comparing unspecified values inside constexpr is expressly not allowed, see [expr.const]/2.23:

— a relational ([expr.rel]) or equality ([expr.eq]) operator where the result is unspecified;

A workaround (and the right thing to do) would be to not rely on addresses of string literals and instead compare the actual strings. For example:

constexpr bool equals(const char* a, const char* b) {
    for (std::size_t i = 0; ; ++i) {
        if (a[i] != b[i]) return false;
        if (a[i] == 0) break;
    }
    return true;
}

template <class X, class V>
constexpr auto find(X& x, V key) {
    std::size_t i = 0;
    while(i < x.size()) {
        if(equals(x[i], key)) return i;
        ++i;
    }

    return i;
}