KSS Utility
C++ general utilities
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends
sequentialmap.hpp
Go to the documentation of this file.
1 //
2 // sequentialmap.hpp
3 // kssutil
4 //
5 // Created by Steven W. Klassen on 2013-04-04.
6 // Copyright (c) 2013 Klassen Software Solutions. All rights reserved.
7 // Licensing follows the MIT License.
8 //
9 
15 #ifndef kssutil_sequentialmap_hpp
16 #define kssutil_sequentialmap_hpp
17 
18 #include <algorithm>
19 #include <cassert>
20 #include <functional>
21 #include <iterator>
22 #include <limits>
23 #include <map>
24 #include <memory>
25 #include <stdexcept>
26 #include <utility>
27 #include <vector>
28 
29 namespace kss { namespace util { namespace containers {
30 
44  template <class Key, class T, class Compare = std::less<Key>,
45  class Alloc = std::allocator<std::pair<Key, T> >,
46  class MAlloc = std::allocator<std::pair<const Key, size_t> > >
47  class SequentialMap {
48  public:
49 
50  // MARK: The standard type definitions.
51  using key_type = Key;
52  using mapped_type = T;
53  using value_type = std::pair<Key, T>;
54  using key_compare = Compare;
55  using allocator_type = Alloc;
56  using m_allocator_type = MAlloc;
57  using reference = typename allocator_type::reference;
58  using const_reference = typename allocator_type::const_reference;
59  using pointer = typename allocator_type::pointer;
60  using const_pointer = typename allocator_type::const_pointer;
61  using iterator = typename std::vector<value_type, Alloc>::iterator;
62  using const_iterator = typename std::vector<value_type, Alloc>::const_iterator;
63  using reverse_iterator = std::reverse_iterator<iterator>;
64  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
65  using difference_type = typename std::iterator_traits<iterator>::difference_type;
66  using size_type = size_t;
67 
68  class value_compare;
69 
70 
71  // MARK: Constructors
72  explicit SequentialMap(const key_compare& comp = key_compare(),
73  const allocator_type& talloc = allocator_type(),
74  const m_allocator_type& malloc = m_allocator_type())
75  {
76  // postconditions
77  assert(_vec.empty());
78  assert(_map.empty());
79  }
80 
81  template <class InputIterator>
82  SequentialMap(InputIterator first, InputIterator last,
83  const key_compare& comp = key_compare(),
84  const allocator_type& alloc = allocator_type())
85  {
86  insert(first, last);
87 
88  // postconditions
89  assert(_vec.size() == _map.size());
90  }
91 
92  SequentialMap(const SequentialMap&) = default;
93  SequentialMap(SequentialMap&&) = default;
94 
95  ~SequentialMap() = default;
96 
97  SequentialMap& operator=(const SequentialMap& x) = default;
99 
100  // MARK: Iterators
101  iterator begin() noexcept { return _vec.begin(); }
102  const_iterator begin() const noexcept { return _vec.begin(); }
103  iterator end() noexcept { return _vec.end(); }
104  const_iterator end() const noexcept { return _vec.end(); }
105  reverse_iterator rbegin() noexcept { return _vec.rbegin(); }
106  const_reverse_iterator rbegin() const noexcept { return _vec.rbegin(); }
107  reverse_iterator rend() noexcept { return _vec.rend(); }
108  const_reverse_iterator rend() const noexcept { return _vec.rend(); }
109  const_iterator cbegin() const noexcept { return _vec.begin(); }
110  const_iterator cend() const noexcept { return _vec.end(); }
111  const_reverse_iterator crbegin() const noexcept { return _vec.rbegin(); }
112  const_reverse_iterator crend() const noexcept { return _vec.rend(); }
113 
114 
115  // MARK: Capacity
116  bool empty() const noexcept { return _map.empty(); }
117  size_type size() const noexcept { return _map.size(); }
118  size_type max_size() const noexcept { return std::min(_map.max_size(), _vec.max_size()); }
119 
120 
121  // MARK: Element access
123  // preconditions
124  assert(_vec.size() == _map.size());
125 
126  iterator it = find(k);
127  if (it == end()) {
128  std::pair<iterator, bool> p = insert(std::make_pair(k, mapped_type()));
129  it = p.first;
130  }
131 
132  // postconditions
133  assert(_vec.size() == _map.size());
134  return it->second;
135  }
136 
137  mapped_type& at(const key_type& k) {
138  // preconditions
139  assert(_vec.size() == _map.size());
140 
141  iterator it = find(k);
142  if (it == end()) {
143  throw std::out_of_range("the given key is not found in the map");
144  }
145 
146  // postconditions
147  assert(_vec.size() == _map.size());
148  return it->second;
149  }
150 
151  const mapped_type& at(const key_type& k) const {
152  // preconditions
153  assert(_vec.size() == _map.size());
154 
155  const_iterator it = find(k);
156  if (it == end()) {
157  throw std::out_of_range("the given key is not found in the map");
158  }
159 
160  // postconditions
161  assert(_vec.size() == _map.size());
162  return it->second;
163  }
164 
165 
166  // MARK: Modifiers
167  std::pair<iterator, bool> insert(const value_type& val) {
168  // preconditions
169  assert(_vec.size() == _map.size());
170 
171  bool wasInserted = false;
172  iterator it = find(val.first);
173  if (it == end()) {
174  it = _vec.insert(_vec.end(), val);
175  _map.insert(std::make_pair(val.first, _vec.size()-1));
176  wasInserted = true;
177  }
178 
179  // postconditions
180  assert(_vec.size() == _map.size());
181  return std::make_pair(it, wasInserted);
182  }
183 
184  iterator insert(iterator position, const value_type& val) {
185  return insert(val).first;
186  }
187 
188  template <class InputIterator>
189  void insert(InputIterator first, InputIterator last) {
190  // preconditions
191  assert(_vec.size() == _map.size());
192 
193  for (InputIterator it = first; it != last; ++it) {
194  insert(*it);
195  }
196 
197  // postconditions
198  assert(_vec.size() == _map.size());
199  }
200 
201  // Note that invalid_argument is thrown if first and last are not in
202  // the map or are not in the correct order. This differs from
203  // map::erase where the behaviour is undefined.
204  void erase(iterator position) {
205  erase(position, position+1);
206  }
207 
209  // preconditions
210  assert(_vec.size() == _map.size());
211 
212  size_type numErased { 0 };
213  iterator it = find(k);
214  if (it != end()) {
215  erase(it);
216  ++numErased;
217  }
218 
219  // postconditions
220  assert(_vec.size() == _map.size());
221  return numErased;
222  }
223 
224  // Note that invalid_argument is thrown if first and last are not in
225  // the map or are not in the correct order. This differs from
226  // map::erase where the behaviour is undefined.
227  void erase(iterator first, iterator last) {
228  // preconditions
229  assert(first >= begin());
230  assert(last >= first);
231  assert(_vec.size() == _map.size());
232 
233  difference_type i = first - begin();
234  difference_type n = last - first;
235  if (i < 0 || n < 0) {
236  throw std::invalid_argument("iterator(s) are not valid for this SequentialMap");
237  }
238 
239  // Need to remove the items from both _vec and _map, then reduce
240  // the indices in _map for all items >= i by n.
241  for (iterator it = first; it != last; ++it) {
242  _map.erase(it->first);
243  }
244  _vec.erase(first, last);
245  for (typename std::map<Key, size_t, Compare, MAlloc>::iterator it = _map.begin(), stop = _map.end(); it != stop; ++it) {
246  if (it->second >= size_type(i)) {
247  it->second -= size_type(n);
248  }
249  }
250 
251  // postconditions
252  assert(_vec.size() == _map.size());
253  }
254 
255  void swap(SequentialMap& x) {
256  _vec.swap(x._vec);
257  _map.swap(x._map);
258 
259  // postconditions
260  assert(_vec.size() == _map.size());
261  assert(x._vec.size() == x._map.size());
262  }
263 
264  void clear() noexcept {
265  _vec.clear();
266  _map.clear();
267 
268  // postconditions
269  assert(_vec.empty());
270  assert(_map.empty());
271  }
272 
273 
274  // MARK: Observers
275  key_compare key_comp() const { return Compare(); }
276  value_compare value_comp() const { return value_compare(Compare()); }
277  allocator_type get_allocator() const noexcept { _vec.get_allocator(); }
278  m_allocator_type get_m_allocator() const noexcept { _map.get_allocator(); }
279 
280 
281  // MARK: Operations
282  iterator find(const key_type& k) {
283  // preconditions
284  assert(_vec.size() == _map.size());
285 
286  iterator retIt = end();
287  typename std::map<Key, size_t, Compare, MAlloc>::iterator it = _map.find(k);
288  if (it != _map.end()) {
289  size_t maxIncr = std::numeric_limits<difference_type>::max();
290  size_t remain = it->second;
291  retIt = _vec.begin();
292  while (remain > maxIncr) {
293  retIt += difference_type(maxIncr);
294  remain -= maxIncr;
295  }
296  retIt += difference_type(remain);
297  }
298 
299  // postconditions
300  assert(_vec.size() == _map.size());
301  return retIt;
302  }
303 
304  const_iterator find(const key_type& k) const {
305  // preconditions
306  assert(_vec.size() == _map.size());
307 
308  const_iterator retIt = end();
309  typename std::map<Key, size_t, Compare, MAlloc>::const_iterator it = _map.find(k);
310  if (it != _map.end()) {
311  size_t maxIncr = std::numeric_limits<difference_type>::max();
312  size_t remain = it->second;
313  retIt = _vec.begin();
314  while (remain > maxIncr) {
315  retIt += difference_type(maxIncr);
316  remain -= maxIncr;
317  }
318  retIt += difference_type(remain);
319  }
320 
321  // postconditions
322  assert(_vec.size() == _map.size());
323  return retIt;
324  }
325 
326  size_type count(const key_type& k) const {
327  assert(_vec.size() == _map.size());
328  return (_map.find(k) == _map.end() ? 0 : 1);
329  }
330 
332  friend class SequentialMap;
333  protected:
334  Compare comp;
335  value_compare(Compare c) : comp(c) {}
336  public:
337  typedef bool result_type;
340  bool operator() (const value_type& x, const value_type& y) const { return comp(x.first, y.first); }
341  };
342 
343  private:
344  std::vector<std::pair<Key, T>, Alloc> _vec;
345  std::map<Key, size_t, Compare, MAlloc> _map;
346  };
347 
348 
349  template <class Key, class T, class Compare, class Alloc, class MAlloc>
352  {
353  x.swap(y);
354  }
355 
356 }}}
357 
358 #endif
std::reverse_iterator< const_iterator > const_reverse_iterator
bool operator()(const value_type &x, const value_type &y) const
typename std::vector< value_type, Alloc >::const_iterator const_iterator
const_iterator end() const noexcept
const_iterator cbegin() const noexcept
typename allocator_type::const_pointer const_pointer
reverse_iterator rend() noexcept
const_iterator find(const key_type &k) const
void swap(CircularArray< T, A > &x, CircularArray< T, A > &y)
typename allocator_type::reference reference
const_reverse_iterator crend() const noexcept
std::reverse_iterator< iterator > reverse_iterator
const_reverse_iterator rend() const noexcept
typename std::vector< value_type, Alloc >::iterator iterator
iterator insert(iterator position, const value_type &val)
const_iterator begin() const noexcept
m_allocator_type get_m_allocator() const noexcept
void erase(iterator first, iterator last)
mapped_type & operator[](const key_type &k)
Combination of a list and a map.
size_type size() const noexcept
mapped_type & at(const key_type &k)
const mapped_type & at(const key_type &k) const
size_type count(const key_type &k) const
const_iterator cend() const noexcept
iterator find(const key_type &k)
const_reverse_iterator rbegin() const noexcept
typename allocator_type::pointer pointer
std::pair< iterator, bool > insert(const value_type &val)
const_reverse_iterator crbegin() const noexcept
size_type erase(const key_type &k)
allocator_type get_allocator() const noexcept
SequentialMap(const key_compare &comp=key_compare(), const allocator_type &talloc=allocator_type(), const m_allocator_type &malloc=m_allocator_type())
reverse_iterator rbegin() noexcept
void insert(InputIterator first, InputIterator last)
typename allocator_type::const_reference const_reference
SequentialMap(InputIterator first, InputIterator last, const key_compare &comp=key_compare(), const allocator_type &alloc=allocator_type())
typename std::iterator_traits< iterator >::difference_type difference_type
SequentialMap & operator=(const SequentialMap &x)=default
size_type max_size() const noexcept