map_vector.h
Go to the documentation of this file.
1 #ifndef cetlib_map_vector_h
2 #define cetlib_map_vector_h
3 
4 // ======================================================================
5 // map_vector: A map mimicking a sparse vector interface
6 //
7 // Integer subscripting is unsupported and yields a compilation failure.
8 // ======================================================================
9 
10 #include "cetlib_except/exception.h"
11 
12 #include <algorithm>
13 #include <iosfwd>
14 #include <vector>
15 
16 namespace cet {
17  class map_vector_key;
18 
19  bool operator==(map_vector_key const&, map_vector_key const&) noexcept;
20  bool operator!=(map_vector_key const&, map_vector_key const&) noexcept;
21  bool operator<(map_vector_key const&, map_vector_key const&) noexcept;
22  bool operator>(map_vector_key const&, map_vector_key const&) noexcept;
23  bool operator<=(map_vector_key const&, map_vector_key const&) noexcept;
24  bool operator>=(map_vector_key const&, map_vector_key const&) noexcept;
25 
26  std::ostream& operator<<(std::ostream&, map_vector_key const&);
27 
28  template <class Value>
29  class map_vector;
30 }
31 
32 // ======================================================================
33 
35 public:
36  // c'tors:
37  constexpr map_vector_key() noexcept : key_(-1l) {}
38  explicit map_vector_key(int key);
39  constexpr explicit map_vector_key(unsigned const key) noexcept : key_{key} {}
40  constexpr explicit map_vector_key(unsigned long key) noexcept;
41 
42  // observers:
43  unsigned long
44  asInt() const noexcept
45  {
46  return key_;
47  }
48  unsigned long
49  asUint() const noexcept
50  {
51  return key_;
52  }
53  void ensure_valid() const;
54 
55 private:
56  unsigned long key_;
57 
58 }; // map_vector_key
59 
61 {
62  if (key < 0) {
63  throw cet::exception("InvalidKey")
64  << "Negative key " << key << " not valid for map_vector_key.";
65  }
66 }
67 
68 constexpr cet::map_vector_key::map_vector_key(unsigned long const key) noexcept
69  : key_{key}
70 {}
71 
72 inline void
74 {
75  if (key_ == static_cast<unsigned long>(-1)) { // Invalid key
76  throw cet::exception("InvalidKey")
77  << "Attempt to use an invalid cet::map_vector_key.";
78  }
79 }
80 
81 // ======================================================================
82 
83 template <class Value>
84 class cet::map_vector {
85 public:
86  // types:
88  using mapped_type = Value;
89  using value_type = std::pair<key_type, mapped_type>;
90  using impl_type = std::vector<value_type>;
91 
92  using size_type = typename impl_type::size_type;
93  using difference_type = typename impl_type::difference_type;
94 
95  using iterator = typename impl_type::iterator;
96  using const_iterator = typename impl_type::const_iterator;
97  using reverse_iterator = typename impl_type::reverse_iterator;
98  using const_reverse_iterator = typename impl_type::const_reverse_iterator;
99 
100  using allocator_type = typename impl_type::allocator_type;
101  using pointer = typename allocator_type::pointer;
102  using const_pointer = typename allocator_type::const_pointer;
103  using reference = typename allocator_type::reference;
104  using const_reference = typename allocator_type::const_reference;
105 
106  // c'tors:
107  map_vector() = default;
108 
109  template <class InIter>
110  map_vector(InIter const b, InIter const e)
111  {
112  insert(b, e);
113  }
114 
115  // use compiler-generated copy c'tor, copy assignment, and d'tor
116 
117  // properties:
118  bool
119  empty() const noexcept
120  {
121  return v_.empty();
122  }
123  size_type
124  size() const noexcept
125  {
126  return v_.size();
127  }
128  size_type
129  max_size() const noexcept
130  {
131  return v_.max_size();
132  }
133  size_type
134  capacity() const noexcept
135  {
136  return v_.capacity();
137  }
138 
140  get_allocator() const noexcept
141  {
142  return v_.get_allocator();
143  }
144 
145  // observers:
146  value_type const& front() const;
147  value_type const& back() const;
148 
149  // To be used in case map_vectors must be concatenated, and not
150  // merged.
151  size_t
152  delta() const
153  {
154  return v_.empty() ? 0 : 1 + v_.back().first.asInt();
155  }
156 
157  bool has(key_type key) const;
158 
159  iterator find(key_type key);
160  const_iterator find(key_type key) const;
161  const_iterator findOrThrow(key_type key) const;
162 
163  mapped_type* getOrNull(key_type key);
164  mapped_type const* getOrNull(key_type key) const;
165 
166  mapped_type& getOrThrow(key_type key);
167  mapped_type const& getOrThrow(key_type key) const;
168 
169  mapped_type& operator[](key_type key);
170  mapped_type const& operator[](key_type key) const { return getOrThrow(key); }
171  mapped_type const&
172  at(key_type key) const
173  {
174  return getOrThrow(key);
175  }
176 
177  // iterators:
178  iterator
179  begin() noexcept
180  {
181  return v_.begin();
182  }
184  begin() const noexcept
185  {
186  return v_.begin();
187  }
188 
189  iterator
190  end() noexcept
191  {
192  return v_.end();
193  }
195  end() const noexcept
196  {
197  return v_.end();
198  }
199 
201  rbegin() noexcept
202  {
203  return v_.rbegin();
204  }
206  rbegin() const noexcept
207  {
208  return v_.rbegin();
209  }
210 
212  rend() noexcept
213  {
214  return v_.rend();
215  }
217  rend() const noexcept
218  {
219  return v_.rend();
220  }
221 
223  cbegin() const noexcept
224  {
225  return v_.cbegin();
226  }
228  cend() const noexcept
229  {
230  return v_.cend();
231  }
233  crbegin() const
234  {
235  return v_.crbegin();
236  }
238  crend() const noexcept
239  {
240  return v_.crend();
241  }
242 
243  // mutators:
244  void
245  clear() noexcept
246  {
247  v_.clear();
248  }
249 
250  void
252  {
253  v_.reserve(n);
254  }
255 
256  void
258  {
259  v_.swap(other.v_);
260  }
261 
262  std::pair<iterator, bool> insert(value_type const& x);
263 
264  template <class InIter>
265  void insert(InIter b, InIter e);
266 
267  // MUST UPDATE WHEN CLASS IS CHANGED!
268  static short
270  {
271  return 10;
272  }
273 
274 private:
275  impl_type v_{};
276 
277  bool class_invariant() const;
278 
279  static bool lt(value_type const&, value_type const&) noexcept;
280  static bool eq(value_type const&, value_type const&) noexcept;
281 
282 }; // map_vector<>
283 
284 // ======================================================================
285 // additional map_vector_key implementation
286 
287 // ----------------------------------------------------------------------
288 // comparisons:
289 
290 inline bool
291 cet::operator==(map_vector_key const& k1, map_vector_key const& k2) noexcept
292 {
293  return k1.asInt() == k2.asInt();
294 }
295 
296 inline bool
297 cet::operator!=(map_vector_key const& k1, map_vector_key const& k2) noexcept
298 {
299  return k1.asInt() != k2.asInt();
300 }
301 
302 inline bool
303 cet::operator<(map_vector_key const& k1, map_vector_key const& k2) noexcept
304 {
305  return k1.asInt() < k2.asInt();
306 }
307 
308 inline bool
309 cet::operator>(map_vector_key const& k1, map_vector_key const& k2) noexcept
310 {
311  return k1.asInt() > k2.asInt();
312 }
313 
314 inline bool
315 cet::operator<=(map_vector_key const& k1, map_vector_key const& k2) noexcept
316 {
317  return k1.asInt() <= k2.asInt();
318 }
319 
320 inline bool
321 cet::operator>=(map_vector_key const& k1, map_vector_key const& k2) noexcept
322 {
323  return k1.asInt() >= k2.asInt();
324 }
325 
326 // ----------------------------------------------------------------------
327 // output:
328 
329 inline std::ostream&
330 cet::operator<<(std::ostream& os, cet::map_vector_key const& key)
331 {
332  return os << key.asInt();
333 }
334 
335 // ======================================================================
336 // additional map_vector<> implementation
337 
338 // ----------------------------------------------------------------------
339 // observers:
340 
341 template <class Value>
344 {
345  if (v_.empty())
346  throw cet::exception("map_vector::front") << "container is empty!\n";
347  return v_.front();
348 }
349 
350 template <class Value>
353 {
354  if (v_.empty())
355  throw cet::exception("map_vector::back") << "container is empty!\n";
356  return v_.back();
357 }
358 
359 template <class Value>
360 bool
362 {
363  value_type const v{key, mapped_type{}};
364  return std::binary_search(v_.begin(), v_.end(), v, lt);
365 }
366 
367 template <class Value>
370 {
371  value_type const v{key, mapped_type{}};
372  auto const begin = v_.begin(), end = v_.end();
373  auto it = std::lower_bound(begin, end, v, lt);
374  if (it != end && it->first != key)
375  it = end;
376  return it;
377 }
378 
379 template <class Value>
382 {
383  value_type const v{key, mapped_type{}};
384  auto const begin = v_.cbegin(), end = v_.cend();
385  auto it = std::lower_bound(begin, end, v, lt);
386  if (it != end && it->first != key)
387  it = end;
388  return it;
389 }
390 
391 template <class Value>
394 {
395  auto p = find(key);
396  if (p == v_.cend())
397  throw cet::exception("map_vector::getOrThrow")
398  << "out of range (no such key): " << key.asInt() << std::endl;
399 
400  return p;
401 }
402 
403 template <class Value>
404 Value*
406 {
407  auto it = find(key);
408  return it == v_.end() ? nullptr : &it->second;
409 }
410 
411 template <class Value>
412 Value const*
414 {
415  auto it = find(key);
416  return it == v_.cend() ? nullptr : &it->second;
417 }
418 
419 template <class Value>
420 Value&
422 {
423  auto* p = getOrNull(key);
424  if (p == nullptr)
425  throw cet::exception("map_vector::getOrThrow")
426  << "out of range (no such key): " << key.asInt() << std::endl;
427 
428  return *p;
429 }
430 
431 template <class Value>
432 Value const&
434 {
435  auto const* p = getOrNull(key);
436  if (p == nullptr)
437  throw cet::exception("map_vector::getOrThrow")
438  << "out of range (no such key): " << key.asInt() << std::endl;
439 
440  return *p;
441 }
442 
443 template <class Value>
445 {
446  value_type const v{key, mapped_type{}};
447  auto const begin = v_.begin(), end = v_.end();
448  auto it = std::lower_bound(begin, end, v, lt);
449  if (it == end || it->first != key)
450  it = v_.insert(it, std::move(v));
451  return it->second;
452 }
453 
454 // ----------------------------------------------------------------------
455 // mutators:
456 
457 template <class Value>
458 std::pair<typename cet::map_vector<Value>::iterator, bool>
460 {
461  v.first.ensure_valid();
462  auto const begin = v_.begin(), end = v_.end();
463  auto it = std::lower_bound(begin, end, v, lt);
464  if (it == end || it->first != v.first)
465  return std::make_pair(v_.insert(it, v), true);
466  return std::make_pair(it, false);
467 }
468 
469 template <class Value>
470 template <class InIter>
471 void
472 cet::map_vector<Value>::insert(InIter const b, InIter const e)
473 {
474  std::for_each(b, e, [](auto const& pr) { return pr.first.ensure_valid(); });
476  std::merge(v_.cbegin(), v_.cend(), b, e, back_inserter(result), lt);
477  auto new_end = std::unique(result.begin(), result.end(), eq);
478  result.erase(new_end, result.end());
479  v_.swap(result);
480 }
481 
482 // ----------------------------------------------------------------------
483 // helpers:
484 
485 template <class Value>
486 bool
488 {
489  return std::is_sorted(v_.begin(), v_.end(), lt);
490 }
491 
492 // ======================================================================
493 
494 template <class Value>
495 bool
496 cet::map_vector<Value>::lt(value_type const& v1, value_type const& v2) noexcept
497 {
498  return v1.first < v2.first;
499 }
500 
501 template <class Value>
502 bool
503 cet::map_vector<Value>::eq(value_type const& v1, value_type const& v2) noexcept
504 {
505  return v1.first == v2.first;
506 }
507 
508 // ======================================================================
509 #endif /* cetlib_map_vector_h */
510 
511 // Local variables:
512 // mode: c++
513 // End:
reverse_iterator rbegin() noexcept
Definition: map_vector.h:201
bool empty() const noexcept
Definition: map_vector.h:119
constexpr map_vector_key(unsigned const key) noexcept
Definition: map_vector.h:39
double lt
allocator_type get_allocator() const noexcept
Definition: map_vector.h:140
set< int >::iterator it
unsigned long asUint() const noexcept
Definition: map_vector.h:49
size_type capacity() const noexcept
Definition: map_vector.h:134
const_reverse_iterator rend() const noexcept
Definition: map_vector.h:217
std::ostream & operator<<(std::ostream &, map_vector_key const &)
Definition: map_vector.h:330
const_iterator cend() const noexcept
Definition: map_vector.h:228
std::vector< value_type > impl_type
Definition: map_vector.h:90
void swap(map_vector< mapped_type > &other)
Definition: map_vector.h:257
const char * p
Definition: xmltok.h:285
bool operator!=(exempt_ptr< E > const &, exempt_ptr< E > const &)
Definition: exempt_ptr.h:219
std::pair< key_type, mapped_type > value_type
Definition: map_vector.h:89
bool operator<(exempt_ptr< E > const &, exempt_ptr< E > const &)
Definition: exempt_ptr.h:257
bool has(key_type key) const
Definition: map_vector.h:361
iterator find(key_type key)
Definition: map_vector.h:369
iterator end() noexcept
Definition: map_vector.h:190
std::pair< iterator, bool > insert(value_type const &x)
Definition: map_vector.h:459
::xsd::cxx::tree::exception< char > exception
Definition: Database.h:225
std::pair< Spectrum *, CheatDecomp * > make_pair(SpectrumLoaderBase &loader_data, SpectrumLoaderBase &loader_mc, HistAxis *axis, Cut *cut, const SystShifts &shift, const Var &wei)
Definition: DataMCLoad.C:336
map_vector(InIter const b, InIter const e)
Definition: map_vector.h:110
const_iterator end() const noexcept
Definition: map_vector.h:195
typename allocator_type::reference reference
Definition: map_vector.h:103
constexpr map_vector_key() noexcept
Definition: map_vector.h:37
typename impl_type::const_reverse_iterator const_reverse_iterator
Definition: map_vector.h:98
size_t delta() const
Definition: map_vector.h:152
void clear() noexcept
Definition: map_vector.h:245
typename impl_type::allocator_type allocator_type
Definition: map_vector.h:100
typename allocator_type::const_reference const_reference
Definition: map_vector.h:104
Value mapped_type
Definition: map_vector.h:88
typename impl_type::reverse_iterator reverse_iterator
Definition: map_vector.h:97
static bool lt(value_type const &, value_type const &) noexcept
Definition: map_vector.h:496
bool operator<=(exempt_ptr< E > const &, exempt_ptr< E > const &)
Definition: exempt_ptr.h:273
const_iterator begin() const noexcept
Definition: map_vector.h:184
typename impl_type::size_type size_type
Definition: map_vector.h:92
size_type max_size() const noexcept
Definition: map_vector.h:129
mapped_type & operator[](key_type key)
Definition: map_vector.h:444
typename impl_type::difference_type difference_type
Definition: map_vector.h:93
std::void_t< T > n
typename allocator_type::const_pointer const_pointer
Definition: map_vector.h:102
typename allocator_type::pointer pointer
Definition: map_vector.h:101
impl_type v_
Definition: map_vector.h:275
bool class_invariant() const
Definition: map_vector.h:487
void reserve(size_type const n)
Definition: map_vector.h:251
value_type const & front() const
Definition: map_vector.h:343
bool operator>(exempt_ptr< E > const &, exempt_ptr< E > const &)
Definition: exempt_ptr.h:266
reverse_iterator rend() noexcept
Definition: map_vector.h:212
bool operator==(exempt_ptr< E > const &, exempt_ptr< E > const &)
Definition: exempt_ptr.h:212
mapped_type const & operator[](key_type key) const
Definition: map_vector.h:170
typename impl_type::iterator iterator
Definition: map_vector.h:95
iterator begin() noexcept
Definition: map_vector.h:179
value_type const & back() const
Definition: map_vector.h:352
const_reverse_iterator crbegin() const
Definition: map_vector.h:233
unsigned long key_
Definition: map_vector.h:56
const hit & b
Definition: hits.cxx:21
bool operator>=(exempt_ptr< E > const &, exempt_ptr< E > const &)
Definition: exempt_ptr.h:280
def insert(astring, substr, pos, overwrite=True)
const_reverse_iterator rbegin() const noexcept
Definition: map_vector.h:206
static bool eq(value_type const &, value_type const &) noexcept
Definition: map_vector.h:503
void ensure_valid() const
Definition: map_vector.h:73
mapped_type const & at(key_type key) const
Definition: map_vector.h:172
Float_t e
Definition: plot.C:35
const_iterator findOrThrow(key_type key) const
Definition: map_vector.h:393
mapped_type & getOrThrow(key_type key)
Definition: map_vector.h:421
static short Class_Version()
Definition: map_vector.h:269
size_type size() const noexcept
Definition: map_vector.h:124
const_reverse_iterator crend() const noexcept
Definition: map_vector.h:238
typename impl_type::const_iterator const_iterator
Definition: map_vector.h:96
const_iterator cbegin() const noexcept
Definition: map_vector.h:223
unsigned long asInt() const noexcept
Definition: map_vector.h:44
mapped_type * getOrNull(key_type key)
Definition: map_vector.h:405