Compiler Explorer

Source code

/**
 * MIT License
 *
 * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tessil@gmx.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
#ifndef TSL_ORDERED_HASH_H
#define TSL_ORDERED_HASH_H

#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <exception>
#include <functional>
#include <iterator>
#include <limits>
#include <memory>
#include <stdexcept>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

/**
 * Macros for compatibility with GCC 4.8
 */
#if (defined(__GNUC__) && (__GNUC__ == 4) && (__GNUC_MINOR__ < 9))
#define TSL_OH_NO_CONTAINER_ERASE_CONST_ITERATOR
#define TSL_OH_NO_CONTAINER_EMPLACE_CONST_ITERATOR
#endif

/**
 * Only activate tsl_oh_assert if TSL_DEBUG is defined.
 * This way we avoid the performance hit when NDEBUG is not defined with assert
 * as tsl_oh_assert is used a lot (people usually compile with "-O3" and not
 * "-O3 -DNDEBUG").
 */
#ifdef TSL_DEBUG
#define tsl_oh_assert(expr) assert(expr)
#else
#define tsl_oh_assert(expr) (static_cast<void>(0))
#endif

/**
 * If exceptions are enabled, throw the exception passed in parameter, otherwise
 * call std::terminate.
 */
#if (defined(__cpp_exceptions) || defined(__EXCEPTIONS) || \
 (defined(_MSC_VER) && defined(_CPPUNWIND))) && \
 !defined(TSL_NO_EXCEPTIONS)
#define TSL_OH_THROW_OR_TERMINATE(ex, msg) throw ex(msg)
#else
#define TSL_OH_NO_EXCEPTIONS
#ifdef NDEBUG
#define TSL_OH_THROW_OR_TERMINATE(ex, msg) std::terminate()
#else
#include <iostream>
#define TSL_OH_THROW_OR_TERMINATE(ex, msg) \
 do { \
 std::cerr << msg << std::endl; \
 std::terminate(); \
 } while (0)
#endif
#endif

namespace tsl {

namespace detail_ordered_hash {

template <typename T>
struct make_void {
 using type = void;
};

template <typename T, typename = void>
struct has_is_transparent : std::false_type {};

template <typename T>
struct has_is_transparent<T,
 typename make_void<typename T::is_transparent>::type>
 : std::true_type {};

template <typename T, typename = void>
struct is_vector : std::false_type {};

template <typename T>
struct is_vector<T,
 typename std::enable_if<std::is_same<
 T, std::vector<typename T::value_type,
 typename T::allocator_type>>::value>::type>
 : std::true_type {};

// Only available in C++17, we need to be compatible with C++11
template <class T>
const T& clamp(const T& v, const T& lo, const T& hi) {
 return std::min(hi, std::max(lo, v));
}

template <typename T, typename U>
static T numeric_cast(U value,
 const char* error_message = "numeric_cast() failed.") {
 T ret = static_cast<T>(value);
 if (static_cast(ret) != value) {
 TSL_OH_THROW_OR_TERMINATE(std::runtime_error, error_message);
 }

const bool is_same_signedness =
 (std::is_unsigned<T>::value && std::is_unsigned::value) ||
 (std::is_signed<T>::value && std::is_signed::value);
 if (!is_same_signedness && (ret < T{}) != (value < U{})) {
 TSL_OH_THROW_OR_TERMINATE(std::runtime_error, error_message);
 }

return ret;
}

/**
 * Fixed size type used to represent size_type values on serialization. Need to
 * be big enough to represent a std::size_t on 32 and 64 bits platforms, and
 * must be the same size on both platforms.
 */
using slz_size_type = std::uint64_t;
static_assert(std::numeric_limits<slz_size_type>::max() >=
 std::numeric_limits<std::size_t>::max(),
 "slz_size_type must be >= std::size_t");

template <class T, class Deserializer>
static T deserialize_value(Deserializer& deserializer) {
 // MSVC < 2017 is not conformant, circumvent the problem by removing the
 // template keyword
#if defined(_MSC_VER) && _MSC_VER < 1910
 return deserializer.Deserializer::operator()<T>();
#else
 return deserializer.Deserializer::template operator()<T>();
#endif
}

/**
 * Each bucket entry stores an index which is the index in m_values
 * corresponding to the bucket's value and a hash (which may be truncated to 32
 * bits depending on IndexType) corresponding to the hash of the value.
 *
 * The size of IndexType limits the size of the hash table to
 * std::numeric_limits<IndexType>::max() - 1 elements (-1 due to a reserved
 * value used to mark a bucket as empty).
 */
template <class IndexType>
class bucket_entry {
 static_assert(std::is_unsigned<IndexType>::value,
 "IndexType must be an unsigned value.");
 static_assert(std::numeric_limits<IndexType>::max() <=
 std::numeric_limits<std::size_t>::max(),
 "std::numeric_limits<IndexType>::max() must be <= "
 "std::numeric_limits<std::size_t>::max().");

public:
 using index_type = IndexType;
 using truncated_hash_type = typename std::conditional<
 std::numeric_limits<IndexType>::max() <=
 std::numeric_limits<std::uint_least32_t>::max(),
 std::uint_least32_t, std::size_t>::type;

bucket_entry() noexcept : m_index(EMPTY_MARKER_INDEX), m_hash(0) {}

bool empty() const noexcept { return m_index == EMPTY_MARKER_INDEX; }

void clear() noexcept { m_index = EMPTY_MARKER_INDEX; }

index_type index() const noexcept {
    tsl_oh_assert(!empty());
    return m_index;
  }

index_type& index_ref() noexcept {
    tsl_oh_assert(!empty());
    return m_index;
  }

void set_index(index_type index) noexcept {
 tsl_oh_assert(index <= max_size());

m_index = index;
  }

truncated_hash_type truncated_hash() const noexcept {
    tsl_oh_assert(!empty());
    return m_hash;
  }

truncated_hash_type& truncated_hash_ref() noexcept {
    tsl_oh_assert(!empty());
    return m_hash;
  }

void set_hash(std::size_t hash) noexcept { m_hash = truncate_hash(hash); }

template <class Serializer>
 void serialize(Serializer& serializer) const {
 const slz_size_type index = m_index;
 serializer(index);

const slz_size_type hash = m_hash;
    serializer(hash);
  }

template <class Deserializer>
 static bucket_entry deserialize(Deserializer& deserializer) {
 const slz_size_type index = deserialize_value<slz_size_type>(deserializer);
 const slz_size_type hash = deserialize_value<slz_size_type>(deserializer);

bucket_entry bentry;
 bentry.m_index =
 numeric_cast<index_type>(index, "Deserialized index is too big.");
 bentry.m_hash = numeric_cast<truncated_hash_type>(
 hash, "Deserialized hash is too big.");

return bentry;
  }

static truncated_hash_type truncate_hash(std::size_t hash) noexcept {
    return truncated_hash_type(hash);
  }

static std::size_t max_size() noexcept {
 return static_cast<std::size_t>(std::numeric_limits<index_type>::max()) -
 NB_RESERVED_INDEXES;
 }

private:
 static const index_type EMPTY_MARKER_INDEX =
 std::numeric_limits<index_type>::max();
 static const std::size_t NB_RESERVED_INDEXES = 1;

index_type m_index;
  truncated_hash_type m_hash;
};

/**
 * Internal common class used by ordered_map and ordered_set.
 *
 * ValueType is what will be stored by ordered_hash (usually std::pair<Key, T>
 * for map and Key for set).
 *
 * KeySelect should be a FunctionObject which takes a ValueType in parameter and
 * return a reference to the key.
 *
 * ValueSelect should be a FunctionObject which takes a ValueType in parameter
 * and return a reference to the value. ValueSelect should be void if there is
 * no value (in set for example).
 *
 * ValueTypeContainer is the container which will be used to store ValueType
 * values. Usually a std::deque<ValueType, Allocator> or std::vector<ValueType,
 * Allocator>.
 *
 *
 *
 * The ordered_hash structure is a hash table which preserves the order of
 * insertion of the elements. To do so, it stores the values in the
 * ValueTypeContainer (m_values) using emplace_back at each insertion of a new
 * element. Another structure (m_buckets of type std::vector<bucket_entry>) will
 * serve as buckets array for the hash table part. Each bucket stores an index
 * which corresponds to the index in m_values where the bucket's value is and
 * the (truncated) hash of this value. An index is used instead of a pointer to
 * the value to reduce the size of each bucket entry.
 *
 * To resolve collisions in the buckets array, the structures use robin hood
 * linear probing with backward shift deletion.
 */
template <class ValueType, class KeySelect, class ValueSelect, class Hash,
 class KeyEqual, class Allocator, class ValueTypeContainer,
 class IndexType>
class ordered_hash : private Hash, private KeyEqual {
 private:
 template <typename U>
 using has_mapped_type =
 typename std::integral_constant<bool, !std::is_same<U, void>::value>;

static_assert(
 std::is_same<typename ValueTypeContainer::value_type, ValueType>::value,
 "ValueTypeContainer::value_type != ValueType. "
 "Check that the ValueTypeContainer has 'Key' as type for a set or "
 "'std::pair<Key, T>' as type for a map.");

static_assert(std::is_same<typename ValueTypeContainer::allocator_type,
 Allocator>::value,
 "ValueTypeContainer::allocator_type != Allocator. "
 "Check that the allocator for ValueTypeContainer is the same "
 "as Allocator.");

static_assert(std::is_same<typename Allocator::value_type, ValueType>::value,
 "Allocator::value_type != ValueType. "
 "Check that the allocator has 'Key' as type for a set or "
 "'std::pair<Key, T>' as type for a map.");

public:
 template <bool IsConst>
 class ordered_iterator;

using key_type = typename KeySelect::key_type;
 using value_type = ValueType;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using hasher = Hash;
 using key_equal = KeyEqual;
 using allocator_type = Allocator;
 using reference = value_type&;
 using const_reference = const value_type&;
 using pointer = value_type*;
 using const_pointer = const value_type*;
 using iterator = ordered_iterator<false>;
 using const_iterator = ordered_iterator<true>;
 using reverse_iterator = std::reverse_iterator<iterator>;
 using const_reverse_iterator = std::reverse_iterator<const_iterator>;

using values_container_type = ValueTypeContainer;

public:
 template <bool IsConst>
 class ordered_iterator {
 friend class ordered_hash;

private:
 using iterator = typename std::conditional<
 IsConst, typename values_container_type::const_iterator,
 typename values_container_type::iterator>::type;

ordered_iterator(iterator it) noexcept : m_iterator(it) {}

public:
    using iterator_category = std::random_access_iterator_tag;
    using value_type = const typename ordered_hash::value_type;
    using difference_type = typename iterator::difference_type;
    using reference = value_type&;
    using pointer = value_type*;

ordered_iterator() noexcept {}

// Copy constructor from iterator to const_iterator.
 template <bool TIsConst = IsConst,
 typename std::enable_if<TIsConst>::type* = nullptr>
 ordered_iterator(const ordered_iterator<!TIsConst>& other) noexcept
 : m_iterator(other.m_iterator) {}

ordered_iterator(const ordered_iterator& other) = default;
    ordered_iterator(ordered_iterator&& other) = default;
    ordered_iterator& operator=(const ordered_iterator& other) = default;
    ordered_iterator& operator=(ordered_iterator&& other) = default;

const typename ordered_hash::key_type& key() const {
      return KeySelect()(*m_iterator);
    }

template <class U = ValueSelect,
 typename std::enable_if<has_mapped_type::value &&
 IsConst>::type* = nullptr>
 const typename U::value_type& value() const {
 return U()(*m_iterator);
 }

template <class U = ValueSelect,
 typename std::enable_if<has_mapped_type::value &&
 !IsConst>::type* = nullptr>
 typename U::value_type& value() {
 return U()(*m_iterator);
 }

reference operator*() const { return *m_iterator; }
    pointer operator->() const { return m_iterator.operator->(); }

ordered_iterator& operator++() {
      ++m_iterator;
      return *this;
    }
    ordered_iterator& operator--() {
      --m_iterator;
      return *this;
    }

ordered_iterator operator++(int) {
      ordered_iterator tmp(*this);
      ++(*this);
      return tmp;
    }
    ordered_iterator operator--(int) {
      ordered_iterator tmp(*this);
      --(*this);
      return tmp;
    }

reference operator[](difference_type n) const { return m_iterator[n]; }

ordered_iterator& operator+=(difference_type n) {
      m_iterator += n;
      return *this;
    }
    ordered_iterator& operator-=(difference_type n) {
      m_iterator -= n;
      return *this;
    }

ordered_iterator operator+(difference_type n) {
      ordered_iterator tmp(*this);
      tmp += n;
      return tmp;
    }
    ordered_iterator operator-(difference_type n) {
      ordered_iterator tmp(*this);
      tmp -= n;
      return tmp;
    }

friend bool operator==(const ordered_iterator& lhs,
                           const ordered_iterator& rhs) {
      return lhs.m_iterator == rhs.m_iterator;
    }

friend bool operator!=(const ordered_iterator& lhs,
                           const ordered_iterator& rhs) {
      return lhs.m_iterator != rhs.m_iterator;
    }

friend bool operator<(const ordered_iterator& lhs,
 const ordered_iterator& rhs) {
 return lhs.m_iterator < rhs.m_iterator;
 }

friend bool operator>(const ordered_iterator& lhs,
                          const ordered_iterator& rhs) {
      return lhs.m_iterator > rhs.m_iterator;
    }

friend bool operator<=(const ordered_iterator& lhs,
 const ordered_iterator& rhs) {
 return lhs.m_iterator <= rhs.m_iterator;
 }

friend bool operator>=(const ordered_iterator& lhs,
                           const ordered_iterator& rhs) {
      return lhs.m_iterator >= rhs.m_iterator;
    }

friend ordered_iterator operator+(difference_type n,
                                      const ordered_iterator& it) {
      return n + it.m_iterator;
    }

friend difference_type operator-(const ordered_iterator& lhs,
                                     const ordered_iterator& rhs) {
      return lhs.m_iterator - rhs.m_iterator;
    }

private:
    iterator m_iterator;
  };

private:
 using bucket_entry = tsl::detail_ordered_hash::bucket_entry<IndexType>;

using buckets_container_allocator = typename std::allocator_traits<
 allocator_type>::template rebind_alloc<bucket_entry>;

using buckets_container_type =
 std::vector<bucket_entry, buckets_container_allocator>;

using truncated_hash_type = typename bucket_entry::truncated_hash_type;
  using index_type = typename bucket_entry::index_type;

public:
  ordered_hash(size_type bucket_count, const Hash& hash, const KeyEqual& equal,
               const Allocator& alloc, float max_load_factor)
      : Hash(hash),
        KeyEqual(equal),
        m_buckets_data(alloc),
        m_buckets(static_empty_bucket_ptr()),
        m_hash_mask(0),
        m_values(alloc),
        m_grow_on_next_insert(false) {
    if (bucket_count > max_bucket_count()) {
      TSL_OH_THROW_OR_TERMINATE(std::length_error,
                                "The map exceeds its maximum size.");
    }

if (bucket_count > 0) {
      bucket_count = round_up_to_power_of_two(bucket_count);

m_buckets_data.resize(bucket_count);
      m_buckets = m_buckets_data.data(), m_hash_mask = bucket_count - 1;
    }

this->max_load_factor(max_load_factor);
  }

ordered_hash(const ordered_hash& other)
      : Hash(other),
        KeyEqual(other),
        m_buckets_data(other.m_buckets_data),
        m_buckets(m_buckets_data.empty() ? static_empty_bucket_ptr()
                                         : m_buckets_data.data()),
        m_hash_mask(other.m_hash_mask),
        m_values(other.m_values),
        m_load_threshold(other.m_load_threshold),
        m_max_load_factor(other.m_max_load_factor),
        m_grow_on_next_insert(other.m_grow_on_next_insert) {}

ordered_hash(ordered_hash&& other) noexcept(
 std::is_nothrow_move_constructible<
 Hash>::value&& std::is_nothrow_move_constructible<KeyEqual>::value&&
 std::is_nothrow_move_constructible<buckets_container_type>::value&&
 std::is_nothrow_move_constructible<values_container_type>::value)
 : Hash(std::move(static_cast<Hash&>(other))),
 KeyEqual(std::move(static_cast<KeyEqual&>(other))),
 m_buckets_data(std::move(other.m_buckets_data)),
 m_buckets(m_buckets_data.empty() ? static_empty_bucket_ptr()
 : m_buckets_data.data()),
 m_hash_mask(other.m_hash_mask),
 m_values(std::move(other.m_values)),
 m_load_threshold(other.m_load_threshold),
 m_max_load_factor(other.m_max_load_factor),
 m_grow_on_next_insert(other.m_grow_on_next_insert) {
 other.m_buckets_data.clear();
 other.m_buckets = static_empty_bucket_ptr();
 other.m_hash_mask = 0;
 other.m_values.clear();
 other.m_load_threshold = 0;
 other.m_grow_on_next_insert = false;
 }

ordered_hash& operator=(const ordered_hash& other) {
    if (&other != this) {
      Hash::operator=(other);
      KeyEqual::operator=(other);

m_buckets_data = other.m_buckets_data;
      m_buckets = m_buckets_data.empty() ? static_empty_bucket_ptr()
                                         : m_buckets_data.data();

m_hash_mask = other.m_hash_mask;
      m_values = other.m_values;
      m_load_threshold = other.m_load_threshold;
      m_max_load_factor = other.m_max_load_factor;
      m_grow_on_next_insert = other.m_grow_on_next_insert;
    }

return *this;
  }

ordered_hash& operator=(ordered_hash&& other) {
    other.swap(*this);
    other.clear();

return *this;
  }

allocator_type get_allocator() const { return m_values.get_allocator(); }

/*
   * Iterators
   */
  iterator begin() noexcept { return iterator(m_values.begin()); }

const_iterator begin() const noexcept { return cbegin(); }

const_iterator cbegin() const noexcept {
    return const_iterator(m_values.cbegin());
  }

iterator end() noexcept { return iterator(m_values.end()); }

const_iterator end() const noexcept { return cend(); }

const_iterator cend() const noexcept {
    return const_iterator(m_values.cend());
  }

reverse_iterator rbegin() noexcept {
    return reverse_iterator(m_values.end());
  }

const_reverse_iterator rbegin() const noexcept { return rcbegin(); }

const_reverse_iterator rcbegin() const noexcept {
    return const_reverse_iterator(m_values.cend());
  }

reverse_iterator rend() noexcept {
    return reverse_iterator(m_values.begin());
  }

const_reverse_iterator rend() const noexcept { return rcend(); }

const_reverse_iterator rcend() const noexcept {
    return const_reverse_iterator(m_values.cbegin());
  }

/*
   * Capacity
   */
  bool empty() const noexcept { return m_values.empty(); }

size_type size() const noexcept { return m_values.size(); }

size_type max_size() const noexcept {
    return std::min(bucket_entry::max_size(), m_values.max_size());
  }

/*
   * Modifiers
   */
  void clear() noexcept {
    for (auto& bucket : m_buckets_data) {
      bucket.clear();
    }

m_values.clear();
    m_grow_on_next_insert = false;
  }

template <typename P>
 std::pair<iterator, bool> insert(P&& value) {
 return insert_impl(KeySelect()(value), std::forward(value));
 }

template <typename P>
 iterator insert_hint(const_iterator hint, P&& value) {
 if (hint != cend() &&
 compare_keys(KeySelect()(*hint), KeySelect()(value))) {
 return mutable_iterator(hint);
 }

return insert(std::forward(value)).first;
 }

template <class InputIt>
 void insert(InputIt first, InputIt last) {
 if (std::is_base_of<
 std::forward_iterator_tag,
 typename std::iterator_traits<InputIt>::iterator_category>::value) {
 const auto nb_elements_insert = std::distance(first, last);
 const size_type nb_free_buckets = m_load_threshold - size();
 tsl_oh_assert(m_load_threshold >= size());

if (nb_elements_insert > 0 &&
 nb_free_buckets < size_type(nb_elements_insert)) {
 reserve(size() + size_type(nb_elements_insert));
 }
 }

for (; first != last; ++first) {
      insert(*first);
    }
  }

template <class K, class M>
 std::pair<iterator, bool> insert_or_assign(K&& key, M&& value) {
 auto it = try_emplace(std::forward<K>(key), std::forward<M>(value));
 if (!it.second) {
 it.first.value() = std::forward<M>(value);
 }

return it;
  }

template <class K, class M>
 iterator insert_or_assign(const_iterator hint, K&& key, M&& obj) {
 if (hint != cend() && compare_keys(KeySelect()(*hint), key)) {
 auto it = mutable_iterator(hint);
 it.value() = std::forward<M>(obj);

return it;
    }

return insert_or_assign(std::forward<K>(key), std::forward<M>(obj)).first;
 }

template <class... Args>
 std::pair<iterator, bool> emplace(Args&&... args) {
 return insert(value_type(std::forward<Args>(args)...));
 }

template <class... Args>
 iterator emplace_hint(const_iterator hint, Args&&... args) {
 return insert_hint(hint, value_type(std::forward<Args>(args)...));
 }

template <class K, class... Args>
 std::pair<iterator, bool> try_emplace(K&& key, Args&&... value_args) {
 return insert_impl(
 key, std::piecewise_construct,
 std::forward_as_tuple(std::forward<K>(key)),
 std::forward_as_tuple(std::forward<Args>(value_args)...));
 }

template <class K, class... Args>
 iterator try_emplace_hint(const_iterator hint, K&& key, Args&&... args) {
 if (hint != cend() && compare_keys(KeySelect()(*hint), key)) {
 return mutable_iterator(hint);
 }

return try_emplace(std::forward<K>(key), std::forward<Args>(args)...).first;
 }

/**
 * Here to avoid `template<class K> size_type erase(const K& key)` being used
 * when we use an `iterator` instead of a `const_iterator`.
 */
 iterator erase(iterator pos) { return erase(const_iterator(pos)); }

iterator erase(const_iterator pos) {
    tsl_oh_assert(pos != cend());

const std::size_t index_erase = iterator_to_index(pos);

auto it_bucket = find_key(pos.key(), hash_key(pos.key()));
    tsl_oh_assert(it_bucket != m_buckets_data.end());

erase_value_from_bucket(it_bucket);

/*
     * One element was removed from m_values, due to the left shift the next
     * element is now at the position of the previous element (or end if none).
     */
    return begin() + index_erase;
  }

iterator erase(const_iterator first, const_iterator last) {
    if (first == last) {
      return mutable_iterator(first);
    }

tsl_oh_assert(std::distance(first, last) > 0);
    const std::size_t start_index = iterator_to_index(first);
    const std::size_t nb_values = std::size_t(std::distance(first, last));
    const std::size_t end_index = start_index + nb_values;

// Delete all values
#ifdef TSL_OH_NO_CONTAINER_ERASE_CONST_ITERATOR
    auto next_it = m_values.erase(mutable_iterator(first).m_iterator,
                                  mutable_iterator(last).m_iterator);
#else
    auto next_it = m_values.erase(first.m_iterator, last.m_iterator);
#endif

/*
 * Mark the buckets corresponding to the values as empty and do a backward
 * shift.
 *
 * Also, the erase operation on m_values has shifted all the values on the
 * right of last.m_iterator. Adapt the indexes for these values.
 */
 std::size_t ibucket = 0;
 while (ibucket < m_buckets_data.size()) {
 if (m_buckets[ibucket].empty()) {
 ibucket++;
 } else if (m_buckets[ibucket].index() >= start_index &&
 m_buckets[ibucket].index() < end_index) {
 m_buckets[ibucket].clear();
 backward_shift(ibucket);
 // Don't increment ibucket, backward_shift may have replaced current
 // bucket.
 } else if (m_buckets[ibucket].index() >= end_index) {
 m_buckets[ibucket].set_index(
 index_type(m_buckets[ibucket].index() - nb_values));
 ibucket++;
 } else {
 ibucket++;
 }
 }

return iterator(next_it);
  }

template <class K>
 size_type erase(const K& key) {
 return erase(key, hash_key(key));
 }

template <class K>
 size_type erase(const K& key, std::size_t hash) {
 return erase_impl(key, hash);
 }

void swap(ordered_hash& other) {
    using std::swap;

swap(static_cast<Hash&>(*this), static_cast<Hash&>(other));
 swap(static_cast<KeyEqual&>(*this), static_cast<KeyEqual&>(other));
 swap(m_buckets_data, other.m_buckets_data);
 swap(m_buckets, other.m_buckets);
 swap(m_hash_mask, other.m_hash_mask);
 swap(m_values, other.m_values);
 swap(m_load_threshold, other.m_load_threshold);
 swap(m_max_load_factor, other.m_max_load_factor);
 swap(m_grow_on_next_insert, other.m_grow_on_next_insert);
 }

/*
 * Lookup
 */
 template <class K, class U = ValueSelect,
 typename std::enable_if<has_mapped_type::value>::type* = nullptr>
 typename U::value_type& at(const K& key) {
 return at(key, hash_key(key));
 }

template <class K, class U = ValueSelect,
 typename std::enable_if<has_mapped_type::value>::type* = nullptr>
 typename U::value_type& at(const K& key, std::size_t hash) {
 return const_cast<typename U::value_type&>(
 static_cast<const ordered_hash*>(this)->at(key, hash));
 }

template <class K, class U = ValueSelect,
 typename std::enable_if<has_mapped_type::value>::type* = nullptr>
 const typename U::value_type& at(const K& key) const {
 return at(key, hash_key(key));
 }

template <class K, class U = ValueSelect,
 typename std::enable_if<has_mapped_type::value>::type* = nullptr>
 const typename U::value_type& at(const K& key, std::size_t hash) const {
 auto it = find(key, hash);
 if (it != end()) {
 return it.value();
 } else {
 TSL_OH_THROW_OR_TERMINATE(std::out_of_range, "Couldn't find the key.");
 }
 }

template <class K, class U = ValueSelect,
 typename std::enable_if<has_mapped_type::value>::type* = nullptr>
 typename U::value_type& operator[](K&& key) {
 return try_emplace(std::forward<K>(key)).first.value();
 }

template <class K>
 size_type count(const K& key) const {
 return count(key, hash_key(key));
 }

template <class K>
 size_type count(const K& key, std::size_t hash) const {
 if (find(key, hash) == cend()) {
 return 0;
 } else {
 return 1;
 }
 }

template <class K>
 iterator find(const K& key) {
 return find(key, hash_key(key));
 }

template <class K>
 iterator find(const K& key, std::size_t hash) {
 auto it_bucket = find_key(key, hash);
 return (it_bucket != m_buckets_data.end())
 ? iterator(m_values.begin() + it_bucket->index())
 : end();
 }

template <class K>
 const_iterator find(const K& key) const {
 return find(key, hash_key(key));
 }

template <class K>
 const_iterator find(const K& key, std::size_t hash) const {
 auto it_bucket = find_key(key, hash);
 return (it_bucket != m_buckets_data.cend())
 ? const_iterator(m_values.begin() + it_bucket->index())
 : end();
 }

template <class K>
 bool contains(const K& key) const {
 return contains(key, hash_key(key));
 }

template <class K>
 bool contains(const K& key, std::size_t hash) const {
 return find(key, hash) != cend();
 }

template <class K>
 std::pair<iterator, iterator> equal_range(const K& key) {
 return equal_range(key, hash_key(key));
 }

template <class K>
 std::pair<iterator, iterator> equal_range(const K& key, std::size_t hash) {
 iterator it = find(key, hash);
 return std::make_pair(it, (it == end()) ? it : std::next(it));
 }

template <class K>
 std::pair<const_iterator, const_iterator> equal_range(const K& key) const {
 return equal_range(key, hash_key(key));
 }

template <class K>
 std::pair<const_iterator, const_iterator> equal_range(
 const K& key, std::size_t hash) const {
 const_iterator it = find(key, hash);
 return std::make_pair(it, (it == cend()) ? it : std::next(it));
 }

/*
   * Bucket interface
   */
  size_type bucket_count() const { return m_buckets_data.size(); }

size_type max_bucket_count() const { return m_buckets_data.max_size(); }

/*
   *  Hash policy
   */
  float load_factor() const {
    if (bucket_count() == 0) {
      return 0;
    }

return float(size()) / float(bucket_count());
  }

float max_load_factor() const { return m_max_load_factor; }

void max_load_factor(float ml) {
    m_max_load_factor = clamp(ml, float(MAX_LOAD_FACTOR__MINIMUM),
                              float(MAX_LOAD_FACTOR__MAXIMUM));

m_max_load_factor = ml;
    m_load_threshold = size_type(float(bucket_count()) * m_max_load_factor);
  }

void rehash(size_type count) {
    count = std::max(count,
                     size_type(std::ceil(float(size()) / max_load_factor())));
    rehash_impl(count);
  }

void reserve(size_type count) {
    reserve_space_for_values(count);

count = size_type(std::ceil(float(count) / max_load_factor()));
    rehash(count);
  }

/*
 * Observers
 */
 hasher hash_function() const { return static_cast<const Hash&>(*this); }

key_equal key_eq() const { return static_cast<const KeyEqual&>(*this); }

/*
   * Other
   */
  iterator mutable_iterator(const_iterator pos) {
    return iterator(m_values.begin() + iterator_to_index(pos));
  }

iterator nth(size_type index) {
 tsl_oh_assert(index <= size());
 return iterator(m_values.begin() + index);
 }

const_iterator nth(size_type index) const {
 tsl_oh_assert(index <= size());
 return const_iterator(m_values.cbegin() + index);
 }

const_reference front() const {
    tsl_oh_assert(!empty());
    return m_values.front();
  }

const_reference back() const {
    tsl_oh_assert(!empty());
    return m_values.back();
  }

const values_container_type& values_container() const noexcept {
    return m_values;
  }

template <class U = values_container_type,
 typename std::enable_if<is_vector::value>::type* = nullptr>
 const typename values_container_type::value_type* data() const noexcept {
 return m_values.data();
 }

template <class U = values_container_type,
 typename std::enable_if<is_vector::value>::type* = nullptr>
 size_type capacity() const noexcept {
 return m_values.capacity();
 }

void shrink_to_fit() { m_values.shrink_to_fit(); }

template <typename P>
 std::pair<iterator, bool> insert_at_position(const_iterator pos, P&& value) {
 return insert_at_position_impl(pos.m_iterator, KeySelect()(value),
 std::forward(value));
 }

template <class... Args>
 std::pair<iterator, bool> emplace_at_position(const_iterator pos,
 Args&&... args) {
 return insert_at_position(pos, value_type(std::forward<Args>(args)...));
 }

template <class K, class... Args>
 std::pair<iterator, bool> try_emplace_at_position(const_iterator pos, K&& key,
 Args&&... value_args) {
 return insert_at_position_impl(
 pos.m_iterator, key, std::piecewise_construct,
 std::forward_as_tuple(std::forward<K>(key)),
 std::forward_as_tuple(std::forward<Args>(value_args)...));
 }

void pop_back() {
    tsl_oh_assert(!empty());
    erase(std::prev(end()));
  }

/**
 * Here to avoid `template<class K> size_type unordered_erase(const K& key)`
 * being used when we use a iterator instead of a const_iterator.
 */
 iterator unordered_erase(iterator pos) {
 return unordered_erase(const_iterator(pos));
 }

iterator unordered_erase(const_iterator pos) {
    const std::size_t index_erase = iterator_to_index(pos);
    unordered_erase(pos.key());

/*
     * One element was deleted, index_erase now points to the next element as
     * the elements after the deleted value were shifted to the left in m_values
     * (will be end() if we deleted the last element).
     */
    return begin() + index_erase;
  }

template <class K>
 size_type unordered_erase(const K& key) {
 return unordered_erase(key, hash_key(key));
 }

template <class K>
 size_type unordered_erase(const K& key, std::size_t hash) {
 auto it_bucket_key = find_key(key, hash);
 if (it_bucket_key == m_buckets_data.end()) {
 return 0;
 }

/**
     * If we are not erasing the last element in m_values, we swap
     * the element we are erasing with the last element. We then would
     * just have to do a pop_back() in m_values.
     */
    if (!compare_keys(key, KeySelect()(back()))) {
      auto it_bucket_last_elem =
          find_key(KeySelect()(back()), hash_key(KeySelect()(back())));
      tsl_oh_assert(it_bucket_last_elem != m_buckets_data.end());
      tsl_oh_assert(it_bucket_last_elem->index() == m_values.size() - 1);

using std::swap;
      swap(m_values[it_bucket_key->index()],
           m_values[it_bucket_last_elem->index()]);
      swap(it_bucket_key->index_ref(), it_bucket_last_elem->index_ref());
    }

erase_value_from_bucket(it_bucket_key);

return 1;
  }

template <class Serializer>
 void serialize(Serializer& serializer) const {
 serialize_impl(serializer);
 }

template <class Deserializer>
 void deserialize(Deserializer& deserializer, bool hash_compatible) {
 deserialize_impl(deserializer, hash_compatible);
 }

friend bool operator==(const ordered_hash& lhs, const ordered_hash& rhs) {
    return lhs.m_values == rhs.m_values;
  }

friend bool operator!=(const ordered_hash& lhs, const ordered_hash& rhs) {
    return lhs.m_values != rhs.m_values;
  }

friend bool operator<(const ordered_hash& lhs, const ordered_hash& rhs) {
 return lhs.m_values < rhs.m_values;
 }

friend bool operator<=(const ordered_hash& lhs, const ordered_hash& rhs) {
 return lhs.m_values <= rhs.m_values;
 }

friend bool operator>(const ordered_hash& lhs, const ordered_hash& rhs) {
    return lhs.m_values > rhs.m_values;
  }

friend bool operator>=(const ordered_hash& lhs, const ordered_hash& rhs) {
    return lhs.m_values >= rhs.m_values;
  }

private:
 template <class K>
 std::size_t hash_key(const K& key) const {
 return Hash::operator()(key);
 }

template <class K1, class K2>
 bool compare_keys(const K1& key1, const K2& key2) const {
 return KeyEqual::operator()(key1, key2);
 }

template <class K>
 typename buckets_container_type::iterator find_key(const K& key,
 std::size_t hash) {
 auto it = static_cast<const ordered_hash*>(this)->find_key(key, hash);
 return m_buckets_data.begin() + std::distance(m_buckets_data.cbegin(), it);
 }

/**
 * Return bucket which has the key 'key' or m_buckets_data.end() if none.
 *
 * From the bucket_for_hash, search for the value until we either find an
 * empty bucket or a bucket which has a value with a distance from its ideal
 * bucket longer than the probe length for the value we are looking for.
 */
 template <class K>
 typename buckets_container_type::const_iterator find_key(
 const K& key, std::size_t hash) const {
 for (std::size_t ibucket = bucket_for_hash(hash),
 dist_from_ideal_bucket = 0;
 ; ibucket = next_bucket(ibucket), dist_from_ideal_bucket++) {
 if (m_buckets[ibucket].empty()) {
 return m_buckets_data.end();
 } else if (m_buckets[ibucket].truncated_hash() ==
 bucket_entry::truncate_hash(hash) &&
 compare_keys(
 key, KeySelect()(m_values[m_buckets[ibucket].index()]))) {
 return m_buckets_data.begin() + ibucket;
 } else if (dist_from_ideal_bucket > distance_from_ideal_bucket(ibucket)) {
 return m_buckets_data.end();
 }
 }
 }

void rehash_impl(size_type bucket_count) {
    tsl_oh_assert(bucket_count >=
                  size_type(std::ceil(float(size()) / max_load_factor())));

if (bucket_count > max_bucket_count()) {
      TSL_OH_THROW_OR_TERMINATE(std::length_error,
                                "The map exceeds its maximum size.");
    }

if (bucket_count > 0) {
      bucket_count = round_up_to_power_of_two(bucket_count);
    }

if (bucket_count == this->bucket_count()) {
      return;
    }

buckets_container_type old_buckets(bucket_count);
    m_buckets_data.swap(old_buckets);
    m_buckets = m_buckets_data.empty() ? static_empty_bucket_ptr()
                                       : m_buckets_data.data();
    // Everything should be noexcept from here.

m_hash_mask = (bucket_count > 0) ? (bucket_count - 1) : 0;
    this->max_load_factor(m_max_load_factor);
    m_grow_on_next_insert = false;

for (const bucket_entry& old_bucket : old_buckets) {
      if (old_bucket.empty()) {
        continue;
      }

truncated_hash_type insert_hash = old_bucket.truncated_hash();
      index_type insert_index = old_bucket.index();

for (std::size_t ibucket = bucket_for_hash(insert_hash),
                       dist_from_ideal_bucket = 0;
           ; ibucket = next_bucket(ibucket), dist_from_ideal_bucket++) {
        if (m_buckets[ibucket].empty()) {
          m_buckets[ibucket].set_index(insert_index);
          m_buckets[ibucket].set_hash(insert_hash);
          break;
        }

const std::size_t distance = distance_from_ideal_bucket(ibucket);
        if (dist_from_ideal_bucket > distance) {
          std::swap(insert_index, m_buckets[ibucket].index_ref());
          std::swap(insert_hash, m_buckets[ibucket].truncated_hash_ref());
          dist_from_ideal_bucket = distance;
        }
      }
    }
  }

template <class T = values_container_type,
 typename std::enable_if<is_vector<T>::value>::type* = nullptr>
 void reserve_space_for_values(size_type count) {
 m_values.reserve(count);
 }

template <class T = values_container_type,
 typename std::enable_if<!is_vector<T>::value>::type* = nullptr>
 void reserve_space_for_values(size_type /*count*/) {}

/**
   * Swap the empty bucket with the values on its right until we cross another
   * empty bucket or if the other bucket has a distance_from_ideal_bucket == 0.
   */
  void backward_shift(std::size_t empty_ibucket) noexcept {
    tsl_oh_assert(m_buckets[empty_ibucket].empty());

std::size_t previous_ibucket = empty_ibucket;
    for (std::size_t current_ibucket = next_bucket(previous_ibucket);
         !m_buckets[current_ibucket].empty() &&
         distance_from_ideal_bucket(current_ibucket) > 0;
         previous_ibucket = current_ibucket,
                     current_ibucket = next_bucket(current_ibucket)) {
      std::swap(m_buckets[current_ibucket], m_buckets[previous_ibucket]);
    }
  }

void erase_value_from_bucket(
      typename buckets_container_type::iterator it_bucket) {
    tsl_oh_assert(it_bucket != m_buckets_data.end() && !it_bucket->empty());

m_values.erase(m_values.begin() + it_bucket->index());

/*
     * m_values.erase shifted all the values on the right of the erased value,
     * shift the indexes by -1 in the buckets array for these values.
     */
    if (it_bucket->index() != m_values.size()) {
      shift_indexes_in_buckets(it_bucket->index(), -1);
    }

// Mark the bucket as empty and do a backward shift of the values on the
    // right
    it_bucket->clear();
    backward_shift(
        std::size_t(std::distance(m_buckets_data.begin(), it_bucket)));
  }

/**
   * Go through each value from [from_ivalue, m_values.size()) in m_values and
   * for each bucket corresponding to the value, shift the index by delta.
   *
   * delta must be equal to 1 or -1.
   */
  void shift_indexes_in_buckets(index_type from_ivalue, int delta) noexcept {
    tsl_oh_assert(delta == 1 || delta == -1);

for (std::size_t ivalue = from_ivalue; ivalue < m_values.size(); ivalue++) {
 // All the values in m_values have been shifted by delta. Find the bucket
 // corresponding to the value m_values[ivalue]
 const index_type old_index = static_cast<index_type>(ivalue - delta);

std::size_t ibucket =
          bucket_for_hash(hash_key(KeySelect()(m_values[ivalue])));
      while (m_buckets[ibucket].index() != old_index) {
        ibucket = next_bucket(ibucket);
      }

m_buckets[ibucket].set_index(index_type(ivalue));
    }
  }

template <class K>
 size_type erase_impl(const K& key, std::size_t hash) {
 auto it_bucket = find_key(key, hash);
 if (it_bucket != m_buckets_data.end()) {
 erase_value_from_bucket(it_bucket);

return 1;
    } else {
      return 0;
    }
  }

/**
 * Insert the element at the end.
 */
 template <class K, class... Args>
 std::pair<iterator, bool> insert_impl(const K& key,
 Args&&... value_type_args) {
 const std::size_t hash = hash_key(key);

std::size_t ibucket = bucket_for_hash(hash);
    std::size_t dist_from_ideal_bucket = 0;

while (!m_buckets[ibucket].empty() &&
 dist_from_ideal_bucket <= distance_from_ideal_bucket(ibucket)) {
 if (m_buckets[ibucket].truncated_hash() ==
 bucket_entry::truncate_hash(hash) &&
 compare_keys(key,
 KeySelect()(m_values[m_buckets[ibucket].index()]))) {
 return std::make_pair(begin() + m_buckets[ibucket].index(), false);
 }

ibucket = next_bucket(ibucket);
      dist_from_ideal_bucket++;
    }

if (size() >= max_size()) {
      TSL_OH_THROW_OR_TERMINATE(
          std::length_error, "We reached the maximum size for the hash table.");
    }

if (grow_on_high_load()) {
      ibucket = bucket_for_hash(hash);
      dist_from_ideal_bucket = 0;
    }

m_values.emplace_back(std::forward<Args>(value_type_args)...);
 insert_index(ibucket, dist_from_ideal_bucket,
 index_type(m_values.size() - 1),
 bucket_entry::truncate_hash(hash));

return std::make_pair(std::prev(end()), true);
  }

/**
 * Insert the element before insert_position.
 */
 template <class K, class... Args>
 std::pair<iterator, bool> insert_at_position_impl(
 typename values_container_type::const_iterator insert_position,
 const K& key, Args&&... value_type_args) {
 const std::size_t hash = hash_key(key);

std::size_t ibucket = bucket_for_hash(hash);
    std::size_t dist_from_ideal_bucket = 0;

ibucket = next_bucket(ibucket);
      dist_from_ideal_bucket++;
    }

if (size() >= max_size()) {
      TSL_OH_THROW_OR_TERMINATE(
          std::length_error, "We reached the maximum size for the hash table.");
    }

if (grow_on_high_load()) {
      ibucket = bucket_for_hash(hash);
      dist_from_ideal_bucket = 0;
    }

const index_type index_insert_position =
        index_type(std::distance(m_values.cbegin(), insert_position));

#ifdef TSL_OH_NO_CONTAINER_EMPLACE_CONST_ITERATOR
 m_values.emplace(
 m_values.begin() + std::distance(m_values.cbegin(), insert_position),
 std::forward<Args>(value_type_args)...);
#else
 m_values.emplace(insert_position, std::forward<Args>(value_type_args)...);
#endif

insert_index(ibucket, dist_from_ideal_bucket, index_insert_position,
                 bucket_entry::truncate_hash(hash));

/*
     * The insertion didn't happend at the end of the m_values container,
     * we need to shift the indexes in m_buckets_data.
     */
    if (index_insert_position != m_values.size() - 1) {
      shift_indexes_in_buckets(index_insert_position + 1, 1);
    }

return std::make_pair(iterator(m_values.begin() + index_insert_position),
                          true);
  }

void insert_index(std::size_t ibucket, std::size_t dist_from_ideal_bucket,
                    index_type index_insert,
                    truncated_hash_type hash_insert) noexcept {
    while (!m_buckets[ibucket].empty()) {
      const std::size_t distance = distance_from_ideal_bucket(ibucket);
      if (dist_from_ideal_bucket > distance) {
        std::swap(index_insert, m_buckets[ibucket].index_ref());
        std::swap(hash_insert, m_buckets[ibucket].truncated_hash_ref());

dist_from_ideal_bucket = distance;
      }

ibucket = next_bucket(ibucket);
      dist_from_ideal_bucket++;

if (dist_from_ideal_bucket > REHASH_ON_HIGH_NB_PROBES__NPROBES &&
          !m_grow_on_next_insert &&
          load_factor() >= REHASH_ON_HIGH_NB_PROBES__MIN_LOAD_FACTOR) {
        // We don't want to grow the map now as we need this method to be
        // noexcept. Do it on next insert.
        m_grow_on_next_insert = true;
      }
    }

m_buckets[ibucket].set_index(index_insert);
    m_buckets[ibucket].set_hash(hash_insert);
  }

std::size_t distance_from_ideal_bucket(std::size_t ibucket) const noexcept {
    const std::size_t ideal_bucket =
        bucket_for_hash(m_buckets[ibucket].truncated_hash());

if (ibucket >= ideal_bucket) {
      return ibucket - ideal_bucket;
    }
    // If the bucket is smaller than the ideal bucket for the value, there was a
    // wrapping at the end of the bucket array due to the modulo.
    else {
      return (bucket_count() + ibucket) - ideal_bucket;
    }
  }

std::size_t next_bucket(std::size_t index) const noexcept {
 tsl_oh_assert(index < m_buckets_data.size());

index++;
 return (index < m_buckets_data.size()) ? index : 0;
 }

std::size_t bucket_for_hash(std::size_t hash) const noexcept {
    return hash & m_hash_mask;
  }

std::size_t iterator_to_index(const_iterator it) const noexcept {
    const auto dist = std::distance(cbegin(), it);
    tsl_oh_assert(dist >= 0);

return std::size_t(dist);
  }

/**
   * Return true if the map has been rehashed.
   */
  bool grow_on_high_load() {
    if (m_grow_on_next_insert || size() >= m_load_threshold) {
      rehash_impl(std::max(size_type(1), bucket_count() * 2));
      m_grow_on_next_insert = false;

return true;
    } else {
      return false;
    }
  }

template <class Serializer>
 void serialize_impl(Serializer& serializer) const {
 const slz_size_type version = SERIALIZATION_PROTOCOL_VERSION;
 serializer(version);

const slz_size_type nb_elements = m_values.size();
    serializer(nb_elements);

const slz_size_type bucket_count = m_buckets_data.size();
    serializer(bucket_count);

const float max_load_factor = m_max_load_factor;
    serializer(max_load_factor);

for (const value_type& value : m_values) {
      serializer(value);
    }

for (const bucket_entry& bucket : m_buckets_data) {
      bucket.serialize(serializer);
    }
  }

template <class Deserializer>
 void deserialize_impl(Deserializer& deserializer, bool hash_compatible) {
 tsl_oh_assert(m_buckets_data.empty()); // Current hash table must be empty

const slz_size_type version =
 deserialize_value<slz_size_type>(deserializer);
 // For now we only have one version of the serialization protocol.
 // If it doesn't match there is a problem with the file.
 if (version != SERIALIZATION_PROTOCOL_VERSION) {
 TSL_OH_THROW_OR_TERMINATE(std::runtime_error,
 "Can't deserialize the ordered_map/set. "
 "The protocol version header is invalid.");
 }

const slz_size_type nb_elements =
 deserialize_value<slz_size_type>(deserializer);
 const slz_size_type bucket_count_ds =
 deserialize_value<slz_size_type>(deserializer);
 const float max_load_factor = deserialize_value<float>(deserializer);

if (max_load_factor < MAX_LOAD_FACTOR__MINIMUM ||
 max_load_factor > MAX_LOAD_FACTOR__MAXIMUM) {
 TSL_OH_THROW_OR_TERMINATE(
 std::runtime_error,
 "Invalid max_load_factor. Check that the serializer "
 "and deserializer support floats correctly as they "
 "can be converted implicitly to ints.");
 }

this->max_load_factor(max_load_factor);

if (bucket_count_ds == 0) {
      tsl_oh_assert(nb_elements == 0);
      return;
    }

if (!hash_compatible) {
 reserve(numeric_cast<size_type>(nb_elements,
 "Deserialized nb_elements is too big."));
 for (slz_size_type el = 0; el < nb_elements; el++) {
 insert(deserialize_value<value_type>(deserializer));
 }
 } else {
 m_buckets_data.reserve(numeric_cast<size_type>(
 bucket_count_ds, "Deserialized bucket_count is too big."));
 m_buckets = m_buckets_data.data(),
 m_hash_mask = m_buckets_data.capacity() - 1;

reserve_space_for_values(numeric_cast<size_type>(
 nb_elements, "Deserialized nb_elements is too big."));
 for (slz_size_type el = 0; el < nb_elements; el++) {
 m_values.push_back(deserialize_value<value_type>(deserializer));
 }

for (slz_size_type b = 0; b < bucket_count_ds; b++) {
 m_buckets_data.push_back(bucket_entry::deserialize(deserializer));
 }
 }
 }

static std::size_t round_up_to_power_of_two(std::size_t value) {
    if (is_power_of_two(value)) {
      return value;
    }

if (value == 0) {
      return 1;
    }

--value;
 for (std::size_t i = 1; i < sizeof(std::size_t) * CHAR_BIT; i *= 2) {
 value |= value >> i;
 }

return value + 1;
  }

static constexpr bool is_power_of_two(std::size_t value) {
    return value != 0 && (value & (value - 1)) == 0;
  }

public:
  static const size_type DEFAULT_INIT_BUCKETS_SIZE = 0;
  static constexpr float DEFAULT_MAX_LOAD_FACTOR = 0.75f;

private:
  static constexpr float MAX_LOAD_FACTOR__MINIMUM = 0.1f;
  static constexpr float MAX_LOAD_FACTOR__MAXIMUM = 0.95f;

static const size_type REHASH_ON_HIGH_NB_PROBES__NPROBES = 128;
  static constexpr float REHASH_ON_HIGH_NB_PROBES__MIN_LOAD_FACTOR = 0.15f;

/**
   * Protocol version currenlty used for serialization.
   */
  static const slz_size_type SERIALIZATION_PROTOCOL_VERSION = 1;

/**
   * Return an always valid pointer to an static empty bucket_entry with
   * last_bucket() == true.
   */
  bucket_entry* static_empty_bucket_ptr() {
    static bucket_entry empty_bucket;
    return &empty_bucket;
  }

private:
  buckets_container_type m_buckets_data;

/**
   * Points to m_buckets_data.data() if !m_buckets_data.empty() otherwise points
   * to static_empty_bucket_ptr. This variable is useful to avoid the cost of
   * checking if m_buckets_data is empty when trying to find an element.
   *
   * TODO Remove m_buckets_data and only use a pointer+size instead of a
   * pointer+vector to save some space in the ordered_hash object.
   */
  bucket_entry* m_buckets;

size_type m_hash_mask;

values_container_type m_values;

size_type m_load_threshold;
  float m_max_load_factor;

bool m_grow_on_next_insert;
};

}  // end namespace detail_ordered_hash

}  // end namespace tsl

