Skip to content

Instantly share code, notes, and snippets.

@gnzlbg
Created Mar 11, 2017
Embed
What would you like to do?
A flat set container adaptor.
#pragma once
/// \file
///
/// A flat set implemented as a vector-like container adaptor.
#include <hm3/utility/range.hpp>
#include <hm3/utility/small_vector.hpp>
#include <hm3/utility/vector.hpp>
namespace hm3 {
/// A set that models ContiguousContainer.
///
/// \tparam K key-type stored in the container.
/// \tparam Compare BinaryPredicate + Strict Weak Ordering Relation.
/// \tparam Vector vector-like container used as storage.
template <typename K, typename Compare = std::less<K>,
typename Vector = vector<K>>
struct flat_set : private Vector, Compare {
static_assert(Same<ranges::range_value_t<Vector>, K>{});
static_assert(not std::is_const<K>{});
static_assert(ranges::Relation<Compare, K, K>{});
static_assert(ranges::Predicate<Compare, K, K>{});
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
using value_type = K;
using const_reference = typename Vector::const_reference&;
using reference = const_reference;
using const_pointer = typename Vector::const_pointer;
using pointer = const_pointer;
using const_iterator = typename Vector::const_iterator;
using iterator = const_iterator;
using const_reverse_iterator = typename std::reverse_iterator<const_iterator>;
using reverse_iterator = const_reverse_iterator;
private:
using vec_t = Vector;
public:
using vec_t::size;
using vec_t::capacity;
using vec_t::empty;
using vec_t::max_size;
/// \name Immutable data access
///@{
/// Pointer to the first element of the container.
constexpr const_pointer data() const noexcept { return get_vector().data(); }
/// Iterator to the beginning of the container.
constexpr const_iterator begin() const noexcept {
return get_vector().begin();
}
/// Iterator to one past the last element of the container..
constexpr const_iterator end() const noexcept { return get_vector().end(); }
/// Iterator to the beginning of the container.
constexpr const_iterator cbegin() const noexcept {
return get_vector().cbegin();
}
/// Iterator to one past the last element of the container..
constexpr const_iterator cend() const noexcept { return get_vector().cend(); }
/// Unchecked reference to the key at position \p pos (nth_element).
constexpr const_reference operator[](size_type pos) const noexcept {
HM3_ASSERT(pos < size(), "position {} out-of-bounds [0, {})", pos, size());
return get_vector()[pos];
}
/// Checked reference to the key at position \p pos (nth_element). Throws if
/// the key does not exist.
constexpr const_reference at(size_type pos) const {
return get_vector().at(pos);
}
/// Unchecked reference to the first element of the container.
constexpr const_reference front() const noexcept {
return get_vector().front();
}
/// Unchecked reference to the last element of the container.
constexpr const_reference back() const noexcept {
return get_vector().back();
}
///@} // Immutable data access
private:
constexpr Vector& get_vector() noexcept {
return static_cast<Vector&>(*this);
}
constexpr Vector const& get_vector() const noexcept {
return static_cast<Vector const&>(*this);
}
constexpr Compare& get_compare() noexcept {
return static_cast<Compare&>(*this);
}
constexpr Compare const& get_compare() const noexcept {
return static_cast<Compare const&>(*this);
}
/// Sorts and uniques the elements of the vector.
constexpr void sort_unique() noexcept {
ranges::sort(get_vector(), get_compare());
get_vector().erase(ranges::unique(get_vector()), get_vector().end());
}
public:
/// \name Constructors / Assignment
///@{
constexpr flat_set(const Compare& comp = Compare(), Vector&& vec = Vector())
: Vector(std::move(vec)), Compare(comp) {
sort_unique();
}
constexpr flat_set(const flat_set& other) = default;
constexpr flat_set(flat_set&& other) = default;
constexpr flat_set& operator=(flat_set const& other) = default;
constexpr flat_set& operator=(flat_set&& other) = default;
explicit constexpr explicit flat_set(Vector&& vec)
: flat_set(Compare(), std::move(vec)) {}
template <class InputIt>
constexpr flat_set(InputIt first, InputIt last,
const Compare& comp = Compare())
: Vector(first, last), Compare(comp) {
static_assert(InputIterator<InputIt>{});
static_assert(ConvertibleTo<ranges::iterator_value_t<InputIt>, K>{});
sort_unique();
}
constexpr flat_set(std::initializer_list<value_type> init,
const Compare& comp = Compare())
: flat_set(ranges::begin(init), ranges::end(init), comp) {}
private:
template <typename Rng>
using insertable_range
= meta::if_<meta::not_<Same<uncvref_t<Rng>, Vector>>,
meta::not_<Same<uncvref_t<Rng>, value_type>>,
ConvertibleTo<ranges::range_reference_t<Rng>, value_type>>;
public:
template <typename Rng,
CONCEPT_REQUIRES_(
insertable_range<Rng>{}
and not Same<uncvref_t<Rng>, std::initializer_list<value_type>>{})>
explicit constexpr flat_set(Rng&& rng, const Compare& comp = Compare())
: flat_set(ranges::begin(rng), ranges::end(rng), comp) {}
///@} Constructors / Assignment
/// \name Mutating operations
///@{
using vec_t::clear;
/// Inserts the key \p v in the set. Returns a pair of an iterator to the
/// inserted value and a boolean which is true if an insertion happenend, and
/// false otherwise.
template <typename K_, CONCEPT_REQUIRES_(ConvertibleTo<K_, value_type>{})>
constexpr pair<const_iterator, bool> insert(K_&& v) {
auto pos = lower_bound(v);
if (pos != end() and *pos == v) { return {pos, false}; }
get_vector().insert(pos, std::forward<K_>(v));
return {pos, true};
}
/// Inserts the range [first, last) into the set.
template <typename InputIt>
constexpr void insert(InputIt first, InputIt last) {
// cannot assume that the range first last is sorted, or that it does not
// contain duplicate elements :/
get_vector().insert(end(), first, last);
sort_unique();
}
/// Inserts the range \p range into the set.
template <typename Rng, CONCEPT_REQUIRES_(insertable_range<Rng>{})>
constexpr void insert(Rng&& rng) {
insert(ranges::begin(rng), ranges::end(rng));
}
/// Inserts initializer list \p rng.
constexpr void insert(std::initializer_list<value_type> rng) {
insert(ranges::begin(rng), ranges::end(rng));
}
// note: emplace does not really make sense, because we need to construct the
// value anyways before inserting in the container to look up if it exists.
// (it make sense for node-based containers though, because you can emplace
// inside the node, but a flat set is not node-based).
/// Erases the key at position \p it.
constexpr const_iterator erase(const_iterator it) noexcept {
HM3_ASSERT(begin() <= it and it <= end(), "iterator out-of-bounds");
return get_vector().erase(it);
}
/// Erases the keys in range [first, last).
constexpr const_iterator erase(const_iterator first,
const_iterator last) noexcept {
HM3_ASSERT(begin() <= first and first <= end(), "iterator out-of-bounds");
HM3_ASSERT(begin() <= last and last <= end(), "iterator out-of-bounds");
return get_vector().erase(first, last);
}
/// Erases the key that compares equal to \p v. Returns the number of keys
/// erased (0 or 1).
template <typename K_,
CONCEPT_REQUIRES_(not Same<uncvref_t<K_>, const_iterator>{})>
constexpr std::size_t erase(K_&& v) noexcept {
auto pos = lower_bound(std::forward<K_>(v));
if (pos != end() and *pos == v) {
erase(pos);
return 1;
}
return 0;
}
/// Replaces the key that compares equal to \p v with \p v.
template <typename K_>
constexpr void replace(K_&& v) noexcept {
auto pos = lower_bound(v);
HM3_ASSERT(pos != end() and *pos == v,
"cannot replace a non-existing element");
if (pos != end() and *pos == v) {
(*const_cast<pointer>(pos)) = std::forward<K_>(v);
}
}
// swap (use default)
///@} // Mutating operations
/// \name Immutable operations
///@{
/// Iterator to the largest element smaller than \p k.
template <typename K_>
constexpr const_iterator lower_bound(K_&& k) const noexcept {
return ranges::lower_bound(get_vector(), std::forward<K_>(k),
get_compare());
}
/// Iterator to the smallest element larger than \p k.
template <typename K_>
constexpr const_iterator upper_bound(K_&& k) const noexcept {
return ranges::upper_bound(get_vector(), std::forward<K_>(k),
get_compare());
}
/// Pair of iterators (lower_bound(k), upper_bound(k)).
template <typename K_>
constexpr pair<const_iterator, const_iterator> equal_range(K_&& k) const
noexcept {
return ranges::equal_range(get_vector(), std::forward<K_>(k),
get_compare());
}
/// Iterator to the element that compares equal to \p k.
template <typename K_>
constexpr const_iterator find(K_&& k) const noexcept {
auto it = lower_bound(std::forward<K_>(k));
if (it == end() or *it == k) { return it; }
return end();
}
/// Number of elements that compares equal to \p k (0 or 1).
template <typename K_>
constexpr std::size_t count(K_&& k) const noexcept {
return find(std::forward<K_>(k)) == end() ? 0 : 1;
}
/// Does the set contain an element that compares equal to \p k?
template <typename K_>
constexpr bool contains(K_&& k) const noexcept {
return find(std::forward<K_>(k)) == end() ? false : true;
}
///@} // Immutable operations
/// Releases the vector.
Vector release() noexcept { return std::move(get_vector()); }
/// Returns a copy of the object that compares the keys.
constexpr Compare key_comp() const noexcept { return get_compare(); }
/// Swaps two flat_sets.
void swap(flat_set& other) noexcept {
ranges::swap(get_vector(), other.get_vector());
}
/// \name Lexicographical comparison operators.
///@{
friend constexpr bool operator==(flat_set const& a,
flat_set const& b) noexcept {
return a.get_vector() == b.get_vector();
}
friend constexpr bool operator!=(flat_set const& a,
flat_set const& b) noexcept {
return a.get_vector() != b.get_vector();
}
friend constexpr bool operator<(flat_set const& a,
flat_set const& b) noexcept {
return a.get_vector() < b.get_vector();
}
friend constexpr bool operator<=(flat_set const& a,
flat_set const& b) noexcept {
return a.get_vector() <= b.get_vector();
}
friend constexpr bool operator>(flat_set const& a,
flat_set const& b) noexcept {
return a.get_vector() > b.get_vector();
}
friend constexpr bool operator>=(flat_set const& a,
flat_set const& b) noexcept {
return a.get_vector() >= b.get_vector();
}
///@} // Comparison operators
};
template <typename K, std::size_t N, typename C = std::less<K>>
using small_flat_set = flat_set<K, C, small_vector<K, N>>;
} // namespace hm3
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment