14 #ifndef OR_TOOLS_BASE_STL_UTIL_H_
15 #define OR_TOOLS_BASE_STL_UTIL_H_
23 #include <forward_list>
30 #include <type_traits>
33 #include "absl/meta/type_traits.h"
34 #include "absl/strings/internal/resize_uninitialized.h"
40 template <
typename LessFunc>
43 explicit Equiv(
const LessFunc& f) : f_(f) {}
46 return !f_(
b,
a) && !f_(
a,
b);
57 template <
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());
74 template <
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());
92 template <
typename T,
typename E>
94 v->erase(std::remove(v->begin(), v->end(), e), v->end());
96 template <
typename T,
typename A,
typename E>
100 template <
typename T,
typename A,
typename E>
106 template <
typename T,
typename P>
108 v->erase(std::remove_if(v->begin(), v->end(), pred), v->end());
110 template <
typename T,
typename A,
typename P>
114 template <
typename T,
typename A,
typename P>
122 template <
typename T>
131 template <
typename T,
typename A>
133 std::deque<T, A> tmp;
144 template <
typename T>
146 if (obj->capacity() >= limit) {
153 template <
typename T,
typename A>
155 if (obj->size() >= limit) {
179 template <
typename T>
181 if (obj->bucket_count() >= limit) {
195 if (min_capacity > s->capacity()) s->reserve(min_capacity);
202 template <
typename T,
typename Traits,
typename Alloc>
213 template <
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();
269 template <
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;
281 template <
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;
296 template <
typename K,
typename V,
typename C,
typename A>
298 const std::map<K, V, C, A>& map_b) {
299 return map_a == map_b;
302 template <
typename HashMap>
304 using Mapped =
typename HashMap::mapped_type;
313 template <
typename ForwardIterator>
315 while (begin != end) {
324 template <
typename ForwardIterator>
326 ForwardIterator end) {
327 while (begin != end) {
337 template <
typename ForwardIterator>
339 ForwardIterator end) {
340 while (begin != end) {
352 template <
typename ForwardIterator>
354 ForwardIterator end) {
355 while (begin != end) {
371 template <
typename T>
373 if (!container)
return;
381 template <
typename T>
407 template <
typename STLContainer>
418 STLContainer* container_ptr_;
436 template <
typename STLContainer>
453 template <
typename STLContainer>
464 STLContainer* container_ptr_;
478 template <
typename STLContainer>
496 template <
typename STLContainer>
503 STLContainer* container_ptr_;
511 template <
typename STLContainer>
518 STLContainer* container_ptr_;
532 template <
typename T>
540 namespace stl_util_internal {
544 template <
typename T>
547 return std::less<T>()(
a,
b);
549 template <
typename T1,
typename T2>
559 template <
typename,
typename =
void,
typename =
void>
562 template <
typename T>
565 template <
typename T>
567 absl::void_t<typename T::reverse_iterator>> : std::false_type {
594 template <
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);
611 template <
typename In1,
typename In2,
typename Out>
617 template <
typename Out,
typename In1,
typename In2,
typename Compare>
624 template <
typename Out,
typename In1,
typename In2>
626 return STLSetDifferenceAs<Out>(
a,
b,
630 template <
typename In1,
typename In2,
typename Compare>
632 return STLSetDifferenceAs<In1>(
a,
b, compare);
635 template <
typename In1,
typename In2>
639 template <
typename In1>
658 template <
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);
674 template <
typename In1,
typename In2,
typename Out>
676 const In1&
a,
const In2&
b, Out* out) {
679 template <
typename Out,
typename In1,
typename In2,
typename Compare>
685 template <
typename Out,
typename In1,
typename In2>
689 template <
typename In1,
typename In2,
typename Compare>
691 return STLSetUnionAs<In1>(
a,
b, compare);
693 template <
typename In1,
typename In2>
697 template <
typename In1>
717 template <
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);
734 template <
typename In1,
typename In2,
typename Out>
740 template <
typename Out,
typename In1,
typename In2,
typename Compare>
746 template <
typename Out,
typename In1,
typename In2>
748 return STLSetSymmetricDifferenceAs<Out>(
751 template <
typename In1,
typename In2,
typename Compare>
753 return STLSetSymmetricDifferenceAs<In1>(
a,
b, comp);
755 template <
typename In1,
typename In2>
760 template <
typename In1>
780 template <
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);
796 template <
typename In1,
typename In2,
typename Out>
802 template <
typename Out,
typename In1,
typename In2,
typename Compare>
808 template <
typename Out,
typename In1,
typename In2>
810 return STLSetIntersectionAs<Out>(
a,
b,
813 template <
typename In1,
typename In2,
typename Compare>
815 return STLSetIntersectionAs<In1>(
a,
b, compare);
817 template <
typename In1,
typename In2>
821 template <
typename In1>
828 template <
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);
838 template <
typename In1,
typename In2>
855 template <
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)) {
874 template <
typename InputIterator1,
typename InputIterator2>
876 InputIterator2 begin2, InputIterator2 end2) {
885 template <
typename In1,
typename In2,
typename Comp>
889 in2.end(), comparator);
891 template <
typename In1,
typename In2>
909 template <
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>
952 template <
typename A>
959 template <
typename U,
typename B>
963 template <
typename U>
976 template <
typename T,
typename A>
980 return static_cast<const Base&
>(
a) ==
static_cast<const Base&
>(
b) &&
981 a.bytes_used() ==
b.bytes_used();
984 template <
typename T,
typename A>
991 #endif // OR_TOOLS_BASE_STL_UTIL_H_