Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
stl_util.h
Go to the documentation of this file.
1// Copyright 2010-2025 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14#ifndef OR_TOOLS_BASE_STL_UTIL_H_
15#define OR_TOOLS_BASE_STL_UTIL_H_
16
17#include <stddef.h>
18#include <string.h>
19
20#include <algorithm>
21#include <cassert>
22#include <deque>
23#include <forward_list>
24#include <functional>
25#include <iterator>
26#include <list>
27#include <map>
28#include <string>
29#include <type_traits>
30
31#include "absl/base/attributes.h"
32#include "absl/meta/type_traits.h"
33#include "absl/strings/internal/resize_uninitialized.h"
34
35namespace gtl {
36namespace internal {
37template <typename LessFunc>
38class Equiv {
39 public:
40 explicit Equiv(const LessFunc& f) : f_(f) {}
41 template <typename T>
42 bool operator()(const T& a, const T& b) const {
43 return !f_(b, a) && !f_(a, b);
44 }
45
46 private:
47 LessFunc f_;
48};
49} // namespace internal
50
51// Sorts and removes duplicates from a sequence container.
52// If specified, the 'less_func' is used to compose an
53// equivalence comparator for the sorting and uniqueness tests.
54template <typename T, typename LessFunc>
55inline void STLSortAndRemoveDuplicates(T* v, const LessFunc& less_func) {
56 std::sort(v->begin(), v->end(), less_func);
57 v->erase(std::unique(v->begin(), v->end(),
59 v->end());
60}
61template <typename T>
62inline void STLSortAndRemoveDuplicates(T* v) {
63 std::sort(v->begin(), v->end());
64 v->erase(std::unique(v->begin(), v->end()), v->end());
65}
66
67// Stable sorts and removes duplicates from a sequence container, retaining
68// the first equivalent element for each equivalence set.
69// The 'less_func' is used to compose an equivalence comparator for the sorting
70// and uniqueness tests.
71template <typename T, typename LessFunc>
72inline void STLStableSortAndRemoveDuplicates(T* v, const LessFunc& less_func) {
73 std::stable_sort(v->begin(), v->end(), less_func);
74 v->erase(std::unique(v->begin(), v->end(),
76 v->end());
77}
78// Stable sorts and removes duplicates from a sequence container, retaining
79// the first equivalent element for each equivalence set, using < comparison and
80// == equivalence testing.
81template <typename T>
83 std::stable_sort(v->begin(), v->end());
84 v->erase(std::unique(v->begin(), v->end()), v->end());
85}
86
87// Remove every occurrence of element e in v. See
88// http://en.wikipedia.org/wiki/Erase-remove_idiom.
89template <typename T, typename E>
90void STLEraseAllFromSequence(T* v, const E& e) {
91 v->erase(std::remove(v->begin(), v->end(), e), v->end());
92}
93template <typename T, typename A, typename E>
94void STLEraseAllFromSequence(std::list<T, A>* c, const E& e) {
95 c->remove(e);
96}
97template <typename T, typename A, typename E>
98void STLEraseAllFromSequence(std::forward_list<T, A>* c, const E& e) {
99 c->remove(e);
100}
101
102// Remove each element e in v satisfying pred(e).
103template <typename T, typename P>
104void STLEraseAllFromSequenceIf(T* v, P pred) {
105 v->erase(std::remove_if(v->begin(), v->end(), pred), v->end());
106}
107template <typename T, typename A, typename P>
108void STLEraseAllFromSequenceIf(std::list<T, A>* c, P pred) {
109 c->remove_if(pred);
110}
111template <typename T, typename A, typename P>
112void STLEraseAllFromSequenceIf(std::forward_list<T, A>* c, P pred) {
113 c->remove_if(pred);
114}
115
116// Clears internal memory of an STL object by swapping the argument with a new,
117// empty object. STL clear()/reserve(0) does not always free internal memory
118// allocated.
119template <typename T>
120void STLClearObject(T* obj) {
121 T tmp;
122 tmp.swap(*obj);
123 // This reserve(0) is needed because "T tmp" sometimes allocates memory (arena
124 // implementation?), even though this may not always work.
125 obj->reserve(0);
126}
127// STLClearObject overload for deque, which is missing reserve().
128template <typename T, typename A>
129void STLClearObject(std::deque<T, A>* obj) {
130 std::deque<T, A> tmp;
131 tmp.swap(*obj);
132}
133
134// Calls STLClearObject() if the object is bigger than the specified limit,
135// otherwise calls the object's clear() member. This can be useful if you want
136// to allow the object to hold on to its allocated memory as long as it's not
137// too much.
138//
139// Note: The name is misleading since the object is always cleared, regardless
140// of its size.
141template <typename T>
142inline void STLClearIfBig(T* obj, size_t limit = 1 << 20) {
143 if (obj->capacity() >= limit) {
144 STLClearObject(obj);
145 } else {
146 obj->clear();
147 }
148}
149// STLClearIfBig overload for deque, which is missing capacity().
150template <typename T, typename A>
151inline void STLClearIfBig(std::deque<T, A>* obj, size_t limit = 1 << 20) {
152 if (obj->size() >= limit) {
153 STLClearObject(obj);
154 } else {
155 obj->clear();
156 }
157}
158
159// Removes all elements and reduces the number of buckets in a hash_set or
160// hash_map back to the default if the current number of buckets is "limit" or
161// more.
162//
163// Adding items to a hash container may add buckets, but removing items or
164// calling clear() does not necessarily reduce the number of buckets. Having
165// lots of buckets is good if you insert comparably many items in every
166// iteration because you'll reduce collisions and table resizes. But having lots
167// of buckets is bad if you insert few items in most subsequent iterations,
168// because repeatedly clearing out all those buckets can get expensive.
169//
170// One solution is to call STLClearHashIfBig() with a "limit" value that is a
171// small multiple of the typical number of items in your table. In the common
172// case, this is equivalent to an ordinary clear. In the rare case where you
173// insert a lot of items, the number of buckets is reset to the default to keep
174// subsequent clear operations cheap. Note that the default number of buckets is
175// 193 in the Gnu library implementation as of Jan '08.
176template <typename T>
177inline void STLClearHashIfBig(T* obj, size_t limit) {
178 if (obj->bucket_count() >= limit) {
179 T tmp;
180 tmp.swap(*obj);
181 } else {
182 obj->clear();
183 }
184}
185
186// Reserves space in the given string only if the existing capacity is not
187// already enough. This is useful for strings because string::reserve() may
188// *shrink* the capacity in some cases, which is usually not what users want.
189// The behavior of this function is similar to that of vector::reserve() but for
190// string.
191inline void STLStringReserveIfNeeded(std::string* s, size_t min_capacity) {
192 if (min_capacity > s->capacity()) s->reserve(min_capacity);
193}
194
195// Like str->resize(new_size), except any new characters added to "*str" as a
196// result of resizing may be left uninitialized, rather than being filled with
197// '0' bytes. Typically used when code is then going to overwrite the backing
198// store of the string with known data.
199template <typename T, typename Traits, typename Alloc>
200inline void STLStringResizeUninitialized(std::basic_string<T, Traits, Alloc>* s,
201 size_t new_size) {
202 absl::strings_internal::STLStringResizeUninitialized(s, new_size);
203}
204
205// Returns true if the string implementation supports a resize where
206// the new characters added to the string are left untouched.
207//
208// (A better name might be "STLStringSupportsUninitializedResize", alluding to
209// the previous function.)
210template <typename T, typename Traits, typename Alloc>
212 const std::basic_string<T, Traits, Alloc>& s) {
213 return absl::strings_internal::STLStringSupportsNontrashingResize(&s);
214}
215
216// Assigns the n bytes starting at ptr to the given string. This is intended to
217// be faster than string::assign() in SOME cases, however, it's actually slower
218// in some cases as well.
219//
220// Just use string::assign directly unless you have benchmarks showing that this
221// function makes your code faster. (Even then, a future version of
222// string::assign() may be faster than this.)
223inline void STLAssignToString(std::string* str, const char* ptr, size_t n) {
225 if (n == 0) return;
226 memcpy(&*str->begin(), ptr, n);
227}
228
229// Appends the n bytes starting at ptr to the given string. This is intended to
230// be faster than string::append() in SOME cases, however, it's actually slower
231// in some cases as well.
232//
233// Just use string::append directly unless you have benchmarks showing that this
234// function makes your code faster. (Even then, a future version of
235// string::append() may be faster than this.)
236inline void STLAppendToString(std::string* str, const char* ptr, size_t n) {
237 if (n == 0) return;
238 size_t old_size = str->size();
239 STLStringResizeUninitialized(str, old_size + n);
240 memcpy(&*str->begin() + old_size, ptr, n);
241}
242
243// Returns a mutable char* pointing to a string's internal buffer, which may not
244// be null-terminated. Returns nullptr for an empty string. If not non-null,
245// writing through this pointer will modify the string.
246//
247// string_as_array(&str)[i] is valid for 0 <= i < str.size() until the
248// next call to a string method that invalidates iterators.
249//
250// In C++11 you may simply use &str[0] to get a mutable char*.
251//
252// Prior to C++11, there was no standard-blessed way of getting a mutable
253// reference to a string's internal buffer. The requirement that string be
254// contiguous is officially part of the C++11 standard [string.require]/5.
255// According to Matt Austern, this should already work on all current C++98
256// implementations.
257inline char* string_as_array(std::string* str) {
258 // DO NOT USE const_cast<char*>(str->data())! See the unittest for why.
259 return str->empty() ? nullptr : &*str->begin();
260}
261
262// Tests two hash maps/sets for equality. This exists because operator== in the
263// STL can return false when the maps/sets contain identical elements. This is
264// because it compares the internal hash tables which may be different if the
265// order of insertions and deletions differed.
266template <typename HashSet>
267inline bool HashSetEquality(const HashSet& set_a, const HashSet& set_b) {
268 if (set_a.size() != set_b.size()) return false;
269 for (typename HashSet::const_iterator i = set_a.begin(); i != set_a.end();
270 ++i)
271 if (set_b.find(*i) == set_b.end()) return false;
272 return true;
273}
274
275// WARNING: Using HashMapEquality for multiple-associative containers like
276// multimap and hash_multimap will result in wrong behavior.
277
278template <typename HashMap, typename BinaryPredicate>
279inline bool HashMapEquality(const HashMap& map_a, const HashMap& map_b,
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();
283 ++i) {
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;
287 }
288 return true;
289}
290
291// We overload for 'map' without a specialized functor and simply use its
292// operator== function.
293template <typename K, typename V, typename C, typename A>
294inline bool HashMapEquality(const std::map<K, V, C, A>& map_a,
295 const std::map<K, V, C, A>& map_b) {
296 return map_a == map_b;
297}
298
299template <typename HashMap>
300inline bool HashMapEquality(const HashMap& a, const HashMap& b) {
301 using Mapped = typename HashMap::mapped_type;
302 return HashMapEquality(a, b, std::equal_to<Mapped>());
303}
304
305// Calls delete (non-array version) on pointers in the range [begin, end).
306//
307// Note: If you're calling this on an entire container, you probably want to
308// call STLDeleteElements(&container) instead (which also clears the container),
309// or use an ElementDeleter.
310template <typename ForwardIterator>
311void STLDeleteContainerPointers(ForwardIterator begin, ForwardIterator end) {
312 while (begin != end) {
313 auto temp = begin;
314 ++begin;
315 delete *temp;
316 }
317}
318
319// Calls delete (non-array version) on BOTH items (pointers) in each pair in the
320// range [begin, end).
321template <typename ForwardIterator>
322void STLDeleteContainerPairPointers(ForwardIterator begin,
323 ForwardIterator end) {
324 while (begin != end) {
325 auto temp = begin;
326 ++begin;
327 delete temp->first;
328 delete temp->second;
329 }
330}
331
332// Calls delete (non-array version) on the FIRST item (pointer) in each pair in
333// the range [begin, end).
334template <typename ForwardIterator>
335void STLDeleteContainerPairFirstPointers(ForwardIterator begin,
336 ForwardIterator end) {
337 while (begin != end) {
338 auto temp = begin;
339 ++begin;
340 delete temp->first;
341 }
342}
343
344// Calls delete (non-array version) on the SECOND item (pointer) in each pair in
345// the range [begin, end).
346//
347// Note: If you're calling this on an entire container, you probably want to
348// call STLDeleteValues(&container) instead, or use ValueDeleter.
349template <typename ForwardIterator>
350void STLDeleteContainerPairSecondPointers(ForwardIterator begin,
351 ForwardIterator end) {
352 while (begin != end) {
353 auto temp = begin;
354 ++begin;
355 delete temp->second;
356 }
357}
358
359// Deletes all the elements in an STL container and clears the container. This
360// function is suitable for use with a vector, set, hash_set, or any other STL
361// container which defines sensible begin(), end(), and clear() methods.
362//
363// If container is nullptr, this function is a no-op.
364//
365// As an alternative to calling STLDeleteElements() directly, consider
366// ElementDeleter (defined below), which ensures that your container's elements
367// are deleted when the ElementDeleter goes out of scope.
368template <typename T>
369void STLDeleteElements(T* container) {
370 if (!container) return;
371 STLDeleteContainerPointers(container->begin(), container->end());
372 container->clear();
373}
374
375// Given an STL container consisting of (key, value) pairs, STLDeleteValues
376// deletes all the "value" components and clears the container. Does nothing in
377// the case it's given a nullptr.
378template <typename T>
379void STLDeleteValues(T* v) {
380 if (!v) return;
381 (STLDeleteContainerPairSecondPointers)(v->begin(), v->end());
382 v->clear();
383}
384
385// A very simple interface that simply provides a virtual destructor. It is used
386// as a non-templated base class for the TemplatedElementDeleter and
387// TemplatedValueDeleter classes.
388//
389// Clients should NOT use this class directly.
391 public:
392 virtual ~BaseDeleter() {}
393 BaseDeleter(const BaseDeleter&) = delete;
394 void operator=(const BaseDeleter&) = delete;
395
396 protected:
398};
399
400// Given a pointer to an STL container, this class will delete all the element
401// pointers when it goes out of scope.
402//
403// Clients should NOT use this class directly. Use ElementDeleter instead.
404template <typename STLContainer>
406 public:
407 explicit TemplatedElementDeleter(STLContainer* ptr) : container_ptr_(ptr) {}
408
409 virtual ~TemplatedElementDeleter() { STLDeleteElements(container_ptr_); }
410
412 void operator=(const TemplatedElementDeleter&) = delete;
413
414 private:
415 STLContainer* container_ptr_;
416};
417
418// ElementDeleter is an RAII object that deletes the elements in the
419// given container when it goes out of scope. This is similar to
420// std::unique_ptr<> except that a container's elements will be deleted rather
421// than the container itself.
422//
423// Example:
424// std::vector<MyProto*> tmp_proto;
425// ElementDeleter d(&tmp_proto);
426// if (...) return false;
427// ...
428// return success;
429//
430// Since C++11, consider using containers of std::unique_ptr instead.
432 public:
433 template <typename STLContainer>
434 explicit ElementDeleter(STLContainer* ptr)
435 : deleter_(new TemplatedElementDeleter<STLContainer>(ptr)) {}
436
437 ~ElementDeleter() { delete deleter_; }
438
440 void operator=(const ElementDeleter&) = delete;
441
442 private:
443 BaseDeleter* deleter_;
444};
445
446// Given a pointer to an STL container this class will delete all the value
447// pointers when it goes out of scope.
448//
449// Clients should NOT use this class directly. Use ValueDeleter instead.
450template <typename STLContainer>
452 public:
453 explicit TemplatedValueDeleter(STLContainer* ptr) : container_ptr_(ptr) {}
454
455 virtual ~TemplatedValueDeleter() { STLDeleteValues(container_ptr_); }
456
458 void operator=(const TemplatedValueDeleter&) = delete;
459
460 private:
461 STLContainer* container_ptr_;
462};
463
464// ValueDeleter is an RAII object that deletes the 'second' member in
465// the given container of std::pair<>s when it goes out of scope.
466//
467// Example:
468// std::map<std::string, Foo*> foo_map;
469// ValueDeleter d(&foo_map);
470// if (...) return false;
471// ...
472// return success;
474 public:
475 template <typename STLContainer>
476 explicit ValueDeleter(STLContainer* ptr)
477 : deleter_(new TemplatedValueDeleter<STLContainer>(ptr)) {}
478
479 ~ValueDeleter() { delete deleter_; }
480
481 ValueDeleter(const ValueDeleter&) = delete;
482 void operator=(const ValueDeleter&) = delete;
483
484 private:
485 BaseDeleter* deleter_;
486};
487
488// RAII object that deletes elements in the given container when it
489// goes out of scope. Like ElementDeleter (above) except that this class is
490// templated and doesn't have a virtual destructor.
491//
492// New code should prefer ElementDeleter.
493template <typename STLContainer>
495 public:
496 STLElementDeleter(STLContainer* ptr) : container_ptr_(ptr) {}
498
499 private:
500 STLContainer* container_ptr_;
501};
502
503// RAII object that deletes the values in the given container of
504// std::pair<>s when it goes out of scope. Like ValueDeleter (above) except that
505// this class is templated and doesn't have a virtual destructor.
506//
507// New code should prefer ValueDeleter.
508template <typename STLContainer>
510 public:
511 STLValueDeleter(STLContainer* ptr) : container_ptr_(ptr) {}
512 ~STLValueDeleter() { STLDeleteValues(container_ptr_); }
513
514 private:
515 STLContainer* container_ptr_;
516};
517
518// Sets the referenced pointer to nullptr and returns its original value. This
519// can be a convenient way to remove a pointer from a container to avoid the
520// eventual deletion by an ElementDeleter.
521//
522// Example:
523//
524// std::vector<Foo*> v{new Foo, new Foo, new Foo};
525// ElementDeleter d(&v);
526// Foo* safe = release_ptr(&v[1]);
527// // v[1] is now nullptr and the Foo it previously pointed to is now
528// // stored in "safe"
529template <typename T>
530ABSL_MUST_USE_RESULT T* release_ptr(T** ptr) {
531 assert(ptr);
532 T* tmp = *ptr;
533 *ptr = nullptr;
534 return tmp;
535}
536
538
539// Like std::less, but allows heterogeneous arguments.
541 template <typename T>
542 bool operator()(const T& a, const T& b) const {
543 // std::less is better than '<' here, because it can order pointers.
544 return std::less<T>()(a, b);
545 }
546 template <typename T1, typename T2>
547 bool operator()(const T1& a, const T2& b) const {
548 return a < b;
549 }
550};
551
552// Trait to detect whether a type T is an hash table.
553// The heuristic used is that the type contains an inner type `hasher` and does
554// not contain an inner type `reverse_iterator`.
555// If the container is iterable in reverse, then order might actually matter.
556template <typename, typename = void, typename = void>
557struct Unordered : std::false_type {};
558
559template <typename T>
560struct Unordered<T, absl::void_t<typename T::hasher>> : std::true_type {};
561
562template <typename T>
563struct Unordered<T, absl::void_t<typename T::hasher>,
564 absl::void_t<typename T::reverse_iterator>> : std::false_type {
565};
566
567} // namespace stl_util_internal
568
569// STLSetDifference:
570//
571// In1 STLSetDifference(a, b);
572// In1 STLSetDifference(a, b, compare);
573// void STLSetDifference(a, b, &out);
574// void STLSetDifference(a, b, &out, compare);
575// Out STLSetDifferenceAs<Out>(a, b);
576// Out STLSetDifferenceAs<Out>(a, b, compare);
577//
578// Appends the elements in "a" that are not in "b" to an output container.
579// Optionally specify a comparator, or '<' is used by default. Both input
580// containers must be sorted with respect to the comparator. If specified,
581// the output container must be distinct from both "a" and "b".
582//
583// If an output container pointer is not given, a container will be returned
584// by value. The return type can be explicitly specified by calling
585// STLSetDifferenceAs, but it defaults to the type of argument "a".
586//
587// See std::set_difference() for details on how set difference is computed.
588//
589// The form taking 4 arguments. All other forms call into this one.
590// Explicit comparator, append to output container.
591template <typename In1, typename In2, typename Out, typename Compare>
592void STLSetDifference(const In1& a, const In2& b, Out* out, Compare 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);
603}
604// Append to output container, Implicit comparator.
605// Note: The 'enable_if' keeps this overload from participating in
606// overload resolution if 'out' is a function pointer, gracefully forcing
607// the 3-argument overload that treats the third argument as a comparator.
608template <typename In1, typename In2, typename Out>
609typename std::enable_if<!std::is_function<Out>::value, void>::type
610STLSetDifference(const In1& a, const In2& b, Out* out) {
612}
613// Explicit comparator, explicit return type.
614template <typename Out, typename In1, typename In2, typename Compare>
615Out STLSetDifferenceAs(const In1& a, const In2& b, Compare compare) {
616 Out out;
617 STLSetDifference(a, b, &out, compare);
618 return out;
619}
620// Implicit comparator, explicit return type.
621template <typename Out, typename In1, typename In2>
622Out STLSetDifferenceAs(const In1& a, const In2& b) {
623 return STLSetDifferenceAs<Out>(a, b,
625}
626// Explicit comparator, implicit return type.
627template <typename In1, typename In2, typename Compare>
628In1 STLSetDifference(const In1& a, const In2& b, Compare compare) {
629 return STLSetDifferenceAs<In1>(a, b, compare);
630}
631// Implicit comparator, implicit return type.
632template <typename In1, typename In2>
633In1 STLSetDifference(const In1& a, const In2& b) {
635}
636template <typename In1>
637In1 STLSetDifference(const In1& a, const In1& b) {
639}
640
641// STLSetUnion:
642//
643// In1 STLSetUnion(a, b);
644// In1 STLSetUnion(a, b, compare);
645// void STLSetUnion(a, b, &out);
646// void STLSetUnion(a, b, &out, compare);
647// Out STLSetUnionAs<Out>(a, b);
648// Out STLSetUnionAs<Out>(a, b, compare);
649// Appends the elements in one or both of the input containers to output
650// container "out". Both input containers must be sorted with operator '<',
651// or with the comparator if specified. "out" must be distinct from both "a"
652// and "b".
653//
654// See std::set_union() for how set union is computed.
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);
667}
668// Note: The 'enable_if' keeps this overload from participating in
669// overload resolution if 'out' is a function pointer, gracefully forcing
670// the 3-argument overload that treats the third argument as a comparator.
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) {
675}
676template <typename Out, typename In1, typename In2, typename Compare>
677Out STLSetUnionAs(const In1& a, const In2& b, Compare compare) {
678 Out out;
679 STLSetUnion(a, b, &out, compare);
680 return out;
681}
682template <typename Out, typename In1, typename In2>
683Out STLSetUnionAs(const In1& a, const In2& b) {
685}
686template <typename In1, typename In2, typename Compare>
687In1 STLSetUnion(const In1& a, const In2& b, Compare compare) {
688 return STLSetUnionAs<In1>(a, b, compare);
689}
690template <typename In1, typename In2>
691In1 STLSetUnion(const In1& a, const In2& b) {
693}
694template <typename In1>
695In1 STLSetUnion(const In1& a, const In1& b) {
699// STLSetSymmetricDifference:
700//
701// In1 STLSetSymmetricDifference(a, b);
702// In1 STLSetSymmetricDifference(a, b, compare);
703// void STLSetSymmetricDifference(a, b, &out);
704// void STLSetSymmetricDifference(a, b, &out, compare);
705// Out STLSetSymmetricDifferenceAs<Out>(a, b);
706// Out STLSetSymmetricDifferenceAs<Out>(a, b, compare);
707//
708// Appends the elements in "a" that are not in "b", and the elements in "b"
709// that are not in "a", to output container "out". Both input containers
710// must be sorted with operator '<', or with the comparator if specified.
711// "out" must be distinct from both "a" and "b".
712//
713// See std::set_symmetric_difference() for how these elements are selected.
714template <typename In1, typename In2, typename Out, typename Compare>
715void STLSetSymmetricDifference(const In1& a, const In2& b, Out* out,
716 Compare 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);
727}
728// Note: The 'enable_if' keeps this overload from participating in
729// overload resolution if 'out' is a function pointer, gracefully forcing
730// the 3-argument overload that treats the third argument as a comparator.
731template <typename In1, typename In2, typename Out>
732typename std::enable_if<!std::is_function<Out>::value, void>::type
733STLSetSymmetricDifference(const In1& a, const In2& b, Out* out) {
736}
737template <typename Out, typename In1, typename In2, typename Compare>
738Out STLSetSymmetricDifferenceAs(const In1& a, const In2& b, Compare comp) {
739 Out out;
740 STLSetSymmetricDifference(a, b, &out, comp);
741 return out;
742}
743template <typename Out, typename In1, typename In2>
744Out STLSetSymmetricDifferenceAs(const In1& a, const In2& b) {
747}
748template <typename In1, typename In2, typename Compare>
749In1 STLSetSymmetricDifference(const In1& a, const In2& b, Compare comp) {
751}
752template <typename In1, typename In2>
753In1 STLSetSymmetricDifference(const In1& a, const In2& b) {
756}
757template <typename In1>
758In1 STLSetSymmetricDifference(const In1& a, const In1& b) {
763// STLSetIntersection:
764//
765// In1 STLSetIntersection(a, b);
766// In1 STLSetIntersection(a, b, compare);
767// void STLSetIntersection(a, b, &out);
768// void STLSetIntersection(a, b, &out, compare);
769// Out STLSetIntersectionAs<Out>(a, b);
770// Out STLSetIntersectionAs<Out>(a, b, compare);
771//
772// Appends the elements that are in both "a" and "b" to output container
773// "out". Both input containers must be sorted with operator '<' or with
774// "compare" if specified. "out" must be distinct from both "a" and "b".
775//
776// See std::set_intersection() for how set intersection is computed.
777template <typename In1, typename In2, typename Out, typename Compare>
778void STLSetIntersection(const In1& a, const In2& b, Out* out, Compare 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);
789}
790// Note: The 'enable_if' keeps this overload from participating in
791// overload resolution if 'out' is a function pointer, gracefully forcing
792// the 3-argument overload that treats the third argument as a comparator.
793template <typename In1, typename In2, typename Out>
794typename std::enable_if<!std::is_function<Out>::value, void>::type
795STLSetIntersection(const In1& a, const In2& b, Out* out) {
796 return STLSetIntersection(a, b, out,
798}
799template <typename Out, typename In1, typename In2, typename Compare>
800Out STLSetIntersectionAs(const In1& a, const In2& b, Compare compare) {
801 Out out;
802 STLSetIntersection(a, b, &out, compare);
803 return out;
804}
805template <typename Out, typename In1, typename In2>
806Out STLSetIntersectionAs(const In1& a, const In2& b) {
809}
810template <typename In1, typename In2, typename Compare>
811In1 STLSetIntersection(const In1& a, const In2& b, Compare compare) {
812 return STLSetIntersectionAs<In1>(a, b, compare);
813}
814template <typename In1, typename In2>
815In1 STLSetIntersection(const In1& a, const In2& b) {
817}
818template <typename In1>
819In1 STLSetIntersection(const In1& a, const In1& b) {
823// Returns true iff every element in "b" is also in "a". Both containers
824// must be sorted by the specified comparator, or by '<' if none is given.
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);
834}
835template <typename In1, typename In2>
836bool STLIncludes(const In1& a, const In2& b) {
840// SortedRangesHaveIntersection:
841//
842// bool SortedRangesHaveIntersection(begin1, end1, begin2, end2);
843// bool SortedRangesHaveIntersection(begin1, end1, begin2, end2,
844// comparator);
845//
846// Returns true iff any element in the sorted range [begin1, end1) is
847// equivalent to any element in the sorted range [begin2, end2). The iterators
848// themselves do not have to be the same type, but the value types must be
849// sorted either by the specified comparator, or by '<' if no comparator is
850// given.
851// [Two elements a,b are considered equivalent if !(a < b) && !(b < a) ].
852template <typename InputIterator1, typename InputIterator2, typename Comp>
853bool SortedRangesHaveIntersection(InputIterator1 begin1, InputIterator1 end1,
854 InputIterator2 begin2, InputIterator2 end2,
855 Comp comparator) {
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)) {
860 ++begin1;
861 continue;
862 }
863 if (comparator(*begin2, *begin1)) {
864 ++begin2;
865 continue;
866 }
867 return true;
868 }
869 return false;
870}
871template <typename InputIterator1, typename InputIterator2>
872bool SortedRangesHaveIntersection(InputIterator1 begin1, InputIterator1 end1,
873 InputIterator2 begin2, InputIterator2 end2) {
875 begin1, end1, begin2, end2, gtl::stl_util_internal::TransparentLess());
876}
877
878// Returns true iff the ordered containers 'in1' and 'in2' have a non-empty
879// intersection. The container elements do not have to be the same type, but the
880// elements must be sorted either by the specified comparator, or by '<' if no
881// comparator is given.
882template <typename In1, typename In2, typename Comp>
883bool SortedContainersHaveIntersection(const In1& in1, const In2& in2,
884 Comp comparator) {
885 return SortedRangesHaveIntersection(in1.begin(), in1.end(), in2.begin(),
886 in2.end(), comparator);
887}
888template <typename In1, typename In2>
889bool SortedContainersHaveIntersection(const In1& in1, const In2& in2) {
894} // namespace gtl
895#endif // OR_TOOLS_BASE_STL_UTIL_H_
virtual ~BaseDeleter()
Definition stl_util.h:392
void operator=(const BaseDeleter &)=delete
BaseDeleter(const BaseDeleter &)=delete
void operator=(const ElementDeleter &)=delete
ElementDeleter(STLContainer *ptr)
Definition stl_util.h:434
ElementDeleter(const ElementDeleter &)=delete
STLElementDeleter(STLContainer *ptr)
Definition stl_util.h:496
STLValueDeleter(STLContainer *ptr)
Definition stl_util.h:511
TemplatedElementDeleter(STLContainer *ptr)
Definition stl_util.h:407
TemplatedElementDeleter(const TemplatedElementDeleter &)=delete
void operator=(const TemplatedElementDeleter &)=delete
void operator=(const TemplatedValueDeleter &)=delete
virtual ~TemplatedValueDeleter()
Definition stl_util.h:455
TemplatedValueDeleter(STLContainer *ptr)
Definition stl_util.h:453
TemplatedValueDeleter(const TemplatedValueDeleter &)=delete
ValueDeleter(STLContainer *ptr)
Definition stl_util.h:476
void operator=(const ValueDeleter &)=delete
ValueDeleter(const ValueDeleter &)=delete
bool operator()(const T &a, const T &b) const
Definition stl_util.h:42
Equiv(const LessFunc &f)
Definition stl_util.h:40
!
Definition array.h:26
void STLDeleteContainerPairFirstPointers(ForwardIterator begin, ForwardIterator end)
Definition stl_util.h:335
void STLDeleteContainerPairPointers(ForwardIterator begin, ForwardIterator end)
Definition stl_util.h:322
void STLDeleteValues(T *v)
Definition stl_util.h:379
bool SortedContainersHaveIntersection(const In1 &in1, const In2 &in2, Comp comparator)
Definition stl_util.h:884
Out STLSetIntersectionAs(const In1 &a, const In2 &b, Compare compare)
Definition stl_util.h:801
bool STLIncludes(const In1 &a, const In2 &b, Compare compare)
Definition stl_util.h:827
void STLSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
Definition stl_util.h:55
ABSL_MUST_USE_RESULT T * release_ptr(T **ptr)
Definition stl_util.h:530
void STLSetUnion(const In1 &a, const In2 &b, Out *out, Compare compare)
Definition stl_util.h:657
void STLClearIfBig(T *obj, size_t limit=1<< 20)
Definition stl_util.h:142
void STLEraseAllFromSequenceIf(T *v, P pred)
Remove each element e in v satisfying pred(e).
Definition stl_util.h:104
void STLDeleteElements(T *container)
Definition stl_util.h:369
void STLDeleteContainerPairSecondPointers(ForwardIterator begin, ForwardIterator end)
Definition stl_util.h:350
bool STLStringSupportsNontrashingResize(const std::basic_string< T, Traits, Alloc > &s)
Definition stl_util.h:211
void STLStableSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
Definition stl_util.h:72
void STLStringResizeUninitialized(std::basic_string< T, Traits, Alloc > *s, size_t new_size)
Definition stl_util.h:200
void STLSetDifference(const In1 &a, const In2 &b, Out *out, Compare compare)
Definition stl_util.h:592
bool HashSetEquality(const HashSet &set_a, const HashSet &set_b)
Definition stl_util.h:267
Out STLSetUnionAs(const In1 &a, const In2 &b, Compare compare)
Definition stl_util.h:678
Out STLSetSymmetricDifferenceAs(const In1 &a, const In2 &b, Compare comp)
Definition stl_util.h:739
void STLEraseAllFromSequence(T *v, const E &e)
Definition stl_util.h:90
void STLDeleteContainerPointers(ForwardIterator begin, ForwardIterator end)
Definition stl_util.h:311
void STLClearHashIfBig(T *obj, size_t limit)
Definition stl_util.h:177
void STLSetSymmetricDifference(const In1 &a, const In2 &b, Out *out, Compare compare)
Definition stl_util.h:716
void STLClearObject(T *obj)
Definition stl_util.h:120
void STLAssignToString(std::string *str, const char *ptr, size_t n)
Definition stl_util.h:223
void STLAppendToString(std::string *str, const char *ptr, size_t n)
Definition stl_util.h:236
Out STLSetDifferenceAs(const In1 &a, const In2 &b, Compare compare)
Explicit comparator, explicit return type.
Definition stl_util.h:615
char * string_as_array(std::string *str)
Definition stl_util.h:257
void STLSetIntersection(const In1 &a, const In2 &b, Out *out, Compare compare)
Definition stl_util.h:779
bool SortedRangesHaveIntersection(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, Comp comparator)
Definition stl_util.h:854
bool HashMapEquality(const HashMap &map_a, const HashMap &map_b, BinaryPredicate mapped_type_equal)
Definition stl_util.h:279
void STLStringReserveIfNeeded(std::string *s, size_t min_capacity)
Definition stl_util.h:191
Like std::less, but allows heterogeneous arguments.
Definition stl_util.h:540
bool operator()(const T1 &a, const T2 &b) const
Definition stl_util.h:547
bool operator()(const T &a, const T &b) const
Definition stl_util.h:542