Constexpr tìm thực hiện

Question

Sau khi trả lời this question và đọc this talk và xem this code, tôi muốn triển khai constexpr find chỉ với lớp mảng đơn giản.

xem xét sau Ví dụ:

#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

Và với tùy chỉnh constexpr iterator:

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

Trong lớp mảng:

typedef const array_iterator<const T> const_iterator; 

đó là sự khác biệt duy, trình biên dịch cho tôi lỗi:

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

là lỗi gcc này, vì kêu vang biên dịch tốt này, hoặc có sự khác biệt trong hai đoạn?

Answer 1

Tôi không thể nói chắc chắn, nhưng bạn lưu trữ con trỏ cho thành viên của mảng vào lớp lặp bên ngoài, đó có thể là lý do cho lỗi đó.

--------- cập nhật bắt đầu ---------

Dưới đây là đoạn tối thiểu đó chứng tỏ vấn đề:

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 
} 

Nó dường như bị cấm để có con trỏ đến các phần tử mảng (với chênh lệch khác 0) trong các biểu thức không đổi.

--------- cập nhật kết thúc ---------

Cách giải quyết là tầm thường - lưu con trỏ vào đối tượng mảng và bù đắp.

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

Bằng cách này, chúng ta có thể thực hiện phiên bản C++ 11 của constexpr kích hoạt tìm:

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

Bạn cũng có thể quan tâm để kiểm tra Sprout library, nó chứa rất nhiều cấu trúc và thuật toán dữ liệu constexpr.