#endif
/**
 * MIT License
 *
 * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tessil@gmx.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
#ifndef TSL_ORDERED_SET_H
#define TSL_ORDERED_SET_H

#include <cstddef>
#include <cstdint>
#include <deque>
#include <functional>
#include <initializer_list>
#include <memory>
#include <type_traits>
#include <utility>
#include <vector>

namespace tsl {

/**
 * Implementation of an hash set using open addressing with robin hood with
 * backshift delete to resolve collisions.
 *
 * The particularity of this hash set is that it remembers the order in which
 * the elements were added and provide a way to access the structure which
 * stores these values through the 'values_container()' method. The used
 * container is defined by ValueTypeContainer, by default a std::deque is used
 * (grows faster) but a std::vector may be used. In this case the set provides a
 * 'data()' method which give a direct access to the memory used to store the
 * values (which can be useful to communicate with C API's).
 *
 * The Key must be copy constructible and/or move constructible. To use
 * `unordered_erase` it also must be swappable.
 *
 * The behaviour of the hash set is undefined if the destructor of Key throws an
 * exception.
 *
 * By default the maximum size of a set is limited to 2^32 - 1 values, if needed
 * this can be changed through the IndexType template parameter. Using an
 * `uint64_t` will raise this limit to 2^64 - 1 values but each bucket will use
 * 16 bytes instead of 8 bytes in addition to the space needed to store the
 * values.
 *
 * Iterators invalidation:
 * - clear, operator=, reserve, rehash: always invalidate the iterators (also
 * invalidate end()).
 * - insert, emplace, emplace_hint, operator[]: when a std::vector is used as
 * ValueTypeContainer and if size() < capacity(), only end(). Otherwise all the
 * iterators are invalidated if an insert occurs.
 * - erase, unordered_erase: when a std::vector is used as ValueTypeContainer
 * invalidate the iterator of the erased element and all the ones after the
 * erased element (including end()). Otherwise all the iterators are invalidated
 * if an erase occurs.
 */
template <class Key, class Hash = std::hash<Key>,
 class KeyEqual = std::equal_to<Key>,
 class Allocator = std::allocator<Key>,
 class ValueTypeContainer = std::deque<Key, Allocator>,
 class IndexType = std::uint_least32_t>
class ordered_set {
 private:
 template <typename U>
 using has_is_transparent = tsl::detail_ordered_hash::has_is_transparent;

class KeySelect {
   public:
    using key_type = Key;

const key_type& operator()(const Key& key) const noexcept { return key; }

key_type& operator()(Key& key) noexcept { return key; }
  };

using ht = detail_ordered_hash::ordered_hash<Key, KeySelect, void, Hash,
 KeyEqual, Allocator,
 ValueTypeContainer, IndexType>;

public:
  using key_type = typename ht::key_type;
  using value_type = typename ht::value_type;
  using size_type = typename ht::size_type;
  using difference_type = typename ht::difference_type;
  using hasher = typename ht::hasher;
  using key_equal = typename ht::key_equal;
  using allocator_type = typename ht::allocator_type;
  using reference = typename ht::reference;
  using const_reference = typename ht::const_reference;
  using pointer = typename ht::pointer;
  using const_pointer = typename ht::const_pointer;
  using iterator = typename ht::iterator;
  using const_iterator = typename ht::const_iterator;
  using reverse_iterator = typename ht::reverse_iterator;
  using const_reverse_iterator = typename ht::const_reverse_iterator;

using values_container_type = typename ht::values_container_type;

/*
   * Constructors
   */
  ordered_set() : ordered_set(ht::DEFAULT_INIT_BUCKETS_SIZE) {}

explicit ordered_set(size_type bucket_count, const Hash& hash = Hash(),
                       const KeyEqual& equal = KeyEqual(),
                       const Allocator& alloc = Allocator())
      : m_ht(bucket_count, hash, equal, alloc, ht::DEFAULT_MAX_LOAD_FACTOR) {}

ordered_set(size_type bucket_count, const Allocator& alloc)
      : ordered_set(bucket_count, Hash(), KeyEqual(), alloc) {}

ordered_set(size_type bucket_count, const Hash& hash, const Allocator& alloc)
      : ordered_set(bucket_count, hash, KeyEqual(), alloc) {}

explicit ordered_set(const Allocator& alloc)
      : ordered_set(ht::DEFAULT_INIT_BUCKETS_SIZE, alloc) {}

template <class InputIt>
 ordered_set(InputIt first, InputIt last,
 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
 const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual(),
 const Allocator& alloc = Allocator())
 : ordered_set(bucket_count, hash, equal, alloc) {
 insert(first, last);
 }

template <class InputIt>
 ordered_set(InputIt first, InputIt last, size_type bucket_count,
 const Allocator& alloc)
 : ordered_set(first, last, bucket_count, Hash(), KeyEqual(), alloc) {}

template <class InputIt>
 ordered_set(InputIt first, InputIt last, size_type bucket_count,
 const Hash& hash, const Allocator& alloc)
 : ordered_set(first, last, bucket_count, hash, KeyEqual(), alloc) {}

ordered_set(std::initializer_list<value_type> init,
 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
 const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual(),
 const Allocator& alloc = Allocator())
 : ordered_set(init.begin(), init.end(), bucket_count, hash, equal,
 alloc) {}

ordered_set(std::initializer_list<value_type> init, size_type bucket_count,
 const Allocator& alloc)
 : ordered_set(init.begin(), init.end(), bucket_count, Hash(), KeyEqual(),
 alloc) {}

ordered_set(std::initializer_list<value_type> init, size_type bucket_count,
 const Hash& hash, const Allocator& alloc)
 : ordered_set(init.begin(), init.end(), bucket_count, hash, KeyEqual(),
 alloc) {}

ordered_set& operator=(std::initializer_list<value_type> ilist) {
 m_ht.clear();

m_ht.reserve(ilist.size());
    m_ht.insert(ilist.begin(), ilist.end());

return *this;
  }

allocator_type get_allocator() const { return m_ht.get_allocator(); }

/*
   * Iterators
   */
  iterator begin() noexcept { return m_ht.begin(); }
  const_iterator begin() const noexcept { return m_ht.begin(); }
  const_iterator cbegin() const noexcept { return m_ht.cbegin(); }

iterator end() noexcept { return m_ht.end(); }
  const_iterator end() const noexcept { return m_ht.end(); }
  const_iterator cend() const noexcept { return m_ht.cend(); }

reverse_iterator rbegin() noexcept { return m_ht.rbegin(); }
  const_reverse_iterator rbegin() const noexcept { return m_ht.rbegin(); }
  const_reverse_iterator rcbegin() const noexcept { return m_ht.rcbegin(); }

reverse_iterator rend() noexcept { return m_ht.rend(); }
  const_reverse_iterator rend() const noexcept { return m_ht.rend(); }
  const_reverse_iterator rcend() const noexcept { return m_ht.rcend(); }

/*
   * Capacity
   */
  bool empty() const noexcept { return m_ht.empty(); }
  size_type size() const noexcept { return m_ht.size(); }
  size_type max_size() const noexcept { return m_ht.max_size(); }

/*
   * Modifiers
   */
  void clear() noexcept { m_ht.clear(); }

std::pair<iterator, bool> insert(const value_type& value) {
 return m_ht.insert(value);
 }
 std::pair<iterator, bool> insert(value_type&& value) {
 return m_ht.insert(std::move(value));
 }

iterator insert(const_iterator hint, const value_type& value) {
    return m_ht.insert_hint(hint, value);
  }

iterator insert(const_iterator hint, value_type&& value) {
    return m_ht.insert_hint(hint, std::move(value));
  }

template <class InputIt>
 void insert(InputIt first, InputIt last) {
 m_ht.insert(first, last);
 }
 void insert(std::initializer_list<value_type> ilist) {
 m_ht.insert(ilist.begin(), ilist.end());
 }

/**
 * Due to the way elements are stored, emplace will need to move or copy the
 * key-value once. The method is equivalent to
 * insert(value_type(std::forward<Args>(args)...));
 *
 * Mainly here for compatibility with the std::unordered_map interface.
 */
 template <class... Args>
 std::pair<iterator, bool> emplace(Args&&... args) {
 return m_ht.emplace(std::forward<Args>(args)...);
 }

/**
 * Due to the way elements are stored, emplace_hint will need to move or copy
 * the key-value once. The method is equivalent to insert(hint,
 * value_type(std::forward<Args>(args)...));
 *
 * Mainly here for compatibility with the std::unordered_map interface.
 */
 template <class... Args>
 iterator emplace_hint(const_iterator hint, Args&&... args) {
 return m_ht.emplace_hint(hint, std::forward<Args>(args)...);
 }

/**
   * When erasing an element, the insert order will be preserved and no holes
   * will be present in the container returned by 'values_container()'.
   *
   * The method is in O(n), if the order is not important 'unordered_erase(...)'
   * method is faster with an O(1) average complexity.
   */
  iterator erase(iterator pos) { return m_ht.erase(pos); }

/**
   * @copydoc erase(iterator pos)
   */
  iterator erase(const_iterator pos) { return m_ht.erase(pos); }

/**
   * @copydoc erase(iterator pos)
   */
  iterator erase(const_iterator first, const_iterator last) {
    return m_ht.erase(first, last);
  }

/**
   * @copydoc erase(iterator pos)
   */
  size_type erase(const key_type& key) { return m_ht.erase(key); }

/**
   * @copydoc erase(iterator pos)
   *
   * Use the hash value 'precalculated_hash' instead of hashing the key. The
   * hash value should be the same as hash_function()(key). Useful to speed-up
   * the lookup to the value if you already have the hash.
   */
  size_type erase(const key_type& key, std::size_t precalculated_hash) {
    return m_ht.erase(key, precalculated_hash);
  }

/**
 * @copydoc erase(iterator pos)
 *
 * This overload only participates in the overload resolution if the typedef
 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
 * to Key.
 */
 template <
 class K, class KE = KeyEqual,
 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
 size_type erase(const K& key) {
 return m_ht.erase(key);
 }

/**
 * @copydoc erase(const key_type& key, std::size_t precalculated_hash)
 *
 * This overload only participates in the overload resolution if the typedef
 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
 * to Key.
 */
 template <
 class K, class KE = KeyEqual,
 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
 size_type erase(const K& key, std::size_t precalculated_hash) {
 return m_ht.erase(key, precalculated_hash);
 }

void swap(ordered_set& other) { other.m_ht.swap(m_ht); }

/*
   * Lookup
   */
  size_type count(const Key& key) const { return m_ht.count(key); }

/**
   * Use the hash value 'precalculated_hash' instead of hashing the key. The
   * hash value should be the same as hash_function()(key). Useful to speed-up
   * the lookup if you already have the hash.
   */
  size_type count(const Key& key, std::size_t precalculated_hash) const {
    return m_ht.count(key, precalculated_hash);
  }

/**
 * This overload only participates in the overload resolution if the typedef
 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
 * to Key.
 */
 template <
 class K, class KE = KeyEqual,
 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
 size_type count(const K& key) const {
 return m_ht.count(key);
 }

/**
 * @copydoc count(const K& key) const
 *
 * Use the hash value 'precalculated_hash' instead of hashing the key. The
 * hash value should be the same as hash_function()(key). Useful to speed-up
 * the lookup if you already have the hash.
 */
 template <
 class K, class KE = KeyEqual,
 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
 size_type count(const K& key, std::size_t precalculated_hash) const {
 return m_ht.count(key, precalculated_hash);
 }

iterator find(const Key& key) { return m_ht.find(key); }

/**
   * Use the hash value 'precalculated_hash' instead of hashing the key. The
   * hash value should be the same as hash_function()(key). Useful to speed-up
   * the lookup if you already have the hash.
   */
  iterator find(const Key& key, std::size_t precalculated_hash) {
    return m_ht.find(key, precalculated_hash);
  }

const_iterator find(const Key& key) const { return m_ht.find(key); }

/**
   * @copydoc find(const Key& key, std::size_t precalculated_hash)
   */
  const_iterator find(const Key& key, std::size_t precalculated_hash) const {
    return m_ht.find(key, precalculated_hash);
  }

/**
 * This overload only participates in the overload resolution if the typedef
 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
 * to Key.
 */
 template <
 class K, class KE = KeyEqual,
 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
 iterator find(const K& key) {
 return m_ht.find(key);
 }

/**
 * @copydoc find(const K& key)
 *
 * Use the hash value 'precalculated_hash' instead of hashing the key. The
 * hash value should be the same as hash_function()(key). Useful to speed-up
 * the lookup if you already have the hash.
 */
 template <
 class K, class KE = KeyEqual,
 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
 iterator find(const K& key, std::size_t precalculated_hash) {
 return m_ht.find(key, precalculated_hash);
 }

/**
 * @copydoc find(const K& key)
 */
 template <
 class K, class KE = KeyEqual,
 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
 const_iterator find(const K& key) const {
 return m_ht.find(key);
 }

/**
 * @copydoc find(const K& key)
 *
 * Use the hash value 'precalculated_hash' instead of hashing the key. The
 * hash value should be the same as hash_function()(key). Useful to speed-up
 * the lookup if you already have the hash.
 */
 template <
 class K, class KE = KeyEqual,
 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
 const_iterator find(const K& key, std::size_t precalculated_hash) const {
 return m_ht.find(key, precalculated_hash);
 }

bool contains(const Key& key) const { return m_ht.contains(key); }

/**
   * Use the hash value 'precalculated_hash' instead of hashing the key. The
   * hash value should be the same as hash_function()(key). Useful to speed-up
   * the lookup if you already have the hash.
   */
  bool contains(const Key& key, std::size_t precalculated_hash) const {
    return m_ht.contains(key, precalculated_hash);
  }

/**
 * This overload only participates in the overload resolution if the typedef
 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
 * to Key.
 */
 template <
 class K, class KE = KeyEqual,
 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
 bool contains(const K& key) const {
 return m_ht.contains(key);
 }

/**
 * @copydoc contains(const K& key) const
 *
 * Use the hash value 'precalculated_hash' instead of hashing the key. The
 * hash value should be the same as hash_function()(key). Useful to speed-up
 * the lookup if you already have the hash.
 */
 template <
 class K, class KE = KeyEqual,
 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
 bool contains(const K& key, std::size_t precalculated_hash) const {
 return m_ht.contains(key, precalculated_hash);
 }

std::pair<iterator, iterator> equal_range(const Key& key) {
 return m_ht.equal_range(key);
 }

/**
 * Use the hash value 'precalculated_hash' instead of hashing the key. The
 * hash value should be the same as hash_function()(key). Useful to speed-up
 * the lookup if you already have the hash.
 */
 std::pair<iterator, iterator> equal_range(const Key& key,
 std::size_t precalculated_hash) {
 return m_ht.equal_range(key, precalculated_hash);
 }

std::pair<const_iterator, const_iterator> equal_range(const Key& key) const {
 return m_ht.equal_range(key);
 }

/**
 * @copydoc equal_range(const Key& key, std::size_t precalculated_hash)
 */
 std::pair<const_iterator, const_iterator> equal_range(
 const Key& key, std::size_t precalculated_hash) const {
 return m_ht.equal_range(key, precalculated_hash);
 }

/**
 * This overload only participates in the overload resolution if the typedef
 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
 * to Key.
 */
 template <
 class K, class KE = KeyEqual,
 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
 std::pair<iterator, iterator> equal_range(const K& key) {
 return m_ht.equal_range(key);
 }

/**
 * @copydoc equal_range(const K& key)
 *
 * Use the hash value 'precalculated_hash' instead of hashing the key. The
 * hash value should be the same as hash_function()(key). Useful to speed-up
 * the lookup if you already have the hash.
 */
 template <
 class K, class KE = KeyEqual,
 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
 std::pair<iterator, iterator> equal_range(const K& key,
 std::size_t precalculated_hash) {
 return m_ht.equal_range(key, precalculated_hash);
 }

/**
 * @copydoc equal_range(const K& key)
 */
 template <
 class K, class KE = KeyEqual,
 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
 std::pair<const_iterator, const_iterator> equal_range(const K& key) const {
 return m_ht.equal_range(key);
 }

/**
 * @copydoc equal_range(const K& key, std::size_t precalculated_hash)
 */
 template <
 class K, class KE = KeyEqual,
 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
 std::pair<const_iterator, const_iterator> equal_range(
 const K& key, std::size_t precalculated_hash) const {
 return m_ht.equal_range(key, precalculated_hash);
 }

/*
   * Bucket interface
   */
  size_type bucket_count() const { return m_ht.bucket_count(); }
  size_type max_bucket_count() const { return m_ht.max_bucket_count(); }

/*
   *  Hash policy
   */
  float load_factor() const { return m_ht.load_factor(); }
  float max_load_factor() const { return m_ht.max_load_factor(); }
  void max_load_factor(float ml) { m_ht.max_load_factor(ml); }

void rehash(size_type count) { m_ht.rehash(count); }
  void reserve(size_type count) { m_ht.reserve(count); }

/*
   * Observers
   */
  hasher hash_function() const { return m_ht.hash_function(); }
  key_equal key_eq() const { return m_ht.key_eq(); }

/*
   * Other
   */

/**
   * Convert a const_iterator to an iterator.
   */
  iterator mutable_iterator(const_iterator pos) {
    return m_ht.mutable_iterator(pos);
  }

/**
 * Requires index <= size().
 *
 * Return an iterator to the element at index. Return end() if index ==
 * size().
 */
 iterator nth(size_type index) { return m_ht.nth(index); }

/**
   * @copydoc nth(size_type index)
   */
  const_iterator nth(size_type index) const { return m_ht.nth(index); }

/**
   * Return const_reference to the first element. Requires the container to not
   * be empty.
   */
  const_reference front() const { return m_ht.front(); }

/**
   * Return const_reference to the last element. Requires the container to not
   * be empty.
   */
  const_reference back() const { return m_ht.back(); }

/**
 * Only available if ValueTypeContainer is a std::vector. Same as calling
 * 'values_container().data()'.
 */
 template <class U = values_container_type,
 typename std::enable_if<
 tsl::detail_ordered_hash::is_vector::value>::type* = nullptr>
 const typename values_container_type::value_type* data() const noexcept {
 return m_ht.data();
 }

/**
   * Return the container in which the values are stored. The values are in the
   * same order as the insertion order and are contiguous in the structure, no
   * holes (size() == values_container().size()).
   */
  const values_container_type& values_container() const noexcept {
    return m_ht.values_container();
  }

template <class U = values_container_type,
 typename std::enable_if<
 tsl::detail_ordered_hash::is_vector::value>::type* = nullptr>
 size_type capacity() const noexcept {
 return m_ht.capacity();
 }

void shrink_to_fit() { m_ht.shrink_to_fit(); }

/**
 * Insert the value before pos shifting all the elements on the right of pos
 * (including pos) one position to the right.
 *
 * Amortized linear time-complexity in the distance between pos and end().
 */
 std::pair<iterator, bool> insert_at_position(const_iterator pos,
 const value_type& value) {
 return m_ht.insert_at_position(pos, value);
 }

/**
 * @copydoc insert_at_position(const_iterator pos, const value_type& value)
 */
 std::pair<iterator, bool> insert_at_position(const_iterator pos,
 value_type&& value) {
 return m_ht.insert_at_position(pos, std::move(value));
 }

/**
 * @copydoc insert_at_position(const_iterator pos, const value_type& value)
 *
 * Same as insert_at_position(pos, value_type(std::forward<Args>(args)...),
 * mainly here for coherence.
 */
 template <class... Args>
 std::pair<iterator, bool> emplace_at_position(const_iterator pos,
 Args&&... args) {
 return m_ht.emplace_at_position(pos, std::forward<Args>(args)...);
 }

void pop_back() { m_ht.pop_back(); }

/**
   * Faster erase operation with an O(1) average complexity but it doesn't
   * preserve the insertion order.
   *
   * If an erasure occurs, the last element of the map will take the place of
   * the erased element.
   */
  iterator unordered_erase(iterator pos) { return m_ht.unordered_erase(pos); }

/**
   * @copydoc unordered_erase(iterator pos)
   */
  iterator unordered_erase(const_iterator pos) {
    return m_ht.unordered_erase(pos);
  }

/**
   * @copydoc unordered_erase(iterator pos)
   */
  size_type unordered_erase(const key_type& key) {
    return m_ht.unordered_erase(key);
  }

/**
   * @copydoc unordered_erase(iterator pos)
   *
   * Use the hash value 'precalculated_hash' instead of hashing the key. The
   * hash value should be the same as hash_function()(key). Useful to speed-up
   * the lookup if you already have the hash.
   */
  size_type unordered_erase(const key_type& key,
                            std::size_t precalculated_hash) {
    return m_ht.unordered_erase(key, precalculated_hash);
  }

/**
 * @copydoc unordered_erase(iterator pos)
 *
 * This overload only participates in the overload resolution if the typedef
 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
 * to Key.
 */
 template <
 class K, class KE = KeyEqual,
 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
 size_type unordered_erase(const K& key) {
 return m_ht.unordered_erase(key);
 }

/**
 * @copydoc unordered_erase(const K& key)
 *
 * Use the hash value 'precalculated_hash' instead of hashing the key. The
 * hash value should be the same as hash_function()(key). Useful to speed-up
 * the lookup if you already have the hash.
 */
 template <
 class K, class KE = KeyEqual,
 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
 size_type unordered_erase(const K& key, std::size_t precalculated_hash) {
 return m_ht.unordered_erase(key, precalculated_hash);
 }

/**
 * Serialize the set through the `serializer` parameter.
 *
 * The `serializer` parameter must be a function object that supports the
 * following call:
 * - `void operator()(const U& value);` where the types `std::uint64_t`,
 * `float` and `Key` must be supported for U.
 *
 * The implementation leaves binary compatibility (endianness, IEEE 754 for
 * floats, ...) of the types it serializes in the hands of the `Serializer`
 * function object if compatibility is required.
 */
 template <class Serializer>
 void serialize(Serializer& serializer) const {
 m_ht.serialize(serializer);
 }

/**
 * Deserialize a previously serialized set through the `deserializer`
 * parameter.
 *
 * The `deserializer` parameter must be a function object that supports the
 * following calls:
 * - `template<typename U> U operator()();` where the types `std::uint64_t`,
 * `float` and `Key` must be supported for U.
 *
 * If the deserialized hash set type is hash compatible with the serialized
 * set, the deserialization process can be sped up by setting
 * `hash_compatible` to true. To be hash compatible, the Hash and KeyEqual
 * must behave the same way than the ones used on the serialized map. The
 * `std::size_t` must also be of the same size as the one on the platform used
 * to serialize the map, the same apply for `IndexType`. If these criteria are
 * not met, the behaviour is undefined with `hash_compatible` sets to true.
 *
 * The behaviour is undefined if the type `Key` of the `ordered_set` is not
 * the same as the type used during serialization.
 *
 * The implementation leaves binary compatibility (endianness, IEEE 754 for
 * floats, size of int, ...) of the types it deserializes in the hands of the
 * `Deserializer` function object if compatibility is required.
 */
 template <class Deserializer>
 static ordered_set deserialize(Deserializer& deserializer,
 bool hash_compatible = false) {
 ordered_set set(0);
 set.m_ht.deserialize(deserializer, hash_compatible);

return set;
  }

friend bool operator==(const ordered_set& lhs, const ordered_set& rhs) {
 return lhs.m_ht == rhs.m_ht;
 }
 friend bool operator!=(const ordered_set& lhs, const ordered_set& rhs) {
 return lhs.m_ht != rhs.m_ht;
 }
 friend bool operator<(const ordered_set& lhs, const ordered_set& rhs) {
 return lhs.m_ht < rhs.m_ht;
 }
 friend bool operator<=(const ordered_set& lhs, const ordered_set& rhs) {
 return lhs.m_ht <= rhs.m_ht;
 }
 friend bool operator>(const ordered_set& lhs, const ordered_set& rhs) {
 return lhs.m_ht > rhs.m_ht;
 }
 friend bool operator>=(const ordered_set& lhs, const ordered_set& rhs) {
 return lhs.m_ht >= rhs.m_ht;
 }

friend void swap(ordered_set& lhs, ordered_set& rhs) { lhs.swap(rhs); }

private:
  ht m_ht;
};

}  // end namespace tsl

#endif

#include <iostream>
#include <benchmark/benchmark.h>
static inline uint64_t xor_shift96() { /* A George Marsaglia generator, period 2^96-1 */
 static uint64_t x = 123456789, y = 362436069, z = 521288629;
 uint64_t t;

x ^= x << 16;
 x ^= x >> 5;
 x ^= x << 1;

t = x;
    x = y;
    y = z;

z = t ^ x ^ y;
    return z;
}

static inline uint64_t _random() {
    return xor_shift96();
}

template<class M>
static void BenchOrderSetInt(benchmark::State &state) {
 M m;
 for (auto i = 0; i < 65536; i++) {
 m.insert(i);
 }
 for (auto _ : state) {
 auto c = m.find(_random() % 65536);
 benchmark::DoNotOptimize(c);
 }
}

BENCHMARK_TEMPLATE(BenchOrderSetInt, std::set<int>);
BENCHMARK_TEMPLATE(BenchOrderSetInt, tsl::ordered_set<int>);

template<class M>
static void BenchOrderSetString(benchmark::State &state) {
 M m;
 std::vector<std::string> keys(65536);
 for (auto i = 0; i < 65536; i++) {
 keys[i] = std::to_string(_random() % 65536);
 auto sKey = std::to_string(i);
 m.insert(sKey);
 } 
 for (auto _ : state) {
 auto kIndex = _random() % 65536;
 auto c = m.find(keys[kIndex].c_str());
 benchmark::DoNotOptimize(c);
 }
}

BENCHMARK_TEMPLATE(BenchOrderSetString, std::set<std::string>);
BENCHMARK_TEMPLATE(BenchOrderSetString, tsl::ordered_set<std::string>);

int main(int argc, char **argv) {
    benchmark::Initialize(&argc, argv);
    benchmark::RunSpecifiedBenchmarks();
    return 0;
}