14#ifndef OR_TOOLS_BASE_STL_UTIL_H_
15#define OR_TOOLS_BASE_STL_UTIL_H_
23#include <forward_list>
33#include "absl/meta/type_traits.h"
34#include "absl/strings/internal/resize_uninitialized.h"
40template <
typename LessFunc>
43 explicit Equiv(
const LessFunc& f) : f_(f) {}
46 return !f_(
b,
a) && !f_(
a,
b);
57template <
typename T,
typename LessFunc>
59 std::sort(v->begin(), v->end(), less_func);
60 v->erase(std::unique(v->begin(), v->end(),
66 std::sort(v->begin(), v->end());
67 v->erase(std::unique(v->begin(), v->end()), v->end());
74template <
typename T,
typename LessFunc>
76 std::stable_sort(v->begin(), v->end(), less_func);
77 v->erase(std::unique(v->begin(), v->end(),
86 std::stable_sort(v->begin(), v->end());
87 v->erase(std::unique(v->begin(), v->end()), v->end());
92template <
typename T,
typename E>
94 v->erase(std::remove(v->begin(), v->end(), e), v->end());
96template <
typename T,
typename A,
typename E>
100template <
typename T,
typename A,
typename E>
106template <
typename T,
typename P>
108 v->erase(std::remove_if(v->begin(), v->end(), pred), v->end());
110template <
typename T,
typename A,
typename P>
114template <
typename T,
typename A,
typename P>
131template <
typename T,
typename A>
133 std::deque<T, A> tmp;
146 if (obj->capacity() >= limit) {
153template <
typename T,
typename A>
155 if (obj->size() >= limit) {
181 if (obj->bucket_count() >= limit) {
195 if (min_capacity > s->capacity()) s->reserve(min_capacity);
202template <
typename T,
typename Traits,
typename Alloc>
213template <
typename T,
typename Traits,
typename Alloc>
215 const std::basic_string<T, Traits, Alloc>& s) {
229 memcpy(&*str->begin(), ptr, n);
241 size_t old_size = str->size();
243 memcpy(&*str->begin() + old_size, ptr, n);
262 return str->empty() ? nullptr : &*str->begin();
269template <
typename HashSet>
271 if (set_a.size() != set_b.size())
return false;
272 for (
typename HashSet::const_iterator i = set_a.begin(); i != set_a.end();
274 if (set_b.find(*i) == set_b.end())
return false;
281template <
typename HashMap,
typename BinaryPredicate>
283 BinaryPredicate mapped_type_equal) {
284 if (map_a.size() != map_b.size())
return false;
285 for (
typename HashMap::const_iterator i = map_a.begin(); i != map_a.end();
287 typename HashMap::const_iterator j = map_b.find(i->first);
288 if (j == map_b.end())
return false;
289 if (!mapped_type_equal(i->second, j->second))
return false;
296template <
typename K,
typename V,
typename C,
typename A>
298 const std::map<K, V, C, A>& map_b) {
299 return map_a == map_b;
302template <
typename HashMap>
304 using Mapped =
typename HashMap::mapped_type;
313template <
typename ForwardIterator>
315 while (begin != end) {
324template <
typename ForwardIterator>
326 ForwardIterator end) {
327 while (begin != end) {
337template <
typename ForwardIterator>
339 ForwardIterator end) {
340 while (begin != end) {
352template <
typename ForwardIterator>
354 ForwardIterator end) {
355 while (begin != end) {
373 if (!container)
return;
407template <
typename STLContainer>
418 STLContainer* container_ptr_;
436 template <
typename STLContainer>
453template <
typename STLContainer>
464 STLContainer* container_ptr_;
478 template <
typename STLContainer>
496template <
typename STLContainer>
503 STLContainer* container_ptr_;
511template <
typename STLContainer>
518 STLContainer* container_ptr_;
540namespace stl_util_internal {
544 template <
typename T>
547 return std::less<T>()(
a,
b);
549 template <
typename T1,
typename T2>
559template <
typename,
typename =
void,
typename =
void>
567 absl::void_t<typename T::reverse_iterator>> : std::false_type {
594template <
typename In1,
typename In2,
typename Out,
typename Compare>
597 "In1 must be an ordered set");
599 "In2 must be an ordered set");
600 assert(std::is_sorted(
a.begin(),
a.end(), compare));
601 assert(std::is_sorted(
b.begin(),
b.end(), compare));
602 assert(
static_cast<const void*
>(&
a) !=
static_cast<const void*
>(out));
603 assert(
static_cast<const void*
>(&
b) !=
static_cast<const void*
>(out));
604 std::set_difference(
a.begin(),
a.end(),
b.begin(),
b.end(),
605 std::inserter(*out, out->end()), compare);
611template <
typename In1,
typename In2,
typename Out>
617template <
typename Out,
typename In1,
typename In2,
typename Compare>
624template <
typename Out,
typename In1,
typename In2>
626 return STLSetDifferenceAs<Out>(
a,
b,
630template <
typename In1,
typename In2,
typename Compare>
632 return STLSetDifferenceAs<In1>(
a,
b, compare);
635template <
typename In1,
typename In2>
639template <
typename In1>
658template <
typename In1,
typename In2,
typename Out,
typename Compare>
661 "In1 must be an ordered set");
663 "In2 must be an ordered set");
664 assert(std::is_sorted(
a.begin(),
a.end(), compare));
665 assert(std::is_sorted(
b.begin(),
b.end(), compare));
666 assert(
static_cast<const void*
>(&
a) !=
static_cast<const void*
>(out));
667 assert(
static_cast<const void*
>(&
b) !=
static_cast<const void*
>(out));
668 std::set_union(
a.begin(),
a.end(),
b.begin(),
b.end(),
669 std::inserter(*out, out->end()), compare);
674template <
typename In1,
typename In2,
typename Out>
676 const In1&
a,
const In2&
b, Out* out) {
679template <
typename Out,
typename In1,
typename In2,
typename Compare>
685template <
typename Out,
typename In1,
typename In2>
689template <
typename In1,
typename In2,
typename Compare>
691 return STLSetUnionAs<In1>(
a,
b, compare);
693template <
typename In1,
typename In2>
697template <
typename In1>
717template <
typename In1,
typename In2,
typename Out,
typename Compare>
721 "In1 must be an ordered set");
723 "In2 must be an ordered set");
724 assert(std::is_sorted(
a.begin(),
a.end(), compare));
725 assert(std::is_sorted(
b.begin(),
b.end(), compare));
726 assert(
static_cast<const void*
>(&
a) !=
static_cast<const void*
>(out));
727 assert(
static_cast<const void*
>(&
b) !=
static_cast<const void*
>(out));
728 std::set_symmetric_difference(
a.begin(),
a.end(),
b.begin(),
b.end(),
729 std::inserter(*out, out->end()), compare);
734template <
typename In1,
typename In2,
typename Out>
740template <
typename Out,
typename In1,
typename In2,
typename Compare>
746template <
typename Out,
typename In1,
typename In2>
748 return STLSetSymmetricDifferenceAs<Out>(
751template <
typename In1,
typename In2,
typename Compare>
753 return STLSetSymmetricDifferenceAs<In1>(
a,
b, comp);
755template <
typename In1,
typename In2>
760template <
typename In1>
780template <
typename In1,
typename In2,
typename Out,
typename Compare>
783 "In1 must be an ordered set");
785 "In2 must be an ordered set");
786 assert(std::is_sorted(
a.begin(),
a.end(), compare));
787 assert(std::is_sorted(
b.begin(),
b.end(), compare));
788 assert(
static_cast<const void*
>(&
a) !=
static_cast<const void*
>(out));
789 assert(
static_cast<const void*
>(&
b) !=
static_cast<const void*
>(out));
790 std::set_intersection(
a.begin(),
a.end(),
b.begin(),
b.end(),
791 std::inserter(*out, out->end()), compare);
796template <
typename In1,
typename In2,
typename Out>
802template <
typename Out,
typename In1,
typename In2,
typename Compare>
808template <
typename Out,
typename In1,
typename In2>
810 return STLSetIntersectionAs<Out>(
a,
b,
813template <
typename In1,
typename In2,
typename Compare>
815 return STLSetIntersectionAs<In1>(
a,
b, compare);
817template <
typename In1,
typename In2>
821template <
typename In1>
828template <
typename In1,
typename In2,
typename Compare>
831 "In1 must be an ordered set");
833 "In2 must be an ordered set");
834 assert(std::is_sorted(
a.begin(),
a.end(), compare));
835 assert(std::is_sorted(
b.begin(),
b.end(), compare));
836 return std::includes(
a.begin(),
a.end(),
b.begin(),
b.end(), compare);
838template <
typename In1,
typename In2>
855template <
typename InputIterator1,
typename InputIterator2,
typename Comp>
857 InputIterator2 begin2, InputIterator2 end2,
859 assert(std::is_sorted(begin1, end1, comparator));
860 assert(std::is_sorted(begin2, end2, comparator));
861 while (begin1 != end1 && begin2 != end2) {
862 if (comparator(*begin1, *begin2)) {
866 if (comparator(*begin2, *begin1)) {
874template <
typename InputIterator1,
typename InputIterator2>
876 InputIterator2 begin2, InputIterator2 end2) {
885template <
typename In1,
typename In2,
typename Comp>
889 in2.end(), comparator);
891template <
typename In1,
typename In2>
909template <
typename T,
typename Alloc = std::allocator<T>>
920 template <
typename U,
typename B>
925 std::allocator<void>::const_pointer hint =
nullptr) {
926 assert(bytes_used_ !=
nullptr);
927 *bytes_used_ += n *
sizeof(T);
928 return Alloc::allocate(n, hint);
932 Alloc::deallocate(p, n);
933 assert(bytes_used_ !=
nullptr);
934 *bytes_used_ -= n *
sizeof(T);
938 template <
typename U>
959 template <
typename U,
typename B>
963 template <
typename U>
976template <
typename T,
typename A>
980 return static_cast<const Base&
>(
a) ==
static_cast<const Base&
>(
b) &&
981 a.bytes_used() ==
b.bytes_used();
984template <
typename T,
typename A>
void operator=(const BaseDeleter &)=delete
BaseDeleter(const BaseDeleter &)=delete
ElementDeleter(const ElementDeleter &)=delete
void operator=(const ElementDeleter &)=delete
ElementDeleter(STLContainer *ptr)
STLCountingAllocator(const STLCountingAllocator< U, B > &x)
STLCountingAllocator(int64 *b)
int64 * bytes_used() const
STLCountingAllocator(const STLCountingAllocator< U, B > &x)
pointer allocate(size_type n, std::allocator< void >::const_pointer hint=nullptr)
STLCountingAllocator(int64 *b)
int64 * bytes_used() const
void deallocate(pointer p, size_type n)
typename Alloc::pointer pointer
typename Alloc::size_type size_type
STLElementDeleter(STLContainer *ptr)
STLValueDeleter(STLContainer *ptr)
TemplatedElementDeleter(const TemplatedElementDeleter &)=delete
void operator=(const TemplatedElementDeleter &)=delete
TemplatedElementDeleter(STLContainer *ptr)
virtual ~TemplatedElementDeleter()
void operator=(const TemplatedValueDeleter &)=delete
TemplatedValueDeleter(STLContainer *ptr)
TemplatedValueDeleter(const TemplatedValueDeleter &)=delete
virtual ~TemplatedValueDeleter()
void operator=(const ValueDeleter &)=delete
ValueDeleter(const ValueDeleter &)=delete
ValueDeleter(STLContainer *ptr)
bool operator()(const T &a, const T &b) const
Out STLSetIntersectionAs(const In1 &a, const In2 &b, Compare compare)
bool SortedContainersHaveIntersection(const In1 &in1, const In2 &in2, Comp comparator)
bool STLStringSupportsNontrashingResize(const std::basic_string< T, Traits, Alloc > &s)
void STLSetIntersection(const In1 &a, const In2 &b, Out *out, Compare compare)
bool operator!=(const STLCountingAllocator< T, A > &a, const STLCountingAllocator< T, A > &b)
Out STLSetSymmetricDifferenceAs(const In1 &a, const In2 &b, Compare comp)
void STLClearHashIfBig(T *obj, size_t limit)
void STLDeleteValues(T *v)
ABSL_MUST_USE_RESULT T * release_ptr(T **ptr)
void STLSetSymmetricDifference(const In1 &a, const In2 &b, Out *out, Compare compare)
void STLSetDifference(const In1 &a, const In2 &b, Out *out, Compare compare)
void STLClearObject(T *obj)
void STLAppendToString(std::string *str, const char *ptr, size_t n)
void STLDeleteContainerPairFirstPointers(ForwardIterator begin, ForwardIterator end)
void STLStableSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
void STLAssignToString(std::string *str, const char *ptr, size_t n)
char * string_as_array(std::string *str)
void STLEraseAllFromSequenceIf(T *v, P pred)
bool HashMapEquality(const HashMap &map_a, const HashMap &map_b, BinaryPredicate mapped_type_equal)
void STLDeleteContainerPairSecondPointers(ForwardIterator begin, ForwardIterator end)
void STLStringReserveIfNeeded(std::string *s, size_t min_capacity)
bool operator==(const STLCountingAllocator< T, A > &a, const STLCountingAllocator< T, A > &b)
void STLDeleteElements(T *container)
bool STLIncludes(const In1 &a, const In2 &b, Compare compare)
Out STLSetDifferenceAs(const In1 &a, const In2 &b, Compare compare)
bool SortedRangesHaveIntersection(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, Comp comparator)
void STLDeleteContainerPointers(ForwardIterator begin, ForwardIterator end)
void STLClearIfBig(T *obj, size_t limit=1<< 20)
void STLSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
bool HashSetEquality(const HashSet &set_a, const HashSet &set_b)
void STLStringResizeUninitialized(std::basic_string< T, Traits, Alloc > *s, size_t new_size)
void STLDeleteContainerPairPointers(ForwardIterator begin, ForwardIterator end)
Out STLSetUnionAs(const In1 &a, const In2 &b, Compare compare)
void STLEraseAllFromSequence(T *v, const E &e)
void STLSetUnion(const In1 &a, const In2 &b, Out *out, Compare compare)
bool operator()(const T1 &a, const T2 &b) const
bool operator()(const T &a, const T &b) const