HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros 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_ArraySet.h"
17 
18 namespace UT {
19 
20 template<class KeyEqual,typename Key,typename T>
22 {
23  bool operator()(const std::pair<Key,T> &a,const std::pair<Key,T> &b) const
24  {
25  return KeyEqual()(a.first, b.first);
26  }
27 };
28 
29 template<typename Hash,typename Key,typename T>
30 struct MapKeyHash
31 {
32  size_t operator()(const std::pair<Key,T> &a) const
33  {
34  return Hash()(a.first);
35  }
36 };
37 
38 template<typename S0,typename S1>
39 struct MapKeyClearer : public DefaultClearer<std::pair<S0,S1> >
40 {
42  using Base::clear;
43  /// Only need to actually check the key,
44  /// even though clear and clearConstruct will clear both.
45  static bool isClear(const std::pair<S0,S1> &v)
46  {
47  return DefaultClearer<S0>::isClear(v.first);
48  }
49  /// An overload for when there's only a key.
50  static bool isClear(const S0 &v)
51  {
53  }
56 };
57 
58 template<
59  typename Key,
60  typename T,
61  bool MULTI=false,
62  std::size_t MAX_LOAD_FACTOR_256=128,
63  typename Clearer=MapKeyClearer<Key,T>,
64  class Hash=std::hash<Key>,
65  class KeyEqual=std::equal_to<Key>
66 >
67 class ArrayMap : public ArraySet<std::pair<Key,T>,MULTI,MAX_LOAD_FACTOR_256,Clearer,MapKeyHash<Hash,Key,T>,MapKeyEqual<KeyEqual,Key,T> >
68 {
69 public:
72  typedef Key key_type;
73  typedef T mapped_type;
74  typedef Hash hasher;
75  typedef KeyEqual key_equal;
76 
77  /// GCC and Clang can't find base class members in templated code, so we
78  /// need to declare explicitly that we're inheriting them.
79  using pointer = typename set_type::pointer;
81  using value_type = typename set_type::value_type;
82  using size_type = typename set_type::size_type;
83 
84  /// Inherit iterator and const_iterator
85  using iterator = typename set_type::iterator;
86  template<bool constant_type>
87  using iterator_t = typename set_type::template iterator_t<constant_type>;
89 
90  /// Inherit the constructors from ArraySet
91  using set_type::set_type;
92 
93  /// Inherit insert from ArraySet, in addition to signatures below.
94  using set_type::insert;
95 
96  std::pair<iterator, bool> insert(const Key &key, const T &val)
97  {
98  return insert(std::pair<Key,T>(key, val));
99  }
100  std::pair<iterator, bool> insert(Key &&key, T &&val)
101  {
102  return insert(std::make_pair(key, val));
103  }
104 
105  /// Returns an iterator to the first item matching key,
106  /// or an end iterator if no items match key.
107  /// @{
108  iterator find(const Key &key)
109  {
110  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
111 
112  const pointer pstart = myBuckets;
113  if (!pstart)
114  return iterator(nullptr,nullptr,false);
115 
116  const pointer pend = pstart + myNumBuckets;
117 
118  const pointer search_start = searchStart(key);
119  for (pointer p = search_start; p != pend; ++p)
120  {
121  if (key_equal()(key,p->first))
122  return iterator(p,pend,false);
123  if (Clearer::isClear(*p))
124  return iterator(pend,pend,false);
125  }
126  // Hit the end, so search back from before the start of the block.
127  for (pointer p = search_start-1; p >= pstart; --p)
128  {
129  if (key_equal()(key,p->first))
130  return iterator(p,pend,false);
131  if (Clearer::isClear(*p))
132  return iterator(pend,pend,false);
133  }
134  return iterator(pend,pend,false);
135  }
136  const_iterator find(const Key &key) const
137  {
138  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
139 
140  const const_pointer pstart = myBuckets;
141  if (!pstart)
142  return const_iterator(nullptr,nullptr,false);
143 
144  const const_pointer pend = pstart + myNumBuckets;
145 
146  const_pointer search_start = searchStart(key);
147  for (const_pointer p = search_start; p != pend; ++p)
148  {
149  if (key_equal()(key,p->first))
150  return const_iterator(p,pend,false);
151  if (Clearer::isClear(*p))
152  return const_iterator(pend,pend,false);
153  }
154  // Hit the end, so search back from before the start of the block.
155  for (const_pointer p = search_start-1; p >= pstart; --p)
156  {
157  if (key_equal()(key,p->first))
158  return const_iterator(p,pend,false);
159  if (Clearer::isClear(*p))
160  return const_iterator(pend,pend,false);
161  }
162  return const_iterator(pend,pend,false);
163  }
164  /// @}
165 
166  /// Returns a reference to the value of the first item matching key.
167  /// WARNING: This throws an exception if nothing matches key!
168  /// @{
169  T &at(const Key &key)
170  {
171  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
172 
173  if (!myBuckets)
174  {
175  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap::at!");
176  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &)");
177  }
178 
179  const pointer pstart = myBuckets;
180  const const_pointer pend = pstart + myNumBuckets;
181  const pointer search_start = searchStart(key);
182  for (pointer p = search_start; p != pend; ++p)
183  {
184  if (key_equal()(key,p->first))
185  return p->second;
186  if (Clearer::isClear(*p))
187  {
188  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap::at!");
189  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &)");
190  }
191  }
192  // Hit the end, so search back from before the start of the block.
193  for (pointer p = search_start-1; p >= pstart; --p)
194  {
195  if (key_equal()(key,p->first))
196  return p->second;
197  if (Clearer::isClear(*p))
198  {
199  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap::at!");
200  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &)");
201  }
202  }
203  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap::at!");
204  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &)");
205  }
206  const T &at(const Key &key) const
207  {
208  if (!myBuckets)
209  {
210  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap!");
211  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &) const");
212  }
213 
214  const const_pointer pstart = myBuckets;
215  const const_pointer pend = pstart + myNumBuckets;
216  const_pointer search_start = searchStart(key);
217  for (const_pointer p = search_start; p != pend; ++p)
218  {
219  if (key_equal()(key,p->first))
220  return p->second;
221  if (Clearer::isClear(*p))
222  {
223  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap!");
224  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &) const");
225  }
226  }
227  // Hit the end, so search back from before the start of the block.
228  for (const_pointer p = search_start-1; p >= pstart; --p)
229  {
230  if (key_equal()(key,p->first))
231  return p->second;
232  if (Clearer::isClear(*p))
233  {
234  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap!");
235  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &) const");
236  }
237  }
238  UT_ASSERT_MSG(0,"WARNING! An exception is about to be thrown in UT::ArrayMap!");
239  throw std::out_of_range("Key not found in UT::ArrayMap::at(const Key &) const");
240  }
241  /// @}
242 
243  /// Returns the number of entries matching key.
244  /// If MULTI is false, this will only return either 0 or 1.
245  size_type count(const Key &key) const
246  {
247  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
248 
249  if (!myBuckets)
250  return 0;
251 
252  const const_pointer pstart = myBuckets;
253  const const_pointer pend = pstart + myNumBuckets;
254  const_pointer search_start = searchStart(key);
255  size_type count = 0;
256  for (const_pointer p = search_start; p != pend; ++p)
257  {
258  if (key_equal()(key,p->first))
259  {
260  if (!MULTI)
261  return 1;
262  ++count;
263  }
264  if (Clearer::isClear(*p))
265  return MULTI ? count : 0;
266  }
267  // Hit the end, so search back from before the start of the block.
268  for (const_pointer p = search_start-1; p >= pstart; --p)
269  {
270  if (key_equal()(key,p->first))
271  {
272  if (!MULTI)
273  return 1;
274  ++count;
275  }
276  if (Clearer::isClear(*p))
277  return MULTI ? count : 0;
278  }
279  return MULTI ? count : 0;
280  }
281 
282  /// Returns true iff the set contains the given key.
283  /// This should be faster than count() if MULTI is true.
284  bool contains(const Key &key) const
285  {
286  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
287 
288  if (!myBuckets)
289  return false;
290 
291  const const_pointer pstart = myBuckets;
292  const const_pointer pend = pstart + myNumBuckets;
293  const_pointer search_start = searchStart(key);
294  for (const_pointer p = search_start; p != pend; ++p)
295  {
296  if (key_equal()(key,p->first))
297  return true;
298  if (Clearer::isClear(*p))
299  return false;
300  }
301  // Hit the end, so search back from before the start of the block.
302  for (const_pointer p = search_start-1; p >= pstart; --p)
303  {
304  if (key_equal()(key,p->first))
305  return true;
306  if (Clearer::isClear(*p))
307  return false;
308  }
309  return false;
310  }
311 
312  /// Returns a reference to the first value that is mapped-to from a key
313  /// matching key, inserting if none exist.
314  /// NOTE: If you use this, key cannot match the key of a pair
315  /// cleared by Clearer, else insertHelper will assert.
316  T &operator[](const Key &key)
317  {
318  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
319 
320  iterator it = find(key);
321  if (!it.atEnd())
322  return it->second;
323 
324  // NOTE: Must use value initialization (not to be confused with default
325  // constructor!) for second, so that, e.g. ints will be
326  // initialized to zero and pointers will be nullptr.
327  value_type value(key, mapped_type());
328 
329  pointer dest;
330  set_type::template insertHelper<false,true>(myBuckets,myNumBuckets,value,dest);
331  *dest = std::move(value);
332  ++*((size_type*)(myBuckets+myNumBuckets));
333  return dest->second;
334  }
335 
336  /// Returns a reference to the first value that is mapped-to from a key
337  /// matching key, inserting if none exist.
338  /// NOTE: If you use this, key cannot match the key of a pair
339  /// cleared by Clearer, else insertHelper will assert.
340  T &operator[](Key &&key)
341  {
342  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
343 
344  iterator it = find(key);
345  if (!it.atEnd())
346  return it->second;
347 
348  // NOTE: Must use value initialization (not to be confused with default
349  // constructor!) for second, so that, e.g. ints will be
350  // initialized to zero and pointers will be nullptr.
351  value_type value(std::move(key), mapped_type());
352 
353  pointer dest;
354  set_type::template insertHelper<false,true>(myBuckets,myNumBuckets,value,dest);
355  *dest = std::move(value);
356  ++*((size_type*)(myBuckets+myNumBuckets));
357  return dest->second;
358  }
359 
360  /// Returns a pair of iterators representing the range of values matching
361  /// key, as [first,second).
362  /// @{
363  std::pair<const_iterator,const_iterator> equal_range(const Key &key) const
364  {
365  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
366 
367  const const_pointer pstart = myBuckets;
368  const const_pointer pend = pstart + myNumBuckets;
369  if (!pstart)
370  return std::make_pair(const_iterator(nullptr,nullptr,false), const_iterator(nullptr,nullptr,false));
371 
372  const const_pointer search_start = searchStart(key);
373  if (!MULTI)
374  {
375  for (const_pointer p = search_start; p != pend; ++p)
376  {
377  if (key_equal()(key,p->first))
378  return std::make_pair(const_iterator(p,pend,false), const_iterator(p+1,pend,true));
379  if (Clearer::isClear(*p))
380  return std::make_pair(const_iterator(pend,pend,false), const_iterator(pend,pend,false));
381  }
382  // Hit the end, so search back from before the start of the block.
383  for (const_pointer p = search_start-1; p >= pstart; --p)
384  {
385  if (key_equal()(key,p->first))
386  return std::make_pair(const_iterator(p,pend,false), const_iterator(p+1,pend,true));
387  if (Clearer::isClear(*p))
388  return std::make_pair(const_iterator(pend,pend,false), const_iterator(pend,pend,false));
389  }
390  return std::make_pair(const_iterator(pend,pend,false), const_iterator(pend,pend,false));
391  }
392 
393  // MULTI is true, so we might have multiple matches
394  const_pointer first_found = nullptr;
395  const_pointer end_found = pend;
396  for (const_pointer p = search_start; p != pend; ++p)
397  {
398  if (key_equal()(key,p->first))
399  {
400  if (!first_found)
401  first_found = p;
402  }
403  else if (first_found)
404  {
405  if (first_found != search_start)
406  return std::make_pair(const_iterator(first_found,pend,false), const_iterator(p,pend,true));
407 
408  end_found = p;
409  break;
410  }
411  else if (Clearer::isClear(*p))
412  {
413  // NOTE: first_found must be false
414  return std::make_pair(const_iterator(pend,pend,false), const_iterator(pend,pend,false));
415  }
416  }
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  {
423  return std::make_pair(const_iterator(p+1,pend,false), const_iterator(end_found,pend,true));
424  }
425  }
426  return std::make_pair(const_iterator(pstart,pend,false), const_iterator(end_found,pend,true));
427  }
428  std::pair<iterator,iterator> equal_range(const Key &key)
429  {
430  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
431 
432  const pointer pstart = myBuckets;
433  const pointer pend = pstart + myNumBuckets;
434  if (!pstart)
435  return std::make_pair(iterator(nullptr,nullptr,false), iterator(nullptr,nullptr,false));
436 
437  const pointer search_start = searchStart(key);
438  if (!MULTI)
439  {
440  for (pointer p = search_start; p != pend; ++p)
441  {
442  if (key_equal()(key,p->first))
443  return std::make_pair(iterator(p,pend,false), iterator(p+1,pend,true));
444  if (Clearer::isClear(*p))
445  return std::make_pair(iterator(pend,pend,false), iterator(pend,pend,false));
446  }
447  // Hit the end, so search back from before the start of the block.
448  for (pointer p = search_start-1; p >= pstart; --p)
449  {
450  if (key_equal()(key,p->first))
451  return std::make_pair(iterator(p,pend,false), iterator(p+1,pend,true));
452  if (Clearer::isClear(*p))
453  return std::make_pair(iterator(pend,pend,false), iterator(pend,pend,false));
454  }
455  return std::make_pair(iterator(pend,pend,false), iterator(pend,pend,false));
456  }
457 
458  // MULTI is true, so we might have multiple matches
459  pointer first_found = nullptr;
460  pointer end_found = pend;
461  for (pointer p = search_start; p != pend; ++p)
462  {
463  if (key_equal()(key,p->first))
464  {
465  if (!first_found)
466  first_found = p;
467  }
468  else if (first_found)
469  {
470  if (first_found != search_start)
471  return std::make_pair(iterator(first_found,pend,false), iterator(p,pend,true));
472 
473  end_found = p;
474  break;
475  }
476  else if (Clearer::isClear(*p))
477  {
478  // NOTE: first_found must be false
479  return std::make_pair(iterator(pend,pend,false), iterator(pend,pend,false));
480  }
481  }
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  {
488  return std::make_pair(iterator(p+1,pend,false), iterator(end_found,pend,true));
489  }
490  }
491  return std::make_pair(iterator(pstart,pend,false), iterator(end_found,pend,true));
492  }
493  /// @}
494 
495  /// Inherit erase from ArraySet, in addition to signatures below.
496  using set_type::erase;
497 
498  /// Removes all items matching key and returns
499  /// the number of items removed.
500  size_type erase(const Key &key)
501  {
502  UT_ASSERT_MSG_P(!Clearer::isClear(key),"Don't query a clear key!");
503 
504  if (!MULTI)
505  {
506  iterator it = find(key);
507  if (it.atEnd())
508  return 0;
509  erase(it);
510  return 1;
511  }
512 
513  std::pair<iterator,iterator> its = equal_range(key);
514  size_type count = std::distance(its.first, its.second);
515  erase(its.first, its.second);
516  return count;
517  }
518 
519  template<typename FUNCTOR>
521  void forEachKey(FUNCTOR &&functor) const
522  {
524  const const_pointer pend = p + myNumBuckets;
525  for (; p != pend; ++p)
526  {
527  if (!Clearer::isClear(*p))
528  functor(p->first);
529  }
530  }
531 
532  template<typename FUNCTOR>
534  void forEachValue(FUNCTOR &&functor) const
535  {
537  const const_pointer pend = p + myNumBuckets;
538  for (; p != pend; ++p)
539  {
540  if (!Clearer::isClear(*p))
541  functor(p->second);
542  }
543  }
544 
545  template<bool constant_type>
547  {
548  public:
549  typedef std::forward_iterator_tag iterator_category;
550  typedef std::ptrdiff_t difference_type;
555 
556  template<typename COMPARATOR>
557  ordered_iterator_t(map_type &map, const COMPARATOR &comparator)
558  : myMap(map)
559  , myI(0)
560  {
561  myKeys.setCapacity(map.size());
562  map.forEachKey([this](const Key &key) {
563  myKeys.append(key);
564  });
565  myKeys.stdsort(comparator);
566  }
568  : myMap(that.myMap)
569  , myKeys(std::move(that.myKeys))
570  , myI(that.myI)
571  {}
573  {
574  return *myMap.find(myKeys[myI]);
575  }
577  {
578  return &*myMap.find(myKeys[myI]);
579  }
580  operator pointer() const
581  {
582  return &*myMap.find(myKeys[myI]);
583  }
584  void operator++()
585  {
586  ++myI;
587  }
588  bool atEnd() const
589  {
590  return myI >= myKeys.size();
591  }
592  private:
593  /// Use atEnd(), not ==
594  bool operator==(const ordered_iterator_t<constant_type> &) const = delete;
595  bool operator!=(const ordered_iterator_t<constant_type> &) const = delete;
596 
597  map_type &myMap;
598  UT_Array<Key> myKeys;
599  exint myI;
600  };
601 
602  template<typename COMPARATOR>
603  ordered_iterator_t<true> ordered_begin(const COMPARATOR &comparator) const
604  {
605  return ordered_iterator_t<true>(*this, comparator);
606  }
607 
608  template<typename COMPARATOR>
609  ordered_iterator_t<true> ordered_cbegin(const COMPARATOR &comparator) const
610  {
611  return ordered_iterator_t<true>(*this, comparator);
612  }
613 
614  template<typename COMPARATOR>
615  ordered_iterator_t<false> ordered_begin(const COMPARATOR &comparator)
616  {
617  return ordered_iterator_t<false>(*this, comparator);
618  }
619 
620 private:
621  /// GCC and Clang can't find base class members in templated code, so we
622  /// need to declare explicitly that we're inheriting them.
623  using set_type::myBuckets;
625 
626  pointer searchStart(const Key &key)
627  {
628  const size_type hash = hasher()(key);
629  return myBuckets + (hash%myNumBuckets);
630  }
631  const_pointer searchStart(const Key &key) const
632  {
633  const size_type hash = hasher()(key);
634  return myBuckets + (hash%myNumBuckets);
635  }
636 };
637 
638 template<
639  typename Key,
640  typename T,
641  bool MULTI,
642  std::size_t MAX_LOAD_FACTOR_256,
643  typename Clearer,
644  class Hash,
645  class KeyEqual
646 >
647 struct DefaultClearer<ArrayMap<Key,T,MULTI,MAX_LOAD_FACTOR_256,Clearer,Hash,KeyEqual> >
648  : public DefaultClearer<typename ArrayMap<Key,T,MULTI,MAX_LOAD_FACTOR_256,Clearer,Hash,KeyEqual>::set_type>
649 {};
650 
651 } // namespace UT
652 
653 #endif
ArrayMap< Key, T, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > map_type
Definition: UT_ArrayMap.h:71
T & at(const Key &key)
Definition: UT_ArrayMap.h:169
bool contains(const Key &key) const
Definition: UT_ArrayMap.h:284
SYS_FORCE_INLINE void forEachValue(FUNCTOR &&functor) const
Definition: UT_ArrayMap.h:534
ordered_iterator_t< true > ordered_cbegin(const COMPARATOR &comparator) const
Definition: UT_ArrayMap.h:609
ordered_iterator_t(map_type &map, const COMPARATOR &comparator)
Definition: UT_ArrayMap.h:557
const GLdouble * v
Definition: glcorearb.h:836
T & operator[](Key &&key)
Definition: UT_ArrayMap.h:340
std::conditional< constant_type, typename set_type::const_pointer, typename set_type::pointer >::type pointer
Definition: UT_ArrayMap.h:553
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
Definition: UT_ArrayMap.h:363
SYS_FORCE_INLINE void forEachKey(FUNCTOR &&functor) const
Definition: UT_ArrayMap.h:521
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:296
const T & at(const Key &key) const
Definition: UT_ArrayMap.h:206
std::forward_iterator_tag iterator_category
Definition: UT_ArrayMap.h:549
ordered_iterator_t< true > ordered_begin(const COMPARATOR &comparator) const
Definition: UT_ArrayMap.h:603
exint size() const
Definition: UT_Array.h:444
reference operator*() const
Definition: UT_ArrayMap.h:572
iterator find(const Key &key)
Definition: UT_ArrayMap.h:108
T & operator[](const Key &key)
Definition: UT_ArrayMap.h:316
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:244
std::conditional< constant_type, const typename ArrayMap::map_type, typename ArrayMap::map_type >::type map_type
Definition: UT_ArrayMap.h:554
std::conditional< constant_type, const value_type, value_type >::type & reference
Definition: UT_ArrayMap.h:552
bool operator()(const std::pair< Key, T > &a, const std::pair< Key, T > &b) const
Definition: UT_ArrayMap.h:23
typename set_type::const_pointer const_pointer
Definition: UT_ArrayMap.h:80
void setCapacity(exint newcapacity)
Definition: UT_ArrayImpl.h:751
typename set_type::size_type size_type
Definition: UT_ArrayMap.h:82
std::size_t size_type
Definition: UT_ArraySet.h:247
static void clearConstruct(std::pair< S0, S1 > *p)
Definition: UT_ArraySet.h:118
std::pair< iterator, iterator > equal_range(const Key &key)
Definition: UT_ArrayMap.h:428
T distance(const UT_Vector4T< T > &v1, const UT_Vector4T< T > &v2)
Definition: UT_Vector4.h:634
int64 exint
Definition: SYS_Types.h:109
size_t operator()(const std::pair< Key, T > &a) const
Definition: UT_ArrayMap.h:32
std::pair< iterator, bool > insert(const Key &key, const T &val)
Definition: UT_ArrayMap.h:96
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
Set iterator class.
Definition: UT_ArraySet.h:594
ordered_iterator_t(ordered_iterator_t< constant_type > &&that)
Definition: UT_ArrayMap.h:567
size_type erase(const Key &key)
Definition: UT_ArrayMap.h:500
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:45
ordered_iterator_t< false > ordered_begin(const COMPARATOR &comparator)
Definition: UT_ArrayMap.h:615
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:551
GLenum void ** pointer
Definition: glcorearb.h:809
const_iterator find(const Key &key) const
Definition: UT_ArrayMap.h:136
#define UT_ASSERT_MSG_P(ZZ, MM)
Definition: UT_Assert.h:104
size_type count(const Key &key) const
Definition: UT_ArrayMap.h:245
static bool isClear(const S0 &v)
An overload for when there's only a key.
Definition: UT_ArrayMap.h:50
typename set_type::iterator iterator
Inherit iterator and const_iterator.
Definition: UT_ArrayMap.h:85
const value_type * const_pointer
Definition: UT_ArraySet.h:254
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:109
KeyEqual key_equal
Definition: UT_ArrayMap.h:75
typename set_type::template iterator_t< constant_type > iterator_t
Definition: UT_ArrayMap.h:87
std::pair< iterator, bool > insert(Key &&key, T &&val)
Definition: UT_ArrayMap.h:100
#define UT_ASSERT_MSG(ZZ, MM)
Definition: UT_Assert.h:105
typename set_type::const_iterator const_iterator
Definition: UT_ArrayMap.h:88
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:70
value_type * pointer
Definition: UT_ArraySet.h:253