14#ifndef OR_TOOLS_BASE_STL_UTIL_H_
15#define OR_TOOLS_BASE_STL_UTIL_H_
23#include <forward_list>
31#include "absl/base/attributes.h"
32#include "absl/meta/type_traits.h"
33#include "absl/strings/internal/resize_uninitialized.h"
37template <
typename LessFunc>
40 explicit Equiv(
const LessFunc& f) : f_(f) {}
43 return !f_(b, a) && !f_(a, b);
54template <
typename T,
typename LessFunc>
56 std::sort(v->begin(), v->end(), less_func);
57 v->erase(std::unique(v->begin(), v->end(),
63 std::sort(v->begin(), v->end());
64 v->erase(std::unique(v->begin(), v->end()), v->end());
71template <
typename T,
typename LessFunc>
73 std::stable_sort(v->begin(), v->end(), less_func);
74 v->erase(std::unique(v->begin(), v->end(),
83 std::stable_sort(v->begin(), v->end());
84 v->erase(std::unique(v->begin(), v->end()), v->end());
89template <
typename T,
typename E>
91 v->erase(std::remove(v->begin(), v->end(), e), v->end());
93template <
typename T,
typename A,
typename E>
97template <
typename T,
typename A,
typename E>
103template <
typename T,
typename P>
105 v->erase(std::remove_if(v->begin(), v->end(), pred), v->end());
107template <
typename T,
typename A,
typename P>
111template <
typename T,
typename A,
typename P>
128template <
typename T,
typename A>
130 std::deque<T, A> tmp;
143 if (obj->capacity() >= limit) {
150template <
typename T,
typename A>
152 if (obj->size() >= limit) {
178 if (obj->bucket_count() >= limit) {
192 if (min_capacity > s->capacity()) s->reserve(min_capacity);
199template <
typename T,
typename Traits,
typename Alloc>
202 absl::strings_internal::STLStringResizeUninitialized(s, new_size);
210template <
typename T,
typename Traits,
typename Alloc>
212 const std::basic_string<T, Traits, Alloc>& s) {
213 return absl::strings_internal::STLStringSupportsNontrashingResize(&s);
226 memcpy(&*str->begin(), ptr, n);
238 size_t old_size = str->size();
240 memcpy(&*str->begin() + old_size, ptr, n);
259 return str->empty() ? nullptr : &*str->begin();
266template <
typename HashSet>
268 if (set_a.size() != set_b.size())
return false;
269 for (
typename HashSet::const_iterator i = set_a.begin(); i != set_a.end();
271 if (set_b.find(*i) == set_b.end())
return false;
278template <
typename HashMap,
typename BinaryPredicate>
280 BinaryPredicate mapped_type_equal) {
281 if (map_a.size() != map_b.size())
return false;
282 for (
typename HashMap::const_iterator i = map_a.begin(); i != map_a.end();
284 typename HashMap::const_iterator j = map_b.find(i->first);
285 if (j == map_b.end())
return false;
286 if (!mapped_type_equal(i->second, j->second))
return false;
293template <
typename K,
typename V,
typename C,
typename A>
295 const std::map<K, V, C, A>& map_b) {
296 return map_a == map_b;
299template <
typename HashMap>
301 using Mapped =
typename HashMap::mapped_type;
310template <
typename ForwardIterator>
312 while (begin != end) {
321template <
typename ForwardIterator>
323 ForwardIterator end) {
324 while (begin != end) {
334template <
typename ForwardIterator>
336 ForwardIterator end) {
337 while (begin != end) {
349template <
typename ForwardIterator>
351 ForwardIterator end) {
352 while (begin != end) {
370 if (!container)
return;
404template <
typename STLContainer>
415 STLContainer* container_ptr_;
433 template <
typename STLContainer>
450template <
typename STLContainer>
461 STLContainer* container_ptr_;
475 template <
typename STLContainer>
493template <
typename STLContainer>
500 STLContainer* container_ptr_;
508template <
typename STLContainer>
515 STLContainer* container_ptr_;
541 template <
typename T>
544 return std::less<T>()(a, b);
546 template <
typename T1,
typename T2>
556template <
typename,
typename =
void,
typename =
void>
564 absl::void_t<typename T::reverse_iterator>> : std::false_type {
591template <
typename In1,
typename In2,
typename Out,
typename Compare>
594 "In1 must be an ordered set");
596 "In2 must be an ordered set");
597 assert(std::is_sorted(a.begin(), a.end(), compare));
598 assert(std::is_sorted(b.begin(), b.end(), compare));
599 assert(
static_cast<const void*
>(&a) !=
static_cast<const void*
>(out));
600 assert(
static_cast<const void*
>(&b) !=
static_cast<const void*
>(out));
601 std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
602 std::inserter(*out, out->end()), compare);
608template <
typename In1,
typename In2,
typename Out>
609typename std::enable_if<!std::is_function<Out>::value,
void>::type
614template <
typename Out,
typename In1,
typename In2,
typename Compare>
621template <
typename Out,
typename In1,
typename In2>
627template <
typename In1,
typename In2,
typename Compare>
632template <
typename In1,
typename In2>
636template <
typename In1>
655template <
typename In1,
typename In2,
typename Out,
typename Compare>
656void STLSetUnion(
const In1& a,
const In2& b, Out* out, Compare compare) {
658 "In1 must be an ordered set");
660 "In2 must be an ordered set");
661 assert(std::is_sorted(a.begin(), a.end(), compare));
662 assert(std::is_sorted(b.begin(), b.end(), compare));
663 assert(
static_cast<const void*
>(&a) !=
static_cast<const void*
>(out));
664 assert(
static_cast<const void*
>(&b) !=
static_cast<const void*
>(out));
665 std::set_union(a.begin(), a.end(), b.begin(), b.end(),
666 std::inserter(*out, out->end()), compare);
671template <
typename In1,
typename In2,
typename Out>
672typename std::enable_if<!std::is_function<Out>::value,
void>::type
STLSetUnion(
673 const In1& a,
const In2& b, Out* out) {
676template <
typename Out,
typename In1,
typename In2,
typename Compare>
677Out
STLSetUnionAs(
const In1& a,
const In2& b, Compare compare) {
682template <
typename Out,
typename In1,
typename In2>
686template <
typename In1,
typename In2,
typename Compare>
687In1
STLSetUnion(
const In1& a,
const In2& b, Compare compare) {
690template <
typename In1,
typename In2>
694template <
typename In1>
714template <
typename In1,
typename In2,
typename Out,
typename Compare>
718 "In1 must be an ordered set");
720 "In2 must be an ordered set");
721 assert(std::is_sorted(a.begin(), a.end(), compare));
722 assert(std::is_sorted(b.begin(), b.end(), compare));
723 assert(
static_cast<const void*
>(&a) !=
static_cast<const void*
>(out));
724 assert(
static_cast<const void*
>(&b) !=
static_cast<const void*
>(out));
725 std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(),
726 std::inserter(*out, out->end()), compare);
731template <
typename In1,
typename In2,
typename Out>
732typename std::enable_if<!std::is_function<Out>::value,
void>::type
737template <
typename Out,
typename In1,
typename In2,
typename Compare>
743template <
typename Out,
typename In1,
typename In2>
748template <
typename In1,
typename In2,
typename Compare>
752template <
typename In1,
typename In2>
757template <
typename In1>
777template <
typename In1,
typename In2,
typename Out,
typename Compare>
780 "In1 must be an ordered set");
782 "In2 must be an ordered set");
783 assert(std::is_sorted(a.begin(), a.end(), compare));
784 assert(std::is_sorted(b.begin(), b.end(), compare));
785 assert(
static_cast<const void*
>(&a) !=
static_cast<const void*
>(out));
786 assert(
static_cast<const void*
>(&b) !=
static_cast<const void*
>(out));
787 std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
788 std::inserter(*out, out->end()), compare);
793template <
typename In1,
typename In2,
typename Out>
794typename std::enable_if<!std::is_function<Out>::value,
void>::type
799template <
typename Out,
typename In1,
typename In2,
typename Compare>
805template <
typename Out,
typename In1,
typename In2>
810template <
typename In1,
typename In2,
typename Compare>
814template <
typename In1,
typename In2>
818template <
typename In1>
825template <
typename In1,
typename In2,
typename Compare>
826bool STLIncludes(
const In1& a,
const In2& b, Compare compare) {
828 "In1 must be an ordered set");
830 "In2 must be an ordered set");
831 assert(std::is_sorted(a.begin(), a.end(), compare));
832 assert(std::is_sorted(b.begin(), b.end(), compare));
833 return std::includes(a.begin(), a.end(), b.begin(), b.end(), compare);
835template <
typename In1,
typename In2>
852template <
typename InputIterator1,
typename InputIterator2,
typename Comp>
854 InputIterator2 begin2, InputIterator2 end2,
856 assert(std::is_sorted(begin1, end1, comparator));
857 assert(std::is_sorted(begin2, end2, comparator));
858 while (begin1 != end1 && begin2 != end2) {
859 if (comparator(*begin1, *begin2)) {
863 if (comparator(*begin2, *begin1)) {
871template <
typename InputIterator1,
typename InputIterator2>
873 InputIterator2 begin2, InputIterator2 end2) {
882template <
typename In1,
typename In2,
typename Comp>
886 in2.end(), comparator);
888template <
typename In1,
typename In2>
void operator=(const BaseDeleter &)=delete
BaseDeleter(const BaseDeleter &)=delete
void operator=(const ElementDeleter &)=delete
ElementDeleter(STLContainer *ptr)
ElementDeleter(const ElementDeleter &)=delete
STLElementDeleter(STLContainer *ptr)
STLValueDeleter(STLContainer *ptr)
TemplatedElementDeleter(STLContainer *ptr)
TemplatedElementDeleter(const TemplatedElementDeleter &)=delete
virtual ~TemplatedElementDeleter()
void operator=(const TemplatedElementDeleter &)=delete
void operator=(const TemplatedValueDeleter &)=delete
virtual ~TemplatedValueDeleter()
TemplatedValueDeleter(STLContainer *ptr)
TemplatedValueDeleter(const TemplatedValueDeleter &)=delete
ValueDeleter(STLContainer *ptr)
void operator=(const ValueDeleter &)=delete
ValueDeleter(const ValueDeleter &)=delete
bool operator()(const T &a, const T &b) const
void STLDeleteContainerPairFirstPointers(ForwardIterator begin, ForwardIterator end)
void STLDeleteContainerPairPointers(ForwardIterator begin, ForwardIterator end)
void STLDeleteValues(T *v)
bool SortedContainersHaveIntersection(const In1 &in1, const In2 &in2, Comp comparator)
Out STLSetIntersectionAs(const In1 &a, const In2 &b, Compare compare)
bool STLIncludes(const In1 &a, const In2 &b, Compare compare)
void STLSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
ABSL_MUST_USE_RESULT T * release_ptr(T **ptr)
void STLSetUnion(const In1 &a, const In2 &b, Out *out, Compare compare)
void STLClearIfBig(T *obj, size_t limit=1<< 20)
void STLEraseAllFromSequenceIf(T *v, P pred)
Remove each element e in v satisfying pred(e).
void STLDeleteElements(T *container)
void STLDeleteContainerPairSecondPointers(ForwardIterator begin, ForwardIterator end)
bool STLStringSupportsNontrashingResize(const std::basic_string< T, Traits, Alloc > &s)
void STLStableSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
void STLStringResizeUninitialized(std::basic_string< T, Traits, Alloc > *s, size_t new_size)
void STLSetDifference(const In1 &a, const In2 &b, Out *out, Compare compare)
bool HashSetEquality(const HashSet &set_a, const HashSet &set_b)
Out STLSetUnionAs(const In1 &a, const In2 &b, Compare compare)
Out STLSetSymmetricDifferenceAs(const In1 &a, const In2 &b, Compare comp)
void STLEraseAllFromSequence(T *v, const E &e)
void STLDeleteContainerPointers(ForwardIterator begin, ForwardIterator end)
void STLClearHashIfBig(T *obj, size_t limit)
void STLSetSymmetricDifference(const In1 &a, const In2 &b, Out *out, Compare compare)
void STLClearObject(T *obj)
void STLAssignToString(std::string *str, const char *ptr, size_t n)
void STLAppendToString(std::string *str, const char *ptr, size_t n)
Out STLSetDifferenceAs(const In1 &a, const In2 &b, Compare compare)
Explicit comparator, explicit return type.
char * string_as_array(std::string *str)
void STLSetIntersection(const In1 &a, const In2 &b, Out *out, Compare compare)
bool SortedRangesHaveIntersection(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, Comp comparator)
bool HashMapEquality(const HashMap &map_a, const HashMap &map_b, BinaryPredicate mapped_type_equal)
void STLStringReserveIfNeeded(std::string *s, size_t min_capacity)
Like std::less, but allows heterogeneous arguments.
bool operator()(const T1 &a, const T2 &b) const
bool operator()(const T &a, const T &b) const