HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_ArrayMap.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_ArrayMap.h (UT Library, C++)
7  *
8  * COMMENTS: Flat-array-based hash map implementation.
9  */
10 
11 #pragma once
12 
13 #ifndef __UT_ArrayMap__
14 #define __UT_ArrayMap__
15 
16 #include "UT_Array.h"
17 #include "UT_ArraySet.h"
18 #include "UT_IteratorRange.h"
19 
20 #include <hboost/functional/hash.hpp>
21 
22 #include <iterator>
23 #include <stdexcept>
24 #include <utility>
25 
26 namespace UT {
27 
28 template<class KeyEqual,typename Key,typename T>
30 {
31  bool operator()(const std::pair<Key,T> &a,const std::pair<Key,T> &b) const
32  {
33  return KeyEqual()(a.first, b.first);
34  }
35 };
36 
37 template<typename Hash,typename Key,typename T>
38 struct MapKeyHash
39 {
40  size_t operator()(const std::pair<Key,T> &a) const
41  {
42  return Hash()(a.first);
43  }
44 };
45 
46 template<typename S0,typename S1>
47 struct MapKeyClearer : public DefaultClearer<std::pair<S0,S1> >
48 {
50  using Base::clear;
51  /// Only need to actually check the key,
52  /// even though clear and clearConstruct will clear both.
53  static bool isClear(const std::pair<S0,S1> &v)
54  {
55  return DefaultClearer<S0>::isClear(v.first);
56  }
57  /// An overload for when there's only a key.
58  static bool isClear(const S0 &v)
59  {
61  }
64 };
65 
66 /// This is close to a drop-in replacement for std::unordered_map,
67 /// except that it uses a single array of items and empty spaces
68 /// marked with a dedicated "clear" value.
69 /// It also has a fixed maximum load factor, and doesn't store a
70 /// hasher, comparator, or allocator object as member data,
71 /// avoiding unnecessary overhead, but these differences introduce
72 /// some interface incompatibilities.
73 ///
74 /// See the comment on UT::ArraySet for specifics on these interface
75 /// incompatibilities. Most functions are inherited from UT::ArraySet.
76 template<
77  typename Key,
78  typename T,
79  bool MULTI=false,
80  std::size_t MAX_LOAD_FACTOR_256=128,
81  typename Clearer=MapKeyClearer<Key,T>,
82  class Hash=hboost::hash<Key>,
83  class KeyEqual=std::equal_to<Key>
84 >
85 class ArrayMap : public ArraySet<std::pair<Key,T>,MULTI,MAX_LOAD_FACTOR_256,Clearer,MapKeyHash<Hash,Key,T>,MapKeyEqual<KeyEqual,Key,T> >
86 {
87 public:
90  typedef Key key_type;
91  typedef T mapped_type;
92  typedef Hash hasher;
93  typedef KeyEqual key_equal;
94 
95  /// GCC and Clang can't find base class members in templated code, so we
96  /// need to declare explicitly that we're inheriting them.
97  using pointer = typename set_type::pointer;
99  using value_type = typename set_type::value_type;
100  using size_type = typename set_type::size_type;
101 
102  /// Inherit iterator and const_iterator
103  using iterator = typename set_type::iterator;
104  template<bool constant_type>
105  using iterator_t = typename set_type::template iterator_t<constant_type>;
107 
108  /// Inherit the constructors from ArraySet
109  using set_type::set_type;
110 
111  /// Inherit size from ArraySet.
112  using set_type::size;
113 
114  /// Inherit insert from ArraySet, in addition to signatures below.
115  using set_type::insert;
116 
117  std::pair<iterator, bool> insert(const Key &key, const T &val)
118  {
119  return insert(std::pair<Key,T>(key, val));
120  }
121  std::pair<iterator, bool> insert(Key &&key, T &&val)
122  {
123  return insert(std::make_pair(std::forward<Key>(key),
124  std::forward<T>(val)));
125  }
126 
127  bool operator==(const map_type &that) const
128  {
129  if (size() != that.size())
130  return false;
131 
132  // Check if one has no allocation (both empty)
133  if (!myBuckets || !that.myBuckets)
134  return true;
135 
136  const const_pointer pend = myBuckets + myNumBuckets;
137  for (const_pointer p = myBuckets; p != pend; ++p)
138  {
139  if (Clearer::isClear(*p))
140  continue;
141  // NOTE: Don't just use that.contains(*p), since it only checks the key!
142  const_iterator it = that.find(p->first);
143  if (it.atEnd())
144  return false;
145  if (*p != *it)
146  return false;
147  }
148  return true;
149  }
150  bool operator!=(const map_type &that) const
151  {
152  return !(*this == that);
153  }
154 
155  /// Returns an iterator to the first item matching key,
156  /// or an end iterator if no items match key.
157  /// @{
158  iterator find(const Key &key)
159  {
160  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
161 
162  const pointer pstart = myBuckets;
163  if (!pstart)
164  return iterator(nullptr,nullptr,false);
165 
166  const pointer pend = pstart + myNumBuckets;
167 
168  const pointer search_start = searchStart(key);
169  for (pointer p = search_start; p != pend; ++p)
170  {
171  if (key_equal()(key,p->first))
172  return iterator(p,pend,false);
173  if (Clearer::isClear(*p))
174  return iterator(pend,pend,false);
175  }
176  // Hit the end, so search back from before the start of the block.
177  for (pointer p = search_start-1; p >= pstart; --p)
178  {
179  if (key_equal()(key,p->first))
180  return iterator(p,pend,false);
181  if (Clearer::isClear(*p))
182  return iterator(pend,pend,false);
183  }
184  return iterator(pend,pend,false);
185  }
186  const_iterator find(const Key &key) const
187  {
188  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
189 
190  const const_pointer pstart = myBuckets;
191  if (!pstart)
192  return const_iterator(nullptr,nullptr,false);
193 
194  const const_pointer pend = pstart + myNumBuckets;
195 
196  const_pointer search_start = searchStart(key);
197  for (const_pointer p = search_start; p != pend; ++p)
198  {
199  if (key_equal()(key,p->first))
200  return const_iterator(p,pend,false);
201  if (Clearer::isClear(*p))
202  return const_iterator(pend,pend,false);
203  }
204  // Hit the end, so search back from before the start of the block.
205  for (const_pointer p = search_start-1; p >= pstart; --p)
206  {
207  if (key_equal()(key,p->first))
208  return const_iterator(p,pend,false);
209  if (Clearer::isClear(*p))
210  return const_iterator(pend,pend,false);
211  }
212  return const_iterator(pend,pend,false);
213  }
214  /// @}
215 
216  /// Returns a reference to the value of the first item matching key.
217  /// WARNING: This throws an exception if nothing matches key!
218  /// @{
219  T &at(const Key &key)
220  {
221  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
222 
223  if (!myBuckets)
224  {
225  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap::at!");
226  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &)");
227  }
228 
229  const pointer pstart = myBuckets;
230  const const_pointer pend = pstart + myNumBuckets;
231  const pointer search_start = searchStart(key);
232  for (pointer p = search_start; p != pend; ++p)
233  {
234  if (key_equal()(key,p->first))
235  return p->second;
236  if (Clearer::isClear(*p))
237  {
238  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap::at!");
239  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &)");
240  }
241  }
242  // Hit the end, so search back from before the start of the block.
243  for (pointer p = search_start-1; p >= pstart; --p)
244  {
245  if (key_equal()(key,p->first))
246  return p->second;
247  if (Clearer::isClear(*p))
248  {
249  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap::at!");
250  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &)");
251  }
252  }
253  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap::at!");
254  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &)");
255  }
256  const T &at(const Key &key) const
257  {
258  if (!myBuckets)
259  {
260  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap!");
261  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &) const");
262  }
263 
264  const const_pointer pstart = myBuckets;
265  const const_pointer pend = pstart + myNumBuckets;
266  const_pointer search_start = searchStart(key);
267  for (const_pointer p = search_start; p != pend; ++p)
268  {
269  if (key_equal()(key,p->first))
270  return p->second;
271  if (Clearer::isClear(*p))
272  {
273  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap!");
274  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &) const");
275  }
276  }
277  // Hit the end, so search back from before the start of the block.
278  for (const_pointer p = search_start-1; p >= pstart; --p)
279  {
280  if (key_equal()(key,p->first))
281  return p->second;
282  if (Clearer::isClear(*p))
283  {
284  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap!");
285  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &) const");
286  }
287  }
288  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap!");
289  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &) const");
290  }
291  /// @}
292 
293  /// Returns the number of entries matching key.
294  /// If MULTI is false, this will only return either 0 or 1.
295  size_type count(const Key &key) const
296  {
297  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
298 
299  if (!myBuckets)
300  return 0;
301 
302  const const_pointer pstart = myBuckets;
303  const const_pointer pend = pstart + myNumBuckets;
304  const_pointer search_start = searchStart(key);
305  size_type count = 0;
306  for (const_pointer p = search_start; p != pend; ++p)
307  {
308  if (key_equal()(key,p->first))
309  {
310  if (!MULTI)
311  return 1;
312  ++count;
313  }
314  if (Clearer::isClear(*p))
315  return MULTI ? count : 0;
316  }
317  // Hit the end, so search back from before the start of the block.
318  for (const_pointer p = search_start-1; p >= pstart; --p)
319  {
320  if (key_equal()(key,p->first))
321  {
322  if (!MULTI)
323  return 1;
324  ++count;
325  }
326  if (Clearer::isClear(*p))
327  return MULTI ? count : 0;
328  }
329  return MULTI ? count : 0;
330  }
331 
332  /// Returns true iff the set contains the given key.
333  /// This should be faster than count() if MULTI is true.
334  bool contains(const Key &key) const
335  {
336  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
337 
338  if (!myBuckets)
339  return false;
340 
341  const const_pointer pstart = myBuckets;
342  const const_pointer pend = pstart + myNumBuckets;
343  const_pointer search_start = searchStart(key);
344  for (const_pointer p = search_start; p != pend; ++p)
345  {
346  if (key_equal()(key,p->first))
347  return true;
348  if (Clearer::isClear(*p))
349  return false;
350  }
351  // Hit the end, so search back from before the start of the block.
352  for (const_pointer p = search_start-1; p >= pstart; --p)
353  {
354  if (key_equal()(key,p->first))
355  return true;
356  if (Clearer::isClear(*p))
357  return false;
358  }
359  return false;
360  }
361 
362  /// Returns a reference to the first value that is mapped-to from a key
363  /// matching key, inserting if none exist.
364  /// NOTE: If you use this, key cannot match the key of a pair
365  /// cleared by Clearer, else insertHelper will assert.
366  T &operator[](const Key &key)
367  {
368  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
369 
370  iterator it = find(key);
371  if (!it.atEnd())
372  return it->second;
373 
374  // NOTE: Must use value initialization (not to be confused with default
375  // constructor!) for second, so that, e.g. ints will be
376  // initialized to zero and pointers will be nullptr.
377  value_type value(key, mapped_type());
378 
379  pointer dest;
380  set_type::template insertHelper<false,true>(myBuckets,myNumBuckets,value,dest);
381  *dest = std::move(value);
382  ++*((size_type*)(myBuckets+myNumBuckets));
383  return dest->second;
384  }
385 
386  /// Returns a reference to the first value that is mapped-to from a key
387  /// matching key, inserting if none exist.
388  /// NOTE: If you use this, key cannot match the key of a pair
389  /// cleared by Clearer, else insertHelper will assert.
390  T &operator[](Key &&key)
391  {
392  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
393 
394  iterator it = find(key);
395  if (!it.atEnd())
396  return it->second;
397 
398  // NOTE: Must use value initialization (not to be confused with default
399  // constructor!) for second, so that, e.g. ints will be
400  // initialized to zero and pointers will be nullptr.
401  value_type value(std::move(key), mapped_type());
402 
403  pointer dest;
404  set_type::template insertHelper<false,true>(myBuckets,myNumBuckets,value,dest);
405  *dest = std::move(value);
406  ++*((size_type*)(myBuckets+myNumBuckets));
407  return dest->second;
408  }
409 
410  /// Returns a pair of iterators representing the range of values matching
411  /// key, as [first,second).
412  /// @{
413  std::pair<const_iterator,const_iterator> equal_range(const Key &key) const
414  {
415  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
416 
417  const const_pointer pstart = myBuckets;
418  const const_pointer pend = pstart + myNumBuckets;
419  if (!pstart)
420  return std::make_pair(const_iterator(nullptr,nullptr,false), const_iterator(nullptr,nullptr,false));
421 
422  const const_pointer search_start = searchStart(key);
423  if (!MULTI)
424  {
425  for (const_pointer p = search_start; p != pend; ++p)
426  {
427  if (key_equal()(key,p->first))
428  return std::make_pair(const_iterator(p,pend,false), const_iterator(p+1,pend,true));
429  if (Clearer::isClear(*p))
430  return std::make_pair(const_iterator(pend,pend,false), const_iterator(pend,pend,false));
431  }
432  // Hit the end, so search back from before the start of the block.
433  for (const_pointer p = search_start-1; p >= pstart; --p)
434  {
435  if (key_equal()(key,p->first))
436  return std::make_pair(const_iterator(p,pend,false), const_iterator(p+1,pend,true));
437  if (Clearer::isClear(*p))
438  return std::make_pair(const_iterator(pend,pend,false), const_iterator(pend,pend,false));
439  }
440  return std::make_pair(const_iterator(pend,pend,false), const_iterator(pend,pend,false));
441  }
442 
443  // MULTI is true, so we might have multiple matches
444  const_pointer first_found = nullptr;
445  const_pointer end_found = pend;
446  for (const_pointer p = search_start; p != pend; ++p)
447  {
448  if (key_equal()(key,p->first))
449  {
450  if (!first_found)
451  first_found = p;
452  }
453  else if (first_found)
454  {
455  if (first_found != search_start)
456  return std::make_pair(const_iterator(first_found,pend,false), const_iterator(p,pend,true));
457 
458  end_found = p;
459  break;
460  }
461  else if (Clearer::isClear(*p))
462  {
463  // NOTE: first_found must be false
464  return std::make_pair(const_iterator(pend,pend,false), const_iterator(pend,pend,false));
465  }
466  }
467 
468  // Hit the end, so search back from before the start of the block.
469  for (const_pointer p = search_start-1; p >= pstart; --p)
470  {
471  if (!key_equal()(key,p->first))
472  {
473  return std::make_pair(const_iterator(p+1,pend,false), const_iterator(end_found,pend,true));
474  }
475  }
476  return std::make_pair(const_iterator(pstart,pend,false), const_iterator(end_found,pend,true));
477  }
478  std::pair<iterator,iterator> equal_range(const Key &key)
479  {
480  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
481 
482  const pointer pstart = myBuckets;
483  const pointer pend = pstart + myNumBuckets;
484  if (!pstart)
485  return std::make_pair(iterator(nullptr,nullptr,false), iterator(nullptr,nullptr,false));
486 
487  const pointer search_start = searchStart(key);
488  if (!MULTI)
489  {
490  for (pointer p = search_start; p != pend; ++p)
491  {
492  if (key_equal()(key,p->first))
493  return std::make_pair(iterator(p,pend,false), iterator(p+1,pend,true));
494  if (Clearer::isClear(*p))
495  return std::make_pair(iterator(pend,pend,false), iterator(pend,pend,false));
496  }
497  // Hit the end, so search back from before the start of the block.
498  for (pointer p = search_start-1; p >= pstart; --p)
499  {
500  if (key_equal()(key,p->first))
501  return std::make_pair(iterator(p,pend,false), iterator(p+1,pend,true));
502  if (Clearer::isClear(*p))
503  return std::make_pair(iterator(pend,pend,false), iterator(pend,pend,false));
504  }
505  return std::make_pair(iterator(pend,pend,false), iterator(pend,pend,false));
506  }
507 
508  // MULTI is true, so we might have multiple matches
509  pointer first_found = nullptr;
510  pointer end_found = pend;
511  for (pointer p = search_start; p != pend; ++p)
512  {
513  if (key_equal()(key,p->first))
514  {
515  if (!first_found)
516  first_found = p;
517  }
518  else if (first_found)
519  {
520  if (first_found != search_start)
521  return std::make_pair(iterator(first_found,pend,false), iterator(p,pend,true));
522 
523  end_found = p;
524  break;
525  }
526  else if (Clearer::isClear(*p))
527  {
528  // NOTE: first_found must be false
529  return std::make_pair(iterator(pend,pend,false), iterator(pend,pend,false));
530  }
531  }
532 
533  // Hit the end, so search back from before the start of the block.
534  for (pointer p = search_start-1; p >= pstart; --p)
535  {
536  if (!key_equal()(key,p->first))
537  {
538  return std::make_pair(iterator(p+1,pend,false), iterator(end_found,pend,true));
539  }
540  }
541  return std::make_pair(iterator(pstart,pend,false), iterator(end_found,pend,true));
542  }
543  /// @}
544 
545  /// Inherit erase from ArraySet, in addition to signatures below.
546  using set_type::erase;
547 
548  /// Removes all items matching key and returns
549  /// the number of items removed.
550  size_type erase(const Key &key)
551  {
552  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
553 
554  if (!MULTI)
555  {
556  iterator it = find(key);
557  if (it.atEnd())
558  return 0;
559  erase(it);
560  return 1;
561  }
562 
563  // NOTE: This commented out code won't work, because the 2-argument erase isn't implemented.
564  //std::pair<iterator,iterator> its = equal_range(key);
565  //size_type count = std::distance(its.first, its.second);
566  //erase(its.first, its.second);
567 
568  size_type count = 0;
569  for (iterator it = find(key); !it.atEnd(); it = find(key))
570  {
571  erase(it);
572  }
573  return count;
574  }
575 
576  template<typename FUNCTOR>
578  void forEachKey(FUNCTOR &&functor) const
579  {
581  const const_pointer pend = p + myNumBuckets;
582  for (; p != pend; ++p)
583  {
584  if (!Clearer::isClear(*p))
585  functor(p->first);
586  }
587  }
588 
589  template<typename FUNCTOR>
591  void forEachValue(FUNCTOR &&functor) const
592  {
594  const const_pointer pend = p + myNumBuckets;
595  for (; p != pend; ++p)
596  {
597  if (!Clearer::isClear(*p))
598  functor(p->second);
599  }
600  }
601 
602  template<bool constant_type>
604  {
605  public:
606  typedef std::forward_iterator_tag iterator_category;
607  typedef std::ptrdiff_t difference_type;
612 
613  template<typename COMPARATOR>
614  ordered_iterator_t(map_type &map, const COMPARATOR &comparator)
615  : myMap(map)
616  , myI(0)
617  {
618  myKeys.setCapacity(map.size());
619  map.forEachKey([this](const Key &key) {
620  myKeys.append(key);
621  });
622  myKeys.stdsort(comparator);
623  }
625  : myMap(that.myMap)
626  , myKeys(std::move(that.myKeys))
627  , myI(that.myI)
628  {}
630  {
631  return *myMap.find(myKeys[myI]);
632  }
634  {
635  return &*myMap.find(myKeys[myI]);
636  }
637  operator pointer() const
638  {
639  return &*myMap.find(myKeys[myI]);
640  }
641  void operator++()
642  {
643  ++myI;
644  }
645  bool atEnd() const
646  {
647  return myI >= myKeys.size();
648  }
649  private:
650  /// Use atEnd(), not ==
651  bool operator==(const ordered_iterator_t<constant_type> &) const = delete;
652  bool operator!=(const ordered_iterator_t<constant_type> &) const = delete;
653 
654  map_type &myMap;
655  UT_Array<Key> myKeys;
656  exint myI;
657  };
658 
659  template<typename COMPARATOR>
660  ordered_iterator_t<true> ordered_begin(const COMPARATOR &comparator) const
661  {
662  return ordered_iterator_t<true>(*this, comparator);
663  }
664 
665  template<typename COMPARATOR>
666  ordered_iterator_t<true> ordered_cbegin(const COMPARATOR &comparator) const
667  {
668  return ordered_iterator_t<true>(*this, comparator);
669  }
670 
671  template<typename COMPARATOR>
672  ordered_iterator_t<false> ordered_begin(const COMPARATOR &comparator)
673  {
674  return ordered_iterator_t<false>(*this, comparator);
675  }
676 
677 protected:
678  template<typename VIT, typename VT>
680  {
681  VT &operator()(const VIT &v) const { return v->first; }
682  };
683  template<typename VIT, typename VT>
685  {
686  VT &operator()(const VIT &v) const { return v->second; }
687  };
688 
689  template<typename IT, typename VT, typename DR>
691  public std::iterator<std::forward_iterator_tag, VT>
692  {
693  public:
694  typedef VT& reference;
695  typedef VT* pointer;
696 
698 
699  template<typename EIT, typename EDR>
701  it(src.it) {}
702 
703  reference operator*() const { DR dr; return dr(it); }
704  pointer operator->() const { DR dr; return &dr(it); }
705 
707  { return it == o.it; }
708 
710  { return it != o.it; }
711 
713  {
714  ++it;
715  return *this;
716  }
717 
718  protected:
719  friend class ArrayMap;
720 
721  partial_iterator_base(IT it) : it(it) {}
722  private:
723  IT it;
724  };
725 
726 public:
727  using const_key_iterator = partial_iterator_base<const_iterator, const key_type,
728  deref_pair_first<const_iterator, const key_type>>;
729  using mapped_iterator = partial_iterator_base<iterator, mapped_type,
730  deref_pair_second<iterator, mapped_type>>;
731  using const_mapped_iterator = partial_iterator_base<const_iterator, const mapped_type,
732  deref_pair_second<const_iterator, const mapped_type>>;
733 
734  /// Returns a const range object that iterates over the map but returns
735  /// only the key values.
736  /// Example:
737  /// @code
738  /// UT::ArrayMap<int, const char *> foo = {{1, "one"}, {2, "two"}};
739  /// for (int key : foo.key_range())
740  /// std::cout << key << "\n";
741  /// @endcode
743  { return UTmakeRange(const_key_iterator(this->begin()),
744  const_key_iterator(this->end())); }
745 
746  /// Returns a range object that iterates over the map but returns only
747  /// the mapped values.
749  { return UTmakeRange(mapped_iterator(this->begin()),
750  mapped_iterator(this->end())); }
751 
752  /// Returns a const range object that iterates over the map but returns
753  /// only the mapped values.
755  { return UTmakeRange(const_mapped_iterator(this->begin()),
756  const_mapped_iterator(this->end())); }
757 
758 private:
759  /// GCC and Clang can't find base class members in templated code, so we
760  /// need to declare explicitly that we're inheriting them.
761  using set_type::myBuckets;
763 
764  pointer searchStart(const Key &key)
765  {
766  const size_type hash = hasher()(key);
767  return myBuckets + (hash%myNumBuckets);
768  }
769  const_pointer searchStart(const Key &key) const
770  {
771  const size_type hash = hasher()(key);
772  return myBuckets + (hash%myNumBuckets);
773  }
774 };
775 
776 template<
777  typename Key,
778  typename T,
779  bool MULTI,
780  std::size_t MAX_LOAD_FACTOR_256,
781  typename Clearer,
782  class Hash,
783  class KeyEqual
784 >
785 struct DefaultClearer<ArrayMap<Key,T,MULTI,MAX_LOAD_FACTOR_256,Clearer,Hash,KeyEqual> >
786  : public DefaultClearer<typename ArrayMap<Key,T,MULTI,MAX_LOAD_FACTOR_256,Clearer,Hash,KeyEqual>::set_type>
787 {};
788 
789 } // namespace UT
790 
791 template<typename Key,
792  typename T,
793  bool MULTI = false,
794  int MAX_LOAD_FACTOR_256 = 128,
795  typename Clearer = UT::MapKeyClearer<Key,T>,
796  class Hash = hboost::hash<Key>,
797  class KeyEqual = std::equal_to<Key> >
799 
800 #endif
UT_IteratorRange< const_mapped_iterator > mapped_range() const
Definition: UT_ArrayMap.h:754
ArrayMap< Key, T, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > map_type
Definition: UT_ArrayMap.h:89
GLenum src
Definition: glew.h:2410
T & at(const Key &key)
Definition: UT_ArrayMap.h:219
bool contains(const Key &key) const
Definition: UT_ArrayMap.h:334
SYS_FORCE_INLINE void forEachValue(FUNCTOR &&functor) const
Definition: UT_ArrayMap.h:591
ordered_iterator_t< true > ordered_cbegin(const COMPARATOR &comparator) const
Definition: UT_ArrayMap.h:666
ordered_iterator_t(map_type &map, const COMPARATOR &comparator)
Definition: UT_ArrayMap.h:614
bool operator==(const map_type &that) const
Definition: UT_ArrayMap.h:127
GLuint const GLfloat * val
Definition: glew.h:2794
T & operator[](Key &&key)
Definition: UT_ArrayMap.h:390
GLboolean GLboolean GLboolean GLboolean a
Definition: glew.h:9477
std::conditional< constant_type, typename set_type::const_pointer, typename set_type::pointer >::type pointer
Definition: UT_ArrayMap.h:610
UT_IteratorRange< IterT > UTmakeRange(IterT &&b, IterT &&e)
int64 exint
Definition: SYS_Types.h:125
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
Definition: UT_ArrayMap.h:413
SYS_FORCE_INLINE void forEachKey(FUNCTOR &&functor) const
Definition: UT_ArrayMap.h:578
bool operator==(const partial_iterator_base< IT, VT, DR > &o) const
Definition: UT_ArrayMap.h:706
void stdsort(ComparatorBool is_less)
Sort using std::sort. The ComparatorBool uses the less-than semantics.
Definition: UT_Array.h:301
partial_iterator_base & operator++()
Definition: UT_ArrayMap.h:712
partial_iterator_base< const_iterator, const mapped_type, deref_pair_second< const_iterator, const mapped_type >> const_mapped_iterator
Definition: UT_ArrayMap.h:732
const T & at(const Key &key) const
Definition: UT_ArrayMap.h:256
const GLdouble * v
Definition: glew.h:1391
#define UT_ASSERT_MSG_P(ZZ,...)
Definition: UT_Assert.h:137
std::forward_iterator_tag iterator_category
Definition: UT_ArrayMap.h:606
ordered_iterator_t< true > ordered_begin(const COMPARATOR &comparator) const
Definition: UT_ArrayMap.h:660
exint size() const
Definition: UT_Array.h:458
size_t OIIO_API Hash(const char *s, size_t len)
reference operator*() const
Definition: UT_ArrayMap.h:629
iterator find(const Key &key)
Definition: UT_ArrayMap.h:158
T & operator[](const Key &key)
Definition: UT_ArrayMap.h:366
ArraySet< std::pair< Key, T >, MULTI, MAX_LOAD_FACTOR_256, Clearer, MapKeyHash< Hash, Key, T >, MapKeyEqual< KeyEqual, Key, T > > set_type
Definition: UT_ArraySet.h:169
std::conditional< constant_type, const typename ArrayMap::map_type, typename ArrayMap::map_type >::type map_type
Definition: UT_ArrayMap.h:611
#define UT_ASSERT_MSG(ZZ,...)
Definition: UT_Assert.h:138
std::conditional< constant_type, const value_type, value_type >::type & reference
Definition: UT_ArrayMap.h:609
bool operator()(const std::pair< Key, T > &a, const std::pair< Key, T > &b) const
Definition: UT_ArrayMap.h:31
typename set_type::const_pointer const_pointer
Definition: UT_ArrayMap.h:98
void setCapacity(exint newcapacity)
Definition: UT_ArrayImpl.h:777
typename set_type::size_type size_type
Definition: UT_ArrayMap.h:100
std::size_t size_type
Definition: UT_ArraySet.h:172
partial_iterator_base< const_iterator, const key_type, deref_pair_first< const_iterator, const key_type >> const_key_iterator
Definition: UT_ArrayMap.h:728
static void clearConstruct(std::pair< S0, S1 > *p)
Definition: UT_ArraySet.h:122
std::pair< iterator, iterator > equal_range(const Key &key)
Definition: UT_ArrayMap.h:478
size_t operator()(const std::pair< Key, T > &a) const
Definition: UT_ArrayMap.h:40
std::pair< iterator, bool > insert(const Key &key, const T &val)
Definition: UT_ArrayMap.h:117
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
partial_iterator_base(const partial_iterator_base< EIT, VT, EDR > &src)
Definition: UT_ArrayMap.h:700
Set iterator class.
Definition: UT_ArraySet.h:551
ordered_iterator_t(ordered_iterator_t< constant_type > &&that)
Definition: UT_ArrayMap.h:624
size_type erase(const Key &key)
Definition: UT_ArrayMap.h:550
exint append()
Definition: UT_Array.h:95
static bool isClear(const std::pair< S0, S1 > &v)
Definition: UT_ArrayMap.h:53
partial_iterator_base< iterator, mapped_type, deref_pair_second< iterator, mapped_type >> mapped_iterator
Definition: UT_ArrayMap.h:730
ordered_iterator_t< false > ordered_begin(const COMPARATOR &comparator)
Definition: UT_ArrayMap.h:672
GLdouble GLdouble GLdouble b
Definition: glew.h:9122
GLfloat GLfloat p
Definition: glew.h:16321
std::conditional< constant_type, const typename ArrayMap::value_type, typename ArrayMap::value_type >::type value_type
Definition: UT_ArrayMap.h:608
const_iterator find(const Key &key) const
Definition: UT_ArrayMap.h:186
GLsizei const void * pointer
Definition: glew.h:1523
size_type count(const Key &key) const
Definition: UT_ArrayMap.h:295
static bool isClear(const S0 &v)
An overload for when there's only a key.
Definition: UT_ArrayMap.h:58
bool operator!=(const map_type &that) const
Definition: UT_ArrayMap.h:150
bool operator!=(const partial_iterator_base< IT, VT, DR > &o) const
Definition: UT_ArrayMap.h:709
typename set_type::iterator iterator
Inherit iterator and const_iterator.
Definition: UT_ArrayMap.h:103
VT & operator()(const VIT &v) const
Definition: UT_ArrayMap.h:686
const value_type * const_pointer
Definition: UT_ArraySet.h:179
GLuint GLuint GLsizei count
Definition: glew.h:1253
static void clear(std::pair< S0, S1 > &v)
Definition: UT_ArraySet.h:113
KeyEqual key_equal
Definition: UT_ArrayMap.h:93
typename set_type::template iterator_t< constant_type > iterator_t
Definition: UT_ArrayMap.h:105
std::pair< iterator, bool > insert(Key &&key, T &&val)
Definition: UT_ArrayMap.h:121
VT & operator()(const VIT &v) const
Definition: UT_ArrayMap.h:681
GLsizei const GLfloat * value
Definition: glew.h:1849
UT_IteratorRange< const_key_iterator > key_range() const
Definition: UT_ArrayMap.h:742
typename set_type::const_iterator const_iterator
Definition: UT_ArrayMap.h:106
UT_IteratorRange< mapped_iterator > mapped_range()
Definition: UT_ArrayMap.h:748
ArraySet< std::pair< Key, T >, MULTI, MAX_LOAD_FACTOR_256, Clearer, MapKeyHash< Hash, Key, T >, MapKeyEqual< KeyEqual, Key, T > > set_type
Definition: UT_ArrayMap.h:88
type
Definition: core.h:528
value_type * pointer
Definition: UT_ArraySet.h:178