Constexpr trova l'implementazione

Question

Dopo aver risposto a this question e aver letto this talk e guardando this code, voglio implementare constexpr find con una semplice classe di array.

Consideriamo seguente esempio:

#include <cstddef> 

template <class It, class T> 
constexpr auto constexpr_find(const It& b, const It& e, T value) { 
    auto begin = b; 
    while (begin != e) { 
     if (*begin == value) break; 

     ++begin; 
    } 
    return *begin; 
} 

template<typename T, size_t N> 
class array 
{ 
public: 
    typedef T* iterator; 
    typedef const T* const_iterator; 
    constexpr auto begin() const { return const_iterator(array_); } 
    constexpr auto end() const { return const_iterator(array_ + N); } 

    T array_[N]; 
    static constexpr size_t size = N; 
}; 

int main() 
{ 
    constexpr array<int, 3> array{{0,2,3}}; 
    static_assert(constexpr_find(array.begin(), array.end(), 0) == 0, ""); 
} 

compiles as expected

E con l'abitudine constexpr iteratore:

template<class T> 
class array_iterator 
{ 
public: 
    constexpr array_iterator(const T* v) : iterator(v) 
    { 
    } 
    constexpr const T& operator *() const { return *iterator; } 
    constexpr array_iterator& operator ++() 
    { 
     ++iterator; 
     return *this; 
    } 
    constexpr bool operator != (const array_iterator& other) const { return iterator != other.iterator; } 
private: 
    const T* iterator; 
}; 

In classe Array:

typedef const array_iterator<const T> const_iterator; 

che è l'unica differenza, compilatore dammi errore:

in constexpr expansion of constexpr_find<array_iterator<const int>, int>(array.array<T, N>::begin<int, 3u>(), array.array<T, N>::end<int, 3u>(), 0)

error: (((const int*)(& array.array<int, 3u>::array_)) != (((const int*)(& array.array<int, 3u>::array_)) + 12u)) is not a constant expression

Live example

È questo bug gcc, dal momento che clang compilare questo fine, o non v'è differenza di due frammenti?

Answer 1

Non posso dire con certezza, ma si memorizzano i puntatori per il membro dell'array nella classe iteratore esterna, potrebbe essere la ragione di tale errore.

--------- --------- inizio aggiornamento

Ecco il frammento di minima che illustra il problema:

constexpr const struct A { int i[2]; } a {{0,0}}; 

int main() 
{ 
    static_assert (nullptr != a.i , ""); // ok 
    static_assert (nullptr != a.i+0, ""); // ok 
    static_assert (nullptr != a.i+1, ""); // error 
} 

Sembra essere proibita avere puntatori agli elementi di un array (con offset diverso da zero) in espressioni costanti.

fine aggiornamento --------- ---------

La soluzione è banale - memorizzare il puntatore oggetto array e offset.

Live

#include <cstddef> 

template <class It, class T> 
constexpr auto constexpr_find(const It& b, const It& e, T value) { 
    auto begin = b, end = e; 
    while (begin != end) { 
     if (*begin == value) break; 

     ++begin; 
    } 
    return *begin; 
} 

template<class Array> 
class array_iterator 
{ 
public: 
    constexpr array_iterator(const Array& a, size_t pos=0u) : array_(&a), pos_ (pos) 
    { 
    } 
    constexpr const typename Array::value_type& 
    operator *() const { return (*array_)[pos_]; } 

    constexpr array_iterator& operator ++() 
    { 
     ++pos_; 
     return *this; 
    } 
    constexpr bool operator != (const array_iterator& other) const 
    { return array_ != other.array_ || pos_ != other.pos_; } 

private: 
    const Array* array_; 
    size_t pos_; 
}; 

template<typename T, size_t N> 
class array 
{ 
public: 
    typedef T value_type; 
    typedef const array_iterator<array> const_iterator; 
    constexpr T const& operator[] (size_t idx) const { return array_[idx]; } 
    constexpr auto begin() const { return const_iterator(*this); } 
    constexpr auto end() const { return const_iterator(*this, N); } 

    T array_[N]; 
    static constexpr size_t size = N; 
}; 

int main() 
{ 
    constexpr array<int, 3> array{{0,2,3}}; 
    static_assert(constexpr_find(array.begin(), array.end(), 0) == 0, ""); 
} 

Tra l'altro, è possibile implementare C++ 11 versione di constexpr abilitato ritrovamento:

Live

#include <cstddef> 
#include <cassert> 

#if !defined(__clang__) && __GNUC__ < 5 
// TODO: constexpr asserts does not work in gcc4, but we may use 
// "thow" workaround from 
// http://ericniebler.com/2014/09/27/assert-and-constexpr-in-cxx11/ 
# define ce_assert(x) ((void)0) 
#else 
# define ce_assert(x) assert(x) 
#endif 
namespace my { 

template <class It, class T> 
inline constexpr It 
find (It begin, It end, T const& value) noexcept 
{ 
    return ! (begin != end && *begin != value) 
     ? begin 
     : find (begin+1, end, value); 
} 

template<class Array> 
class array_iterator 
{ 
public: 
    using value_type = typename Array::value_type; 

    constexpr array_iterator(const Array& array, size_t size = 0u) noexcept 
    : array_ (&array) 
    , pos_ (size) 
    {} 

    constexpr const value_type operator*() const noexcept 
    { 
    return ce_assert (pos_ < Array::size), (*array_) [pos_]; 
    } 

#if __cplusplus >= 201402L // C++14 
    constexpr 
#endif 
    array_iterator& operator ++() noexcept 
    { 
    return ce_assert (pos_ < Array::size), ++pos_, *this; 
    } 

    constexpr array_iterator operator+ (size_t n) const noexcept 
    { 
    return ce_assert (pos_+n <= Array::size), array_iterator (*array_, pos_+n); 
    } 

    friend constexpr bool 
    operator != (const array_iterator& i1, const array_iterator& i2) noexcept 
    { 
    return i1.array_ != i2.array_ || i1.pos_ != i2.pos_; 
    } 

    friend constexpr size_t 
    operator- (array_iterator const& i1, array_iterator const& i2) noexcept 
    { 
    return ce_assert (i1.array_ == i2.array_), i1.pos_ - i2.pos_; 
    } 

private: 
    const Array* array_; 
    size_t pos_; 
}; 

template<typename T, size_t N> 
class array 
{ 
public: 
    using value_type = T; 
    using const_iterator = const array_iterator<array>; 

    constexpr value_type const& 
    operator[] (size_t idx) const noexcept 
    { return array_[idx]; } 

    constexpr const_iterator begin() const noexcept 
    { return const_iterator(*this); } 

    constexpr const_iterator end() const noexcept 
    { return const_iterator(*this, N); } 

    T array_[N]; 
    static constexpr size_t size = N; 
}; 

} 

int main() 
{ 
    static constexpr my::array<int, 3> array{{0,2,3}}; 

    static_assert (
    find (array.begin(), array.end(), 2) - array.begin() == 1, 
    "error"); 
} 

Si può anche essere interessati a verificare Sprout library, contiene molte strutture e algoritmi di dati di constexpr.