Constexpr查找实现

Question

回答完this question并阅读this talk并查看this code，我想实现constexpr find仅仅是简单的数组类。

考虑下面的例子：

#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

以及使用自定义constexpr迭代：

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; 

这唯一的区别，编译器给我的错误：

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的错误，因为铛编译此罚款，有两个片段的差异？

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

顺便说一句，这是可以实现C++ 11版本constexpr启用发现：

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

您可能也有兴趣检查它包含了很多constexpr数据结构和算法。