12 #ifndef CPROVER_UTIL_DENSE_INTEGER_MAP_H
13 #define CPROVER_UTIL_DENSE_INTEGER_MAP_H
16 #include <unordered_set>
28 return std::forward<T>(t);
52 template <
class K,
class V,
class KeyToDenseInteger =
identity_functort>
91 auto key_integer = KeyToDenseInteger{}(key);
92 INVARIANT(((int64_t)key_integer) >=
offset,
"index should be in range");
93 auto ret = (std::size_t)key_integer - (std::size_t)
offset;
117 template <
class UnderlyingIterator,
class UnderlyingValue>
143 typename backing_storet::const_iterator,
144 const typename backing_storet::value_type>()
const
179 UnderlyingIterator
advance(UnderlyingIterator it)
187 auto iterator_pos = (std::size_t)std::distance(
189 (
typename backing_storet::const_iterator)it);
208 typename backing_storet::iterator,
209 typename backing_storet::value_type>
215 typename backing_storet::const_iterator,
216 const typename backing_storet::value_type>
230 template <
typename Iter>
235 "setup_for_keys must only be called on a newly-constructed container");
237 int64_t highest_key = std::numeric_limits<int64_t>::min();
238 int64_t lowest_key = std::numeric_limits<int64_t>::max();
239 std::unordered_set<int64_t> seen_keys;
240 for(Iter it = first; it != last; ++it)
242 int64_t integer_key = (int64_t)KeyToDenseInteger{}(*it);
243 highest_key = std::max(integer_key, highest_key);
244 lowest_key = std::min(integer_key, lowest_key);
246 seen_keys.insert(integer_key).second,
247 "keys for use in dense_integer_mapt must be unique");
250 if(highest_key < lowest_key)
256 std::size_t map_size = (std::size_t)((highest_key - lowest_key) + 1);
259 "dense_integer_mapt size should fit in std::size_t");
261 map_size <= std::numeric_limits<std::size_t>::max(),
262 "dense_integer_mapt size should fit in std::size_t");
264 map.resize(map_size);
265 for(Iter it = first; it != last; ++it)
273 const V &
at(
const K &key)
const
277 return map.at(index).second;
283 return map.at(index).second;
290 return map.at(index).second;
293 std::pair<iterator, bool>
insert(
const std::pair<const K, V> &pair)
297 static_cast<typename backing_storet::iterator::difference_type
>(index);
298 iterator it{std::next(
map.begin(), signed_index), *
this};
305 map.at(index).second = pair.second;
310 std::size_t
count(
const K &key)
const
UnderlyingValue value_type
std::forward_iterator_tag iterator_category
reference operator*() const
UnderlyingValue & reference
UnderlyingIterator underlying_iterator
self_typet operator++(int junk)
iterator_templatet< UnderlyingIterator, UnderlyingValue > self_typet
UnderlyingValue * pointer
iterator_templatet(UnderlyingIterator it, const map_typet &underlying_map)
bool operator==(const self_typet &rhs) const
bool operator!=(const self_typet &rhs) const
dense_integer_mapt< K, V, KeyToDenseInteger > map_typet
const map_typet & underlying_map
UnderlyingIterator skip_unset_values(UnderlyingIterator it)
pointer operator->() const
UnderlyingIterator advance(UnderlyingIterator it)
std::ptrdiff_t difference_type
A map type that is backed by a vector, which relies on the ability to (a) see the keys that might be ...
void setup_for_keys(Iter first, Iter last)
Set the keys that are allowed to be used in this container.
const_iterator cbegin() const
void mark_index_set(std::size_t index)
std::vector< K > possible_keyst
Type of the container returned by possible_keys.
iterator_templatet< typename backing_storet::const_iterator, const typename backing_storet::value_type > const_iterator
const iterator.
const possible_keyst & possible_keys() const
possible_keyst possible_keys_vector
V & operator[](const K &key)
std::size_t count(const K &key) const
std::pair< iterator, bool > insert(const std::pair< const K, V > &pair)
iterator_templatet< typename backing_storet::iterator, typename backing_storet::value_type > iterator
iterator.
bool index_is_set(std::size_t index) const
const_iterator cend() const
std::size_t key_to_index(const K &key) const
std::vector< std::pair< K, V > > backing_storet
const_iterator end() const
const V & at(const K &key) const
const_iterator begin() const
std::vector< bool > value_set
Identity functor. When we use C++20 this can be replaced with std::identity.
constexpr T && operator()(T &&t) const