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