| // Copyright 2011 The Chromium Authors |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| // Derived from google3/util/gtl/stl_util.h |
| |
| #ifndef BASE_STL_UTIL_H_ |
| #define BASE_STL_UTIL_H_ |
| |
| #include<algorithm> |
| #include<iterator> |
| |
| #include"base/check.h" |
| |
| namespacebase{ |
| |
| // Returns a const reference to the underlying container of a container adapter. |
| // Works for std::priority_queue, std::queue, and std::stack. |
| template<class A> |
| consttypename A::container_type&GetUnderlyingContainer(const A& adapter){ |
| structExposedAdapter: A{ |
| using A::c; |
| }; |
| return adapter.*&ExposedAdapter::c; |
| } |
| |
| // Clears internal memory of an STL object. |
| // STL clear()/reserve(0) does not always free internal memory allocated |
| // This function uses swap/destructor to ensure the internal memory is freed. |
| template<class T> |
| voidSTLClearObject(T* obj){ |
| T tmp; |
| tmp.swap(*obj); |
| // Sometimes "T tmp" allocates objects with memory (arena implementation?). |
| // Hence using additional reserve(0) even if it doesn't always work. |
| obj->reserve(0); |
| } |
| |
| // Returns a new ResultType containing the difference of two sorted containers. |
| template<typenameResultType,typenameArg1,typenameArg2> |
| ResultTypeSTLSetDifference(constArg1& a1,constArg2& a2){ |
| DCHECK(std::ranges::is_sorted(a1)); |
| DCHECK(std::ranges::is_sorted(a2)); |
| ResultType difference; |
| std::set_difference(a1.begin(), a1.end(), a2.begin(), a2.end(), |
| std::inserter(difference, difference.end())); |
| return difference; |
| } |
| |
| // Returns a new ResultType containing the union of two sorted containers. |
| template<typenameResultType,typenameArg1,typenameArg2> |
| ResultTypeSTLSetUnion(constArg1& a1,constArg2& a2){ |
| DCHECK(std::ranges::is_sorted(a1)); |
| DCHECK(std::ranges::is_sorted(a2)); |
| ResultType result; |
| std::set_union(a1.begin(), a1.end(), a2.begin(), a2.end(), |
| std::inserter(result, result.end())); |
| return result; |
| } |
| |
| // Returns a new ResultType containing the intersection of two sorted |
| // containers. |
| template<typenameResultType,typenameArg1,typenameArg2> |
| ResultTypeSTLSetIntersection(constArg1& a1,constArg2& a2){ |
| DCHECK(std::ranges::is_sorted(a1)); |
| DCHECK(std::ranges::is_sorted(a2)); |
| ResultType result; |
| std::set_intersection(a1.begin(), a1.end(), a2.begin(), a2.end(), |
| std::inserter(result, result.end())); |
| return result; |
| } |
| |
| // A helper class to be used as the predicate with |EraseIf| to implement |
| // in-place set intersection. Helps implement the algorithm of going through |
| // each container an element at a time, erasing elements from the first |
| // container if they aren't in the second container. Requires each container be |
| // sorted. Note that the logic below appears inverted since it is returning |
| // whether an element should be erased. |
| template<classCollection> |
| classIsNotIn{ |
| public: |
| explicitIsNotIn(constCollection& collection) |
| : it_(collection.begin()), end_(collection.end()){} |
| |
| booloperator()(consttypenameCollection::value_type& x){ |
| while(it_!= end_&&*it_< x){ |
| ++it_; |
| } |
| if(it_== end_||*it_!= x){ |
| returntrue; |
| } |
| ++it_; |
| returnfalse; |
| } |
| |
| private: |
| typenameCollection::const_iterator it_; |
| consttypenameCollection::const_iterator end_; |
| }; |
| |
| }// namespace base |
| |
| #endif// BASE_STL_UTIL_H_ |
