3 #include <boost/optional.hpp>
14 template <
typename Key,
typename Value>
18 static_assert(std::is_unsigned<Key>::value,
19 "sparse-set: requires unsigned indexes");
26 set_max_size(max_size);
29 void set_max_size(
size_t max_size)
31 sparse_.resize(max_size);
34 template <
typename K,
typename V>
35 bool emplace(K&& k,
V&&
v)
37 return insert(std::make_pair(k,
v));
44 bool insert(
const std::pair<Key, Value>& p)
50 if (sparse_.size() <= p.first)
51 sparse_.resize(p.first + 1);
52 if (curr_ < dense_.size())
56 sparse_[p.first] = curr_;
64 return (k < sparse_.capacity()
66 && dense_[sparse_[k]].first == k);
72 Value& operator[](Key k)
76 return dense_[sparse_[k]].second;
86 Key last = dense_[curr_ - 1].first;
87 dense_[sparse_[k]].first = last;
88 sparse_[last] = sparse_[k];
101 return dense_.begin();
106 return dense_.begin() + curr_;
111 return dense_.begin();
116 return dense_.begin() + curr_;
121 std::vector<std::pair<Key, Value>> dense_;
122 std::vector<Key> sparse_;
126 template <
typename Key,
typename Value>
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
#define V(S)
Display S and its value.
Sparse Map implementation.