sl.cpp

template <class Key, class Compare = std::less<Key>> class InsertionSet {
private:
  constexpr static std::size_t block_size = 700;

  std::vector<Key> macro;
  std::vector<std::vector<Key>> micros;
  std::size_t _size;

public:
  using key_type = Key;
  using value_type = Key;
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;
  using key_compare = Compare;
  using value_compare = Compare;
  // using allocator_type = Allocator;
  using reference = value_type &;
  using const_reference = const value_type &;
  // using pointer = std::allocator_traits<Allocator>::pointer
  // using const_pointer = std::allocator_traits<Allocator>::const_pointer

  class iterator {
  private:
    typename std::vector<std::vector<Key>>::const_iterator it_micros;
    typename std::vector<Key>::const_iterator it_micro;

    iterator(typename std::vector<std::vector<Key>>::const_iterator _it_micros,
             typename std::vector<Key>::const_iterator _it_micro)
        : it_micros(_it_micros), it_micro(_it_micro) {
      while (it_micro == it_micros->end())
        it_micro = (++it_micros)->begin();
    }

    friend InsertionSet;

  public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = const Key;
    using difference_type = std::ptrdiff_t;
    using pointer = const Key *;
    using reference = const Key &;

    iterator &operator++() {
      ++it_micro;
      while (it_micro == it_micros->end())
        it_micro = (++it_micros)->begin();
      return *this;
    }

    iterator operator++(int) {
      iterator tmp = *this;
      ++*this;
      return tmp;
    }

    iterator &operator--() {
      while (it_micro == it_micros->begin())
        it_micro = (--it_micros)->end();
      --it_micro;
      return *this;
    }

    iterator operator--(int) {
      iterator tmp = *this;
      --*this;
      return tmp;
    }

    bool operator==(iterator other) const {
      return it_micros == other.it_micros && it_micro == other.it_micro;
    }

    bool operator!=(iterator other) const { return !(*this == other); }

    value_type operator*() const { return *it_micro; }
  };

  using const_iterator = iterator;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;

  InsertionSet() : _size(0) { micros = {{}, {0}}; }

  template <class InputIt>
  InsertionSet(InputIt first, InputIt last) : _size(0) {
    micros = {{}, {0}};
    insert(first, last);
  }

  // Iterators

  iterator begin() const noexcept {
    return iterator(micros.begin(), micros[0].begin());
  }

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

  iterator end() const noexcept {
    return iterator(micros.end() - 1, micros.back().begin());
  }

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

  reverse_iterator rbegin() const noexcept { return reverse_iterator(end()); }

  reverse_iterator crbegin() const noexcept { return rbegin(); }

  reverse_iterator rend() const noexcept { return reverse_iterator(begin()); }

  reverse_iterator crend() const noexcept { return rend(); }

  // Capacity

  bool empty() const noexcept { return _size == 0; }

  size_type size() const noexcept { return _size; }

  size_type max_size() const noexcept {
    return std::numeric_limits<difference_type>::max();
  }

  // Modifiers

  void clear() noexcept {
    for (auto micro : micros)
      micro.clear();
    _size = 0;
  }

  iterator insert(const value_type &value) {
    return insert(std::move(value_type(value)));
  }

  iterator insert(value_type &&value) {
    typename std::vector<Key>::iterator it_macro =
        std::lower_bound(macro.begin(), macro.end(), value, Compare{});
    typename std::vector<std::vector<Key>>::iterator it_micros =
        micros.begin() + (it_macro - macro.begin());
    typename std::vector<Key>::iterator it_micro =
        it_micros->insert(std::upper_bound(it_micros->begin(), it_micros->end(),
                                           value, Compare{}),
                          std::move(value));

    _size++;

    if (it_micros->size() == block_size) {
      macro.insert(it_macro, (*it_micros)[block_size >> 1]);
      it_micros =
          micros.insert(it_micros + 1,
                        std::vector<Key>(it_micros->begin() + (block_size >> 1),
                                         it_micros->end())) -
          1;

      int idx = it_micro - it_micros->begin();
      it_micros->resize(block_size >> 1);

      if (idx >= block_size >> 1)
        it_micro = (++it_micros)->begin() + idx - (block_size >> 1);
    }

    return iterator(it_micros, it_micro);
  }

  iterator insert(iterator pos, const value_type &value) {
    insert(pos, std::move(value_type(value)));
  }

  iterator insert(iterator pos, value_type &&value) {
    // TODO: use hint
    insert(std::move(value));
  }

  template <class InputIt> void insert(InputIt first, InputIt last) {
    for (; first != last; ++first)
      insert(*first);
  }

  void insert(std::initializer_list<value_type> ilist) {
    insert(ilist.begin(), ilist.end());
  }

  template <class... Args> iterator emplace(Args &&...args) { /* TODO */ }

  template <class... Args>
  iterator emplace_hint(iterator hint, Args &&...args) { /* TODO */ }

  iterator erase(iterator pos) {
    std::ptrdiff_t micros_idx = pos.it_micros - micros.begin();
    pos.it_micro = micros[micros_idx].erase(pos.it_micro);

    if (micros_idx == 0 || !pos.it_micros->empty())
      return pos;

    macro.erase(macro.begin() + micros_idx - 1);
    pos.it_micros = micros.erase(pos.it_micros);
    pos.it_micro = pos.it_micros->begin();

    return pos;
  }

  iterator erase(iterator first, iterator last) { /* TODO */ }

  size_type erase(const Key &key) { /* TODO */ }

  void swap(InsertionSet &other) { /* TODO */ }

  // Lookup

  size_type count(const Key &key) const { /* TODO */ }

  iterator find(const Key &key) const {
    iterator it = lower_bound(key);
    return it == end() || *it == key ? it : end();
  }

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

  iterator lower_bound(const Key &key) const {
    typename std::vector<Key>::const_iterator it_macro =
        std::lower_bound(macro.begin(), macro.end(), key, Compare{});
    typename std::vector<std::vector<Key>>::const_iterator it_micros =
        micros.begin() + (it_macro - macro.begin());
    return iterator(
        it_micros,
        std::lower_bound(it_micros->begin(), it_micros->end(), key, Compare{}));
  }

  iterator upper_bound(const Key &key) const {
    typename std::vector<Key>::const_iterator it_macro =
        std::upper_bound(macro.begin(), macro.end(), key, Compare{});
    typename std::vector<std::vector<Key>>::const_iterator it_micros =
        micros.begin() + (it_macro - macro.begin());
    return iterator(
        it_micros,
        std::upper_bound(it_micros->begin(), it_micros->end(), key, Compare{}));
  }

  // Observers

  key_compare key_comp() const { return Compare{}; }

  value_compare value_comp() const { return Compare{}; }
};