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