This document is for a version of USD that is under development. See this page for the current release.
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules 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
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"
20
21#include <algorithm>
22#include <iterator>
23#include <map>
24#include <set>
25#include <utility>
26
27PXR_NAMESPACE_OPEN_SCOPE
28
29// Helper for TfMapLookup(). Uses std::map API to get a value by key.
30template <class T>
31struct Tf_MapLookupHelper {
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
68template <class Container, class Key, class Result>
69bool TfMapLookup(Container const &map, Key const &key, Result* valuePtr)
70{
71 return Tf_MapLookupHelper<Container>::Lookup(map, key, valuePtr);
72}
73
94template <class Container, class Key, class Result>
95const 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
122template <class Container, class Key>
123typename Container::mapped_type *
124TfMapLookupPtr(Container &map, Key const &key)
125{
126 typename Container::iterator i = map.find(key);
127 return (i != map.end()) ? &(i->second) : NULL;
128}
129
130template <class Container, class Key>
131typename Container::mapped_type const *
132TfMapLookupPtr(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
146template <typename T>
147inline std::pair<T,T>
148TfOrderedPair(T a, T b) {
149 return (a < b) ? std::pair<T,T>(a,b) : std::pair<T,T>(b,a);
150}
151
169template <class T>
170inline void TfReset(T &obj) {
171 T().swap(obj);
172}
173
174TF_API size_t Tf_GetEmptyHashMapBucketCount();
175
177template <class Key, class Value, class Hash, class Equal, class Alloc>
178inline void TfReset(TfHashMap<Key, Value, Hash, Equal, Alloc> &hash){
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)
188 TfHashMap<Key, Value, Hash, Equal, Alloc>(0).swap(hash);
189 else if (!hash.empty())
190 hash.clear();
191}
192
193TF_API size_t Tf_GetEmptyHashSetBucketCount();
194
196template <class Value, class Hash, class Equal, class Alloc>
197inline void TfReset(TfHashSet<Value, Hash, Equal, Alloc> &hash) {
198 static size_t emptyCount = Tf_GetEmptyHashSetBucketCount();
199
200 // See comment above about issues with TfHashSet(0).
201 if (hash.bucket_count() > emptyCount)
202 TfHashSet<Value, Hash, Equal, Alloc>(0).swap(hash);
203 else if (!hash.empty())
204 hash.clear();
205}
206
218template <class InputIterator1, class InputIterator2, class OutputIterator>
219void
220TfOrderedSetDifference(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
249template <class BackInsertionSequence,
250 class InputIterator1, class InputIterator2>
251BackInsertionSequence
252TfOrderedSetDifferenceToContainer(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
272template <class InputIterator1, class InputIterator2, class OutputIterator>
273void
274TfOrderedUniquingSetDifference(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
302template <class BackInsertionSequence,
303 class InputIterator1, class InputIterator2>
304BackInsertionSequence
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
324template <class ForwardIterator, class Predicate>
325static inline ForwardIterator
326TfFindBoundary(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
360template <size_t N>
361class TfGet
362{
363public:
364 template <class PairOrTuple>
365 using return_type = typename std::tuple_element<N, PairOrTuple>::type;
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>
374 constexpr const return_type<PairOrTuple>& operator()(
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
387PXR_NAMESPACE_CLOSE_SCOPE
388
389#endif // PXR_BASE_TF_STL_H
A simple iterator adapter for STL containers.
Function object for retrieving the N'th element of a std::pair or std::tuple.
Definition: stl.h:362
std::pair< T, T > TfOrderedPair(T a, T b)
Return an std::pair in sorted order.
Definition: stl.h:148
Container::mapped_type * TfMapLookupPtr(Container &map, Key const &key)
Checks if an item exists in a map or TfHashMap, without copying it.
Definition: stl.h:124
bool TfMapLookup(Container const &map, Key const &key, Result *valuePtr)
Checks if an item exists in a map or a TfHashMap.
Definition: stl.h:69
const Result TfMapLookupByValue(Container const &map, Key const &key, const Result &defaultValue)
Checks if an item exists in a map or a TfHashMap.
Definition: stl.h:95
void TfOrderedSetDifference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
Produce a sequence consisting of the set difference of [first1, last1) and [first2,...
Definition: stl.h:220
BackInsertionSequence TfOrderedUniquingSetDifferenceToContainer(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
Produce a sequence consisting of the set difference of the unique elements in [first1,...
Definition: stl.h:305
void TfReset(T &obj)
Reset obj to be an empty, space-optimized object.
Definition: stl.h:170
BackInsertionSequence TfOrderedSetDifferenceToContainer(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
Produce a sequence consisting of the set difference of [first1, last1) and [first2,...
Definition: stl.h:252
void TfOrderedUniquingSetDifference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
Produce a sequence consisting of the set difference of the unique elements in [first1,...
Definition: stl.h:274
A file containing basic constants and definitions.