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.