HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
stl.h
Go to the documentation of this file.
1 //
2 // Copyright 2016 Pixar
3 //
4 // Licensed under the terms set forth in the LICENSE.txt file available at
5 // https://openusd.org/license.
6 //
7 #ifndef PXR_BASE_TF_STL_H
8 #define PXR_BASE_TF_STL_H
9 
10 /// \file tf/stl.h
11 /// \ingroup group_tf_Stl
12 
13 #include "pxr/pxr.h"
14 
15 #include "pxr/base/tf/api.h"
16 #include "pxr/base/tf/tf.h"
17 #include "pxr/base/tf/hashmap.h"
18 #include "pxr/base/tf/hashset.h"
19 #include "pxr/base/tf/iterator.h"
20 
21 #include <algorithm>
22 #include <iterator>
23 #include <map>
24 #include <set>
25 #include <utility>
26 
28 
29 // Helper for TfMapLookup(). Uses std::map API to get a value by key.
30 template <class T>
32  typedef T Container;
33 
34  template <class Key, class Result>
35  static bool Lookup(Container const& map, Key const &key, Result* valuePtr)
36  {
37  typename Container::const_iterator i = map.find(key);
38  if (i == map.end()) {
39  return false;
40  }
41  else {
42  *valuePtr = i->second;
43  return true;
44  }
45  }
46 };
47 
48 /// Checks if an item exists in a \c map or a \c TfHashMap.
49 ///
50 /// If \p key exists in \p map, then this function returns \c true and the
51 /// value indexed by \p key is copied into \p *valuePtr. Otherwise,
52 /// \p *valuePtr is not modified, and \c false is returned.
53 ///
54 /// Example:
55 /// \code
56 /// TfHashMap<string, int, TfHash> m = ...;
57 /// int value;
58 ///
59 ///
60 /// if (TfMapLookup(m, "someKey", &value))
61 /// printf("Value found: %d\n", value);
62 /// else
63 /// printf("Value not found\n");
64 /// ...
65 /// \endcode
66 ///
67 /// \ingroup group_tf_Stl
68 template <class Container, class Key, class Result>
69 bool TfMapLookup(Container const &map, Key const &key, Result* valuePtr)
70 {
71  return Tf_MapLookupHelper<Container>::Lookup(map, key, valuePtr);
72 }
73 
74 /// Checks if an item exists in a \c map or a \c TfHashMap.
75 ///
76 /// If \p key exists in \p map, then this function returns the value index by
77 /// \p key. Otherwise, \p defaultValue is returned. Note that the result is
78 /// returned by value, so this is best used for types that are quick to copy.
79 ///
80 /// Example:
81 /// \code
82 /// TfHashMap<string, int, TfHash> m;
83 /// m["foo"] = 1;
84 ///
85 /// int value = TfMapLookupByValue(m, "someKey", -1);
86 /// TF_AXIOM(value == -1);
87 ///
88 /// int value = TfMapLookupByValue(m, "foo", -1);
89 /// TF_AXIOM(value == 1);
90 ///
91 /// \endcode
92 ///
93 /// \ingroup group_tf_Stl
94 template <class Container, class Key, class Result>
95 const Result TfMapLookupByValue(Container const &map,
96  Key const &key, const Result &defaultValue)
97 {
98  typename Container::const_iterator i = map.find(key);
99  if (i == map.end()) {
100  return defaultValue;
101  } else {
102  return i->second;
103  }
104 }
105 
106 /// Checks if an item exists in a \c map or \c TfHashMap, without copying it.
107 ///
108 /// If \p key exists in the \p map, then this function returns a pointer to
109 /// the value indexed by \p key. Otherwise, NULL is returned.
110 ///
111 /// Example:
112 /// \code
113 /// TfHashMap<string, BigData, TfHash> m = ...;
114 ///
115 /// if (BigData* bigPtr = TfMapLookupPtr(m, "someKey"))
116 /// bigPtr->ModifyStuff();
117 /// else
118 /// printf("Value not found\n");
119 /// \endcode
120 ///
121 /// \ingroup group_tf_Stl
122 template <class Container, class Key>
123 typename Container::mapped_type *
124 TfMapLookupPtr(Container &map, Key const &key)
125 {
126  typename Container::iterator i = map.find(key);
127  return (i != map.end()) ? &(i->second) : NULL;
128 }
129 
130 template <class Container, class Key>
131 typename Container::mapped_type const *
132 TfMapLookupPtr(Container const &map, Key const &key)
133 {
134  typename Container::const_iterator i = map.find(key);
135  return (i != map.end()) ? &(i->second) : NULL;
136 }
137 
138 /// Return an \c std::pair in sorted order.
139 ///
140 /// This call is a useful helper for maps whose key is an unordered pair of
141 /// elements. One can either define a new data type such that (a,b) is deemed
142 /// equivalent to (b,a), or more simply, adopt the convention that a key is
143 /// always written (a,b) with a < b.
144 ///
145 /// \ingroup group_tf_Stl
146 template <typename T>
147 inline std::pair<T,T>
149  return (a < b) ? std::pair<T,T>(a,b) : std::pair<T,T>(b,a);
150 }
151 
152 /// Reset \a obj to be an empty, space-optimized object.
153 ///
154 /// This can be used to clear c++ containers and reclaim their memory. For
155 /// instance, std::vector::clear() will not reclaim any memory, even if the
156 /// vector previously had a large number of elements. Often, this is what you
157 /// want because the vector is later filled again. But sometimes you want to
158 /// reclaim the memory, and this function will do that.
159 ///
160 /// As another example, gcc's hash_map and hash_set do not clear their bucket
161 /// lists when they themselves are cleared. This can lead to poor performance
162 /// due to ever-growing bucket lists for hashes that are repeatedly filled,
163 /// cleared, and filled again. TfReset will avoid this by effectively
164 /// clearing the bucket list.
165 ///
166 /// This function requires that the expression T().swap(obj) where obj is of
167 /// type T& be valid. This is true for many classes, including the standard
168 /// containers.
169 template <class T>
170 inline void TfReset(T &obj) {
171  T().swap(obj);
172 }
173 
175 
176 /// Specialize for TfHashMap to make minimally sized hashes.
177 template <class Key, class Value, class Hash, class Equal, class Alloc>
179  // If the implementation of the hash map allocates buckets when
180  // constructed asking for zero then only swap a constructed object
181  // if \p hash has more than that many buckets already, otherwise
182  // we just clear(). Note that this assumes that the number of
183  // buckets does not depend on the template parameter types which
184  // is reasonable.
185  static size_t emptyCount = Tf_GetEmptyHashMapBucketCount();
186 
187  if (hash.bucket_count() > emptyCount)
189  else if (!hash.empty())
190  hash.clear();
191 }
192 
194 
195 /// Specialize for TfHashSet to make minimally sized hashes.
196 template <class Value, class Hash, class Equal, class Alloc>
198  static size_t emptyCount = Tf_GetEmptyHashSetBucketCount();
199 
200  // See comment above about issues with TfHashSet(0).
201  if (hash.bucket_count() > emptyCount)
203  else if (!hash.empty())
204  hash.clear();
205 }
206 
207 /// Produce a sequence consisting of the set difference of [\a first1, \a
208 /// last1) and [\a first2, \a last2), while maintaining the relative order of
209 /// the first sequence. No particular order is required for either range, but
210 /// elements must have a strict weak order provided by operator<.
211 ///
212 /// If an element appears multiple times in either the first or second
213 /// sequence, the number of occurrences in the output is the difference
214 /// between the first sequence and the second (or zero if there are more
215 /// occurrences in the second sequence). For example, if the first sequence
216 /// is (1, 3, 3, 1) and the second sequence is (2, 3, 2), the result will be
217 /// (1, 3, 1).
218 template <class InputIterator1, class InputIterator2, class OutputIterator>
219 void
220 TfOrderedSetDifference(InputIterator1 first1, InputIterator1 last1,
221  InputIterator2 first2, InputIterator2 last2,
222  OutputIterator result)
223 {
224  typedef std::multiset<typename InputIterator2::value_type> SetType;
225  SetType set2(first2, last2);
226 
227  // Walk [first1, last1). If the element is in set2, skip it, and remove one
228  // of those elements from set2, otherwise output it.
229  for (InputIterator1 i = first1; i != last1; ++i) {
230  typename SetType::iterator j = set2.find(*i);
231  if (j != set2.end())
232  set2.erase(j);
233  else
234  *result++ = *i;
235  }
236 }
237 
238 /// Produce a sequence consisting of the set difference of [\a first1, \a
239 /// last1) and [\a first2, \a last2), while maintaining the relative order of
240 /// the first sequence. No particular order is required for either range, but
241 /// elements must have a strict weak order provided by operator<.
242 ///
243 /// If an element appears multiple times in either the first or second
244 /// sequence, the number of occurrences in the output is the difference
245 /// between the first sequence and the second (or zero if there are more
246 /// occurrences in the second sequence). For example, if the first sequence
247 /// is (1, 3, 3, 1) and the second sequence is (2, 3, 2), the result will be
248 /// (1, 3, 1).
249 template <class BackInsertionSequence,
250  class InputIterator1, class InputIterator2>
251 BackInsertionSequence
252 TfOrderedSetDifferenceToContainer(InputIterator1 first1, InputIterator1 last1,
253  InputIterator2 first2, InputIterator2 last2)
254 {
255  BackInsertionSequence result;
256  TfOrderedSetDifference(first1, last1, first2, last2,
257  std::back_inserter(result));
258  return result;
259 }
260 
261 /// Produce a sequence consisting of the set difference of the unique elements
262 /// in [\a first1, \a last1) and [\a first2, \a last2), while maintaining the
263 /// relative order of the first sequence. No particular order is required for
264 /// either range, but elements must have a strict weak order provided by
265 /// operator<.
266 ///
267 /// If an element appears multiple times in the first sequence, it appears
268 /// either zero or one times in the output. It appears zero times if it
269 /// appears in the second sequence, and one time if it does not. For example,
270 /// if the first sequence is (1, 3, 3, 1) and the second sequence is (2, 3,
271 /// 2), the result will be (1).
272 template <class InputIterator1, class InputIterator2, class OutputIterator>
273 void
274 TfOrderedUniquingSetDifference(InputIterator1 first1, InputIterator1 last1,
275  InputIterator2 first2, InputIterator2 last2,
276  OutputIterator result)
277 {
278  typedef std::set<typename InputIterator1::value_type> Set1Type;
279  typedef std::set<typename InputIterator2::value_type> Set2Type;
280 
281  Set1Type set1;
282  Set2Type set2(first2, last2);
283 
284  // Walk [first1, last1). If the element is in set1, skip it. Else insert
285  // it into set1, and if the element is not in set2, output it.
286  for (InputIterator1 i = first1; i != last1; ++i)
287  if (set1.insert(*i).second && !set2.count(*i))
288  *result++ = *i;
289 }
290 
291 /// Produce a sequence consisting of the set difference of the unique elements
292 /// in [\a first1, \a last1) and [\a first2, \a last2), while maintaining the
293 /// relative order of the first sequence. No particular order is required for
294 /// either range, but elements must have a strict weak order provided by
295 /// operator<.
296 ///
297 /// If an element appears multiple times in the first sequence, it appears
298 /// either zero or one times in the output. It appears zero times if it
299 /// appears in the second sequence, and one time if it does not. For example,
300 /// if the first sequence is (1, 3, 3, 1) and the second sequence is (2, 3,
301 /// 2), the result will be (1).
302 template <class BackInsertionSequence,
303  class InputIterator1, class InputIterator2>
304 BackInsertionSequence
306  InputIterator1 last1,
307  InputIterator2 first2,
308  InputIterator2 last2)
309 {
310  BackInsertionSequence result;
311  TfOrderedUniquingSetDifference(first1, last1, first2, last2,
312  std::back_inserter(result));
313  return result;
314 }
315 
316 /// A version of binary search that finds the boundary in a partitioned
317 /// sequence. The Predicate pred should return true for objects on the
318 /// 'first' side (or left-hand) side of the boundary.
319 ///
320 /// More precisely, given a range [first, last) and a Predicate pred for which
321 /// there is exactly one iterator called mid in that range such that pred(x)
322 /// is true for every x in [first, mid) and false for every x in [mid, last),
323 /// return mid.
324 template <class ForwardIterator, class Predicate>
325 static inline ForwardIterator
326 TfFindBoundary(ForwardIterator first, ForwardIterator last,
327  Predicate const &pred)
328 {
329  size_t len = std::distance(first, last);
330  size_t half;
331  ForwardIterator middle;
332 
333  while (len > 0) {
334  half = len >> 1;
335  middle = first;
336  std::advance(middle, half);
337  if (pred(*middle)) {
338  first = middle;
339  ++first;
340  len = len - half - 1;
341  }
342  else
343  len = half;
344  }
345  return first;
346 }
347 
348 /// Function object for retrieving the N'th element of a std::pair
349 /// or std::tuple. This is similar to std::get<N>, but wrapped up in a
350 /// function object suitable for use with STL algorithms.
351 ///
352 /// Example:
353 /// \code
354 /// const std::vector<std::pair<int, std::string>> pairs = { ... }
355 /// std::vector<int> intsOnly(pairs.size());
356 /// std::transform(pairs.begin(), pairs.end(), intsOnly.begin(), TfGet<0>());
357 /// \endcode
358 ///
359 /// \ingroup group_tf_Stl
360 template <size_t N>
361 class TfGet
362 {
363 public:
364  template <class PairOrTuple>
366 
367  template <class PairOrTuple>
368  constexpr return_type<PairOrTuple>& operator()(PairOrTuple& p) const
369  {
370  return std::get<N>(p);
371  }
372 
373  template <class PairOrTuple>
375  const PairOrTuple& p) const
376  {
377  return std::get<N>(p);
378  }
379 
380  template <class PairOrTuple>
381  constexpr return_type<PairOrTuple>&& operator()(PairOrTuple&& p) const
382  {
383  return std::get<N>(std::move(p));
384  }
385 };
386 
388 
389 #endif // PXR_BASE_TF_STL_H
type
Definition: core.h:556
GLint first
Definition: glcorearb.h:405
static bool Lookup(Container const &map, Key const &key, Result *valuePtr)
Definition: stl.h:35
void TfReset(T &obj)
Definition: stl.h:170
#define TF_API
Definition: api.h:23
imath_half_bits_t half
if we're in a C-only context, alias the half bits type to half
Definition: half.h:266
void swap(TfHashMap &other)
Definition: hashmap.h:331
void swap(TfHashSet &other)
Definition: hashset.h:326
TF_API size_t Tf_GetEmptyHashSetBucketCount()
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
std::pair< T, T > TfOrderedPair(T a, T b)
Definition: stl.h:148
**But if you need a result
Definition: thread.h:622
void TfOrderedSetDifference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
Definition: stl.h:220
constexpr return_type< PairOrTuple > && operator()(PairOrTuple &&p) const
Definition: stl.h:381
BackInsertionSequence TfOrderedSetDifferenceToContainer(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
Definition: stl.h:252
bool TfMapLookup(Container const &map, Key const &key, Result *valuePtr)
Definition: stl.h:69
constexpr const return_type< PairOrTuple > & operator()(const PairOrTuple &p) const
Definition: stl.h:374
BackInsertionSequence TfOrderedUniquingSetDifferenceToContainer(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
Definition: stl.h:305
void TfOrderedUniquingSetDifference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
Definition: stl.h:274
Container::mapped_type * TfMapLookupPtr(Container &map, Key const &key)
Definition: stl.h:124
Definition: stl.h:361
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
__hostdev__ uint64_t last(uint32_t i) const
Definition: NanoVDB.h:5976
GLint j
Definition: glad.h:2733
constexpr return_type< PairOrTuple > & operator()(PairOrTuple &p) const
Definition: stl.h:368
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1425
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:74
SIM_API const UT_StringHolder distance
typename std::tuple_element< N, PairOrTuple >::type return_type
Definition: stl.h:365
TF_API size_t Tf_GetEmptyHashMapBucketCount()
const Result TfMapLookupByValue(Container const &map, Key const &key, const Result &defaultValue)
Definition: stl.h:95