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(key, val));
124  }
125 
126  bool operator==(const map_type &that) const
127  {
128  if (size() != that.size())
129  return false;
130 
131  // Check if one has no allocation (both empty)
132  if (!myBuckets || !that.myBuckets)
133  return true;
134 
135  const const_pointer pend = myBuckets + myNumBuckets;
136  for (const_pointer p = myBuckets; p != pend; ++p)
137  {
138  if (Clearer::isClear(*p))
139  continue;
140  // NOTE: Don't just use that.contains(*p), since it only checks the key!
141  const_iterator it = that.find(p->first);
142  if (it.atEnd())
143  return false;
144  if (*p != *it)
145  return false;
146  }
147  return true;
148  }
149  bool operator!=(const map_type &that) const
150  {
151  return !(*this == that);
152  }
153 
154  /// Returns an iterator to the first item matching key,
155  /// or an end iterator if no items match key.
156  /// @{
157  iterator find(const Key &key)
158  {
159  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
160 
161  const pointer pstart = myBuckets;
162  if (!pstart)
163  return iterator(nullptr,nullptr,false);
164 
165  const pointer pend = pstart + myNumBuckets;
166 
167  const pointer search_start = searchStart(key);
168  for (pointer p = search_start; p != pend; ++p)
169  {
170  if (key_equal()(key,p->first))
171  return iterator(p,pend,false);
172  if (Clearer::isClear(*p))
173  return iterator(pend,pend,false);
174  }
175  // Hit the end, so search back from before the start of the block.
176  for (pointer p = search_start-1; p >= pstart; --p)
177  {
178  if (key_equal()(key,p->first))
179  return iterator(p,pend,false);
180  if (Clearer::isClear(*p))
181  return iterator(pend,pend,false);
182  }
183  return iterator(pend,pend,false);
184  }
185  const_iterator find(const Key &key) const
186  {
187  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
188 
189  const const_pointer pstart = myBuckets;
190  if (!pstart)
191  return const_iterator(nullptr,nullptr,false);
192 
193  const const_pointer pend = pstart + myNumBuckets;
194 
195  const_pointer search_start = searchStart(key);
196  for (const_pointer p = search_start; p != pend; ++p)
197  {
198  if (key_equal()(key,p->first))
199  return const_iterator(p,pend,false);
200  if (Clearer::isClear(*p))
201  return const_iterator(pend,pend,false);
202  }
203  // Hit the end, so search back from before the start of the block.
204  for (const_pointer p = search_start-1; p >= pstart; --p)
205  {
206  if (key_equal()(key,p->first))
207  return const_iterator(p,pend,false);
208  if (Clearer::isClear(*p))
209  return const_iterator(pend,pend,false);
210  }
211  return const_iterator(pend,pend,false);
212  }
213  /// @}
214 
215  /// Returns a reference to the value of the first item matching key.
216  /// WARNING: This throws an exception if nothing matches key!
217  /// @{
218  T &at(const Key &key)
219  {
220  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
221 
222  if (!myBuckets)
223  {
224  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap::at!");
225  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &)");
226  }
227 
228  const pointer pstart = myBuckets;
229  const const_pointer pend = pstart + myNumBuckets;
230  const pointer search_start = searchStart(key);
231  for (pointer p = search_start; p != pend; ++p)
232  {
233  if (key_equal()(key,p->first))
234  return p->second;
235  if (Clearer::isClear(*p))
236  {
237  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap::at!");
238  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &)");
239  }
240  }
241  // Hit the end, so search back from before the start of the block.
242  for (pointer p = search_start-1; p >= pstart; --p)
243  {
244  if (key_equal()(key,p->first))
245  return p->second;
246  if (Clearer::isClear(*p))
247  {
248  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap::at!");
249  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &)");
250  }
251  }
252  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap::at!");
253  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &)");
254  }
255  const T &at(const Key &key) const
256  {
257  if (!myBuckets)
258  {
259  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap!");
260  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &) const");
261  }
262 
263  const const_pointer pstart = myBuckets;
264  const const_pointer pend = pstart + myNumBuckets;
265  const_pointer search_start = searchStart(key);
266  for (const_pointer p = search_start; p != pend; ++p)
267  {
268  if (key_equal()(key,p->first))
269  return p->second;
270  if (Clearer::isClear(*p))
271  {
272  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap!");
273  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &) const");
274  }
275  }
276  // Hit the end, so search back from before the start of the block.
277  for (const_pointer p = search_start-1; p >= pstart; --p)
278  {
279  if (key_equal()(key,p->first))
280  return p->second;
281  if (Clearer::isClear(*p))
282  {
283  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap!");
284  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &) const");
285  }
286  }
287  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap!");
288  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &) const");
289  }
290  /// @}
291 
292  /// Returns the number of entries matching key.
293  /// If MULTI is false, this will only return either 0 or 1.
294  size_type count(const Key &key) const
295  {
296  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
297 
298  if (!myBuckets)
299  return 0;
300 
301  const const_pointer pstart = myBuckets;
302  const const_pointer pend = pstart + myNumBuckets;
303  const_pointer search_start = searchStart(key);
304  size_type count = 0;
305  for (const_pointer p = search_start; p != pend; ++p)
306  {
307  if (key_equal()(key,p->first))
308  {
309  if (!MULTI)
310  return 1;
311  ++count;
312  }
313  if (Clearer::isClear(*p))
314  return MULTI ? count : 0;
315  }
316  // Hit the end, so search back from before the start of the block.
317  for (const_pointer p = search_start-1; p >= pstart; --p)
318  {
319  if (key_equal()(key,p->first))
320  {
321  if (!MULTI)
322  return 1;
323  ++count;
324  }
325  if (Clearer::isClear(*p))
326  return MULTI ? count : 0;
327  }
328  return MULTI ? count : 0;
329  }
330 
331  /// Returns true iff the set contains the given key.
332  /// This should be faster than count() if MULTI is true.
333  bool contains(const Key &key) const
334  {
335  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
336 
337  if (!myBuckets)
338  return false;
339 
340  const const_pointer pstart = myBuckets;
341  const const_pointer pend = pstart + myNumBuckets;
342  const_pointer search_start = searchStart(key);
343  for (const_pointer p = search_start; p != pend; ++p)
344  {
345  if (key_equal()(key,p->first))
346  return true;
347  if (Clearer::isClear(*p))
348  return false;
349  }
350  // Hit the end, so search back from before the start of the block.
351  for (const_pointer p = search_start-1; p >= pstart; --p)
352  {
353  if (key_equal()(key,p->first))
354  return true;
355  if (Clearer::isClear(*p))
356  return false;
357  }
358  return false;
359  }
360 
361  /// Returns a reference to the first value that is mapped-to from a key
362  /// matching key, inserting if none exist.
363  /// NOTE: If you use this, key cannot match the key of a pair
364  /// cleared by Clearer, else insertHelper will assert.
365  T &operator[](const Key &key)
366  {
367  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
368 
369  iterator it = find(key);
370  if (!it.atEnd())
371  return it->second;
372 
373  // NOTE: Must use value initialization (not to be confused with default
374  // constructor!) for second, so that, e.g. ints will be
375  // initialized to zero and pointers will be nullptr.
376  value_type value(key, mapped_type());
377 
378  pointer dest;
379  set_type::template insertHelper<false,true>(myBuckets,myNumBuckets,value,dest);
380  *dest = std::move(value);
381  ++*((size_type*)(myBuckets+myNumBuckets));
382  return dest->second;
383  }
384 
385  /// Returns a reference to the first value that is mapped-to from a key
386  /// matching key, inserting if none exist.
387  /// NOTE: If you use this, key cannot match the key of a pair
388  /// cleared by Clearer, else insertHelper will assert.
389  T &operator[](Key &&key)
390  {
391  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
392 
393  iterator it = find(key);
394  if (!it.atEnd())
395  return it->second;
396 
397  // NOTE: Must use value initialization (not to be confused with default
398  // constructor!) for second, so that, e.g. ints will be
399  // initialized to zero and pointers will be nullptr.
400  value_type value(std::move(key), mapped_type());
401 
402  pointer dest;
403  set_type::template insertHelper<false,true>(myBuckets,myNumBuckets,value,dest);
404  *dest = std::move(value);
405  ++*((size_type*)(myBuckets+myNumBuckets));
406  return dest->second;
407  }
408 
409  /// Returns a pair of iterators representing the range of values matching
410  /// key, as [first,second).
411  /// @{
412  std::pair<const_iterator,const_iterator> equal_range(const Key &key) const
413  {
414  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
415 
416  const const_pointer pstart = myBuckets;
417  const const_pointer pend = pstart + myNumBuckets;
418  if (!pstart)
419  return std::make_pair(const_iterator(nullptr,nullptr,false), const_iterator(nullptr,nullptr,false));
420 
421  const const_pointer search_start = searchStart(key);
422  if (!MULTI)
423  {
424  for (const_pointer p = search_start; p != pend; ++p)
425  {
426  if (key_equal()(key,p->first))
427  return std::make_pair(const_iterator(p,pend,false), const_iterator(p+1,pend,true));
428  if (Clearer::isClear(*p))
429  return std::make_pair(const_iterator(pend,pend,false), const_iterator(pend,pend,false));
430  }
431  // Hit the end, so search back from before the start of the block.
432  for (const_pointer p = search_start-1; p >= pstart; --p)
433  {
434  if (key_equal()(key,p->first))
435  return std::make_pair(const_iterator(p,pend,false), const_iterator(p+1,pend,true));
436  if (Clearer::isClear(*p))
437  return std::make_pair(const_iterator(pend,pend,false), const_iterator(pend,pend,false));
438  }
439  return std::make_pair(const_iterator(pend,pend,false), const_iterator(pend,pend,false));
440  }
441 
442  // MULTI is true, so we might have multiple matches
443  const_pointer first_found = nullptr;
444  const_pointer end_found = pend;
445  for (const_pointer p = search_start; p != pend; ++p)
446  {
447  if (key_equal()(key,p->first))
448  {
449  if (!first_found)
450  first_found = p;
451  }
452  else if (first_found)
453  {
454  if (first_found != search_start)
455  return std::make_pair(const_iterator(first_found,pend,false), const_iterator(p,pend,true));
456 
457  end_found = p;
458  break;
459  }
460  else if (Clearer::isClear(*p))
461  {
462  // NOTE: first_found must be false
463  return std::make_pair(const_iterator(pend,pend,false), const_iterator(pend,pend,false));
464  }
465  }
466 
467  // Hit the end, so search back from before the start of the block.
468  for (const_pointer p = search_start-1; p >= pstart; --p)
469  {
470  if (!key_equal()(key,p->first))
471  {
472  return std::make_pair(const_iterator(p+1,pend,false), const_iterator(end_found,pend,true));
473  }
474  }
475  return std::make_pair(const_iterator(pstart,pend,false), const_iterator(end_found,pend,true));
476  }
477  std::pair<iterator,iterator> equal_range(const Key &key)
478  {
479  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
480 
481  const pointer pstart = myBuckets;
482  const pointer pend = pstart + myNumBuckets;
483  if (!pstart)
484  return std::make_pair(iterator(nullptr,nullptr,false), iterator(nullptr,nullptr,false));
485 
486  const pointer search_start = searchStart(key);
487  if (!MULTI)
488  {
489  for (pointer p = search_start; p != pend; ++p)
490  {
491  if (key_equal()(key,p->first))
492  return std::make_pair(iterator(p,pend,false), iterator(p+1,pend,true));
493  if (Clearer::isClear(*p))
494  return std::make_pair(iterator(pend,pend,false), iterator(pend,pend,false));
495  }
496  // Hit the end, so search back from before the start of the block.
497  for (pointer p = search_start-1; p >= pstart; --p)
498  {
499  if (key_equal()(key,p->first))
500  return std::make_pair(iterator(p,pend,false), iterator(p+1,pend,true));
501  if (Clearer::isClear(*p))
502  return std::make_pair(iterator(pend,pend,false), iterator(pend,pend,false));
503  }
504  return std::make_pair(iterator(pend,pend,false), iterator(pend,pend,false));
505  }
506 
507  // MULTI is true, so we might have multiple matches
508  pointer first_found = nullptr;
509  pointer end_found = pend;
510  for (pointer p = search_start; p != pend; ++p)
511  {
512  if (key_equal()(key,p->first))
513  {
514  if (!first_found)
515  first_found = p;
516  }
517  else if (first_found)
518  {
519  if (first_found != search_start)
520  return std::make_pair(iterator(first_found,pend,false), iterator(p,pend,true));
521 
522  end_found = p;
523  break;
524  }
525  else if (Clearer::isClear(*p))
526  {
527  // NOTE: first_found must be false
528  return std::make_pair(iterator(pend,pend,false), iterator(pend,pend,false));
529  }
530  }
531 
532  // Hit the end, so search back from before the start of the block.
533  for (pointer p = search_start-1; p >= pstart; --p)
534  {
535  if (!key_equal()(key,p->first))
536  {
537  return std::make_pair(iterator(p+1,pend,false), iterator(end_found,pend,true));
538  }
539  }
540  return std::make_pair(iterator(pstart,pend,false), iterator(end_found,pend,true));
541  }
542  /// @}
543 
544  /// Inherit erase from ArraySet, in addition to signatures below.
545  using set_type::erase;
546 
547  /// Removes all items matching key and returns
548  /// the number of items removed.
549  size_type erase(const Key &key)
550  {
551  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
552 
553  if (!MULTI)
554  {
555  iterator it = find(key);
556  if (it.atEnd())
557  return 0;
558  erase(it);
559  return 1;
560  }
561 
562  // NOTE: This commented out code won't work, because the 2-argument erase isn't implemented.
563  //std::pair<iterator,iterator> its = equal_range(key);
564  //size_type count = std::distance(its.first, its.second);
565  //erase(its.first, its.second);
566 
567  size_type count = 0;
568  for (iterator it = find(key); !it.atEnd(); it = find(key))
569  {
570  erase(it);
571  }
572  return count;
573  }
574 
575  template<typename FUNCTOR>
577  void forEachKey(FUNCTOR &&functor) const
578  {
580  const const_pointer pend = p + myNumBuckets;
581  for (; p != pend; ++p)
582  {
583  if (!Clearer::isClear(*p))
584  functor(p->first);
585  }
586  }
587 
588  template<typename FUNCTOR>
590  void forEachValue(FUNCTOR &&functor) const
591  {
593  const const_pointer pend = p + myNumBuckets;
594  for (; p != pend; ++p)
595  {
596  if (!Clearer::isClear(*p))
597  functor(p->second);
598  }
599  }
600 
601  template<bool constant_type>
603  {
604  public:
605  typedef std::forward_iterator_tag iterator_category;
606  typedef std::ptrdiff_t difference_type;
611 
612  template<typename COMPARATOR>
613  ordered_iterator_t(map_type &map, const COMPARATOR &comparator)
614  : myMap(map)
615  , myI(0)
616  {
617  myKeys.setCapacity(map.size());
618  map.forEachKey([this](const Key &key) {
619  myKeys.append(key);
620  });
621  myKeys.stdsort(comparator);
622  }
624  : myMap(that.myMap)
625  , myKeys(std::move(that.myKeys))
626  , myI(that.myI)
627  {}
629  {
630  return *myMap.find(myKeys[myI]);
631  }
633  {
634  return &*myMap.find(myKeys[myI]);
635  }
636  operator pointer() const
637  {
638  return &*myMap.find(myKeys[myI]);
639  }
640  void operator++()
641  {
642  ++myI;
643  }
644  bool atEnd() const
645  {
646  return myI >= myKeys.size();
647  }
648  private:
649  /// Use atEnd(), not ==
650  bool operator==(const ordered_iterator_t<constant_type> &) const = delete;
651  bool operator!=(const ordered_iterator_t<constant_type> &) const = delete;
652 
653  map_type &myMap;
654  UT_Array<Key> myKeys;
655  exint myI;
656  };
657 
658  template<typename COMPARATOR>
659  ordered_iterator_t<true> ordered_begin(const COMPARATOR &comparator) const
660  {
661  return ordered_iterator_t<true>(*this, comparator);
662  }
663 
664  template<typename COMPARATOR>
665  ordered_iterator_t<true> ordered_cbegin(const COMPARATOR &comparator) const
666  {
667  return ordered_iterator_t<true>(*this, comparator);
668  }
669 
670  template<typename COMPARATOR>
671  ordered_iterator_t<false> ordered_begin(const COMPARATOR &comparator)
672  {
673  return ordered_iterator_t<false>(*this, comparator);
674  }
675 
676 protected:
677  template<typename VIT, typename VT>
679  {
680  VT &operator()(const VIT &v) const { return v->first; }
681  };
682  template<typename VIT, typename VT>
684  {
685  VT &operator()(const VIT &v) const { return v->second; }
686  };
687 
688  template<typename IT, typename VT, typename DR>
690  public std::iterator<std::forward_iterator_tag, VT>
691  {
692  public:
693  typedef VT& reference;
694  typedef VT* pointer;
695 
697 
698  template<typename EIT, typename EDR>
700  it(src.it) {}
701 
702  reference operator*() const { DR dr; return dr(it); }
703  pointer operator->() const { DR dr; return &dr(it); }
704 
706  { return it == o.it; }
707 
709  { return it != o.it; }
710 
712  {
713  ++it;
714  return *this;
715  }
716 
718  {
719  it = src.it;
720  return *this;
721  }
722  protected:
723  friend class ArrayMap;
724 
725  partial_iterator_base(IT it) : it(it) {}
726  private:
727  IT it;
728  };
729 
730 public:
731  using const_key_iterator = partial_iterator_base<const_iterator, const key_type,
732  deref_pair_first<const_iterator, const key_type>>;
733  using mapped_iterator = partial_iterator_base<iterator, mapped_type,
734  deref_pair_second<iterator, mapped_type>>;
735  using const_mapped_iterator = partial_iterator_base<const_iterator, const mapped_type,
736  deref_pair_second<const_iterator, const mapped_type>>;
737 
738  /// Returns a const range object that iterates over the map but returns
739  /// only the key values.
740  /// Example:
741  /// @code
742  /// UT::ArrayMap<int, const char *> foo = {{1, "one"}, {2, "two"}};
743  /// for (int key : foo.key_range())
744  /// std::cout << key << "\n";
745  /// @endcode
747  { return UTmakeRange(const_key_iterator(this->begin()),
748  const_key_iterator(this->end())); }
749 
750  /// Returns a range object that iterates over the map but returns only
751  /// the mapped values.
753  { return UTmakeRange(mapped_iterator(this->begin()),
754  mapped_iterator(this->end())); }
755 
756  /// Returns a const range object that iterates over the map but returns
757  /// only the mapped values.
759  { return UTmakeRange(const_mapped_iterator(this->begin()),
760  const_mapped_iterator(this->end())); }
761 
762 private:
763  /// GCC and Clang can't find base class members in templated code, so we
764  /// need to declare explicitly that we're inheriting them.
765  using set_type::myBuckets;
767 
768  pointer searchStart(const Key &key)
769  {
770  const size_type hash = hasher()(key);
771  return myBuckets + (hash%myNumBuckets);
772  }
773  const_pointer searchStart(const Key &key) const
774  {
775  const size_type hash = hasher()(key);
776  return myBuckets + (hash%myNumBuckets);
777  }
778 };
779 
780 template<
781  typename Key,
782  typename T,
783  bool MULTI,
784  std::size_t MAX_LOAD_FACTOR_256,
785  typename Clearer,
786  class Hash,
787  class KeyEqual
788 >
789 struct DefaultClearer<ArrayMap<Key,T,MULTI,MAX_LOAD_FACTOR_256,Clearer,Hash,KeyEqual> >
790  : public DefaultClearer<typename ArrayMap<Key,T,MULTI,MAX_LOAD_FACTOR_256,Clearer,Hash,KeyEqual>::set_type>
791 {};
792 
793 } // namespace UT
794 
795 template<typename Key,
796  typename T,
797  bool MULTI = false,
798  int MAX_LOAD_FACTOR_256 = 128,
799  typename Clearer = UT::MapKeyClearer<Key,T>,
800  class Hash = hboost::hash<Key>,
801  class KeyEqual = std::equal_to<Key> >
803 
804 #endif
UT_IteratorRange< const_mapped_iterator > mapped_range() const
Definition: UT_ArrayMap.h:758
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:218
bool contains(const Key &key) const
Definition: UT_ArrayMap.h:333
SYS_FORCE_INLINE void forEachValue(FUNCTOR &&functor) const
Definition: UT_ArrayMap.h:590
ordered_iterator_t< true > ordered_cbegin(const COMPARATOR &comparator) const
Definition: UT_ArrayMap.h:665
ordered_iterator_t(map_type &map, const COMPARATOR &comparator)
Definition: UT_ArrayMap.h:613
bool operator==(const map_type &that) const
Definition: UT_ArrayMap.h:126
GLuint const GLfloat * val
Definition: glew.h:2794
T & operator[](Key &&key)
Definition: UT_ArrayMap.h:389
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:609
UT_IteratorRange< IterT > UTmakeRange(IterT &&b, IterT &&e)
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
Definition: UT_ArrayMap.h:412
SYS_FORCE_INLINE void forEachKey(FUNCTOR &&functor) const
Definition: UT_ArrayMap.h:577
bool operator==(const partial_iterator_base< IT, VT, DR > &o) const
Definition: UT_ArrayMap.h:705
void stdsort(ComparatorBool is_less)
Sort using std::sort. The ComparatorBool uses the less-than semantics.
Definition: UT_Array.h:294
partial_iterator_base & operator++()
Definition: UT_ArrayMap.h:711
partial_iterator_base< const_iterator, const mapped_type, deref_pair_second< const_iterator, const mapped_type >> const_mapped_iterator
Definition: UT_ArrayMap.h:736
const T & at(const Key &key) const
Definition: UT_ArrayMap.h:255
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:605
ordered_iterator_t< true > ordered_begin(const COMPARATOR &comparator) const
Definition: UT_ArrayMap.h:659
exint size() const
Definition: UT_Array.h:451
size_t OIIO_API Hash(const char *s, size_t len)
reference operator*() const
Definition: UT_ArrayMap.h:628
iterator find(const Key &key)
Definition: UT_ArrayMap.h:157
T & operator[](const Key &key)
Definition: UT_ArrayMap.h:365
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:610
#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:608
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:756
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:732
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:477
int64 exint
Definition: SYS_Types.h:120
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:699
Set iterator class.
Definition: UT_ArraySet.h:551
ordered_iterator_t(ordered_iterator_t< constant_type > &&that)
Definition: UT_ArrayMap.h:623
size_type erase(const Key &key)
Definition: UT_ArrayMap.h:549
partial_iterator_base & operator=(const partial_iterator_base< IT, VT, DR > &src)
Definition: UT_ArrayMap.h:717
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:734
ordered_iterator_t< false > ordered_begin(const COMPARATOR &comparator)
Definition: UT_ArrayMap.h:671
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:607
const_iterator find(const Key &key) const
Definition: UT_ArrayMap.h:185
GLsizei const void * pointer
Definition: glew.h:1523
size_type count(const Key &key) const
Definition: UT_ArrayMap.h:294
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:149
bool operator!=(const partial_iterator_base< IT, VT, DR > &o) const
Definition: UT_ArrayMap.h:708
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:685
const value_type * const_pointer
Definition: UT_ArraySet.h:179
GLuint GLuint GLsizei count
Definition: glew.h:1253
exint append(void)
Definition: UT_Array.h:95
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:680
GLsizei const GLfloat * value
Definition: glew.h:1849
UT_IteratorRange< const_key_iterator > key_range() const
Definition: UT_ArrayMap.h:746
typename set_type::const_iterator const_iterator
Definition: UT_ArrayMap.h:106
UT_IteratorRange< mapped_iterator > mapped_range()
Definition: UT_ArrayMap.h:752
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