I have a class FlatSet, which is a wrapper around std::vector and implements same interface as std::set.
Recently, new version of visual studio came out with support for c++20's constexpr vector, and I thought I could make the FlatSet constexpr too.
Incidentally, I also have a good use case: I have a pair of functions de/encodeAck, which takes integer and produces FlatSet based on its bits, or vice versa. I want to test these functions with static_assert.
Unfortunately, no compiler seems to accept it as of now (I tried msvc, clang and gcc - all trunk with c++20 enabled). Is my use case correct and the compilers are just not mature enough? Or do I misunderstand something?
Here is all the necessary code:
#include <cstdint>
#include <utility>
#include <type_traits>
#include <vector>
#include <algorithm> // lower_bound, binary_search
#include <functional> // less
using uint8 = std::uint8_t;
using uint16 = std::uint16_t;
using uint32 = std::uint32_t;
using uint64 = std::uint64_t;
using sint8 = std::int8_t;
using sint16 = std::int16_t;
using sint32 = std::int32_t;
using sint64 = std::int64_t;
using uintPtr = std::conditional_t<sizeof(void*) == 8, uint64, uint32>;
using sintPtr = std::conditional_t<sizeof(void*) == 8, sint64, sint32>;
template<class Value, class Compare = std::less<Value>>
struct FlatSet
{
public:
using key_type = Value;
using value_type = Value;
using const_iterator = typename std::vector<Value>::const_iterator;
using const_reverse_iterator = typename std::vector<Value>::const_reverse_iterator;
using size_type = typename std::vector<Value>::size_type;
constexpr FlatSet() = default;
constexpr FlatSet(const FlatSet &other) = default;
constexpr FlatSet(FlatSet &&other) = default;
template<class InputIt>
constexpr FlatSet(InputIt first, InputIt last)
{
insert(first, last);
}
constexpr FlatSet(std::initializer_list<Value> init)
{
insert(init.begin(), init.end());
}
constexpr FlatSet &operator = (const FlatSet &other) = default;
constexpr FlatSet &operator = (FlatSet &&other) = default;
constexpr FlatSet &operator = (std::initializer_list<Value> ilist)
{
clear();
insert(ilist.begin(), ilist.end());
return *this;
}
constexpr std::pair<const_iterator, bool> insert(const Value &value)
{
auto it = std::lower_bound<const_iterator, Value, Compare>(data_.begin(), data_.end(), value, Compare());
if (it != data_.end() && equals(*it, value))
return { it, false };
return { data_.insert(it, value), true };
}
constexpr std::pair<const_iterator, bool> insert(Value &&value)
{
auto it = std::lower_bound<const_iterator, Value, Compare>(data_.begin(), data_.end(), value, Compare());
if (it != data_.end() && equals(*it, value))
return { it, false };
return { data_.insert(it, std::move(value)), true };
}
template<class InputIt>
constexpr void insert(InputIt first, InputIt last)
{
while (first != last)
insert(*first++);
}
constexpr void insert(std::initializer_list<Value> ilist)
{
insert(ilist.begin(), ilist.end());
}
constexpr const_iterator erase(const_iterator pos)
{
return data_.erase(pos);
}
constexpr const_iterator erase(const_iterator first, const_iterator last)
{
return data_.erase(first, last);
}
constexpr uintPtr erase(const Value &value)
{
auto it = std::lower_bound<const_iterator, Value, Compare>(data_.begin(), data_.end(), value, Compare());
if (it != data_.end() && equals(*it, value))
{
data_.erase(it);
return 1;
}
return 0;
}
constexpr void clear()
{
data_.clear();
}
constexpr void reserve(uintPtr s)
{
data_.reserve(s);
}
constexpr const_iterator find(const Value &value) const
{
auto it = std::lower_bound<const_iterator, Value, Compare>(data_.begin(), data_.end(), value, Compare());
if (it != data_.end() && equals(*it, value))
return it;
return data_.end();
}
constexpr uintPtr count(const Value &value) const
{
return std::binary_search<const_iterator, Value, Compare>(data_.begin(), data_.end(), value, Compare());
}
constexpr uintPtr size() const noexcept
{
return data_.size();
}
constexpr bool empty() const noexcept
{
return data_.empty();
}
constexpr const Value *data() const noexcept
{
return data_.data();
}
constexpr const_iterator begin() const noexcept
{
return data_.begin();
}
constexpr const_iterator end() const noexcept
{
return data_.end();
}
constexpr const_reverse_iterator rbegin() const noexcept
{
return data_.rbegin();
}
constexpr const_reverse_iterator rend() const noexcept
{
return data_.rend();
}
private:
std::vector<Value> data_;
static constexpr bool equals (const Value &a, const Value &b)
{
return !Compare()(a, b) && !Compare()(b, a);
}
friend constexpr bool operator == (const FlatSet &a, const FlatSet &b)
{
return a.data_ == b.data_;
}
};
constexpr FlatSet<uint16> decodeAck(uint16 seqn, uint32 bits)
{
FlatSet<uint16> result;
result.reserve(32);
for (uint16 i = 0; i < 32; i++)
{
uint32 m = uint32(1) << i;
if ((bits & m) == m)
{
uint16 s = seqn - i;
result.insert(s);
}
}
return result;
}
constexpr uint32 encodeAck(uint16 seqn, const FlatSet<uint16> &bits)
{
uint32 result = 0;
for (uint16 i = 0; i < 32; i++)
{
uint16 s = seqn - i;
if (bits.count(s))
{
uint32 m = uint32(1) << i;
result |= m;
}
}
return result;
}
static_assert(decodeAck(1000, encodeAck(1000, { 999 })) == FlatSet<uint16>({ 999 }));
static_assert(decodeAck(1000, encodeAck(1000, { 1000 })) == FlatSet<uint16>({ 1000 }));
//static_assert(decodeAck(1000, encodeAck(1000, { 1000, 999 })) == FlatSet<uint16>({ 1000, 999 }));
//static_assert(decodeAck(1000, encodeAck(1000, { 1000, 999, 990 })) == FlatSet<uint16>({ 1000, 999, 990 }));
static_assert(decodeAck(5, encodeAck(5, { 1, 65533 })) == FlatSet<uint16>({ 1, 65533 }));
// the commented lines issue this error:
<source>(213): error C2131: expression did not evaluate to a constant
C:/data/msvc/14.29.30130.2-Pre/include\vector(826): note: failure was caused by call of undefined function or one not declared 'constexpr'
C:/data/msvc/14.29.30130.2-Pre/include\vector(826): note: see usage of 'std::_Alloc_temporary<std::allocator<Value>>::_Alloc_temporary'
with
[
Value=uint16
]
https://godbolt.org/z/xGeE6xcxP
Thanks