Skip to content

Instantly share code, notes, and snippets.

@Mukundan314
Created September 30, 2024 09:06
Show Gist options
  • Save Mukundan314/27b313fb91d426098bb25d750ffc5e2f to your computer and use it in GitHub Desktop.
Save Mukundan314/27b313fb91d426098bb25d750ffc5e2f to your computer and use it in GitHub Desktop.
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{}; }
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment