Constexpr find implementation

Question

this questionと、this talkとを読んで、this codeを見ると、単純な配列クラスでconstexpr findを実装したいと思います。

たとえば、次の点を考慮：配列クラスで

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; 
}; 

：

typedef const array_iterator<const T> const_iterator; 

だ

compiles as expected

とカスタムconstexprのイテレータと

#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, ""); 
} 

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

が打ち鳴らすが、この罰金をコンパイルするので、このgccのバグで、または2つのスニペットに差がある。唯一の違いは、コンパイラは私にエラーを与えますか？

Answer 1

私は確かに言うことはできませんが、配列のメンバのポインタを外部のイテレータクラスに格納すると、そのエラーの原因かもしれません。ここで

---------更新開始---------

は、問題を示し、最小限の抜粋です：

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 
} 

禁じられているように見えます定数式に配列要素へのポインタ（オフセットがゼロでない）を持たせる。

---------更新終了---------

問題を回避するには自明である - 配列オブジェクトへのポインタを格納し、オフセット。

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, ""); 
} 

ところで、constexprの有効検索のC++ 11バージョンを実装することが可能である：またチェックして興味がある可能性があり

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"); 
} 

をSprout libraryには、多くのconstexprデータ構造とアルゴリズムが含まれています。