OR-Tools  8.1
stl_util.h
Go to the documentation of this file.
1 // Copyright 2010-2018 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 <memory>
29 #include <string>
30 #include <type_traits>
31 #include <vector>
32 
33 #include "absl/meta/type_traits.h"
34 #include "absl/strings/internal/resize_uninitialized.h"
36 #include "ortools/base/macros.h"
37 
38 namespace gtl {
39 namespace internal {
40 template <typename LessFunc>
41 class Equiv {
42  public:
43  explicit Equiv(const LessFunc& f) : f_(f) {}
44  template <typename T>
45  bool operator()(const T& a, const T& b) const {
46  return !f_(b, a) && !f_(a, b);
47  }
48 
49  private:
50  LessFunc f_;
51 };
52 } // namespace internal
53 
54 // Sorts and removes duplicates from a sequence container.
55 // If specified, the 'less_func' is used to compose an
56 // equivalence comparator for the sorting and uniqueness tests.
57 template <typename T, typename LessFunc>
58 inline void STLSortAndRemoveDuplicates(T* v, const LessFunc& less_func) {
59  std::sort(v->begin(), v->end(), less_func);
60  v->erase(std::unique(v->begin(), v->end(),
62  v->end());
63 }
64 template <typename T>
65 inline void STLSortAndRemoveDuplicates(T* v) {
66  std::sort(v->begin(), v->end());
67  v->erase(std::unique(v->begin(), v->end()), v->end());
68 }
69 
70 // Stable sorts and removes duplicates from a sequence container, retaining
71 // the first equivalent element for each equivalence set.
72 // The 'less_func' is used to compose an equivalence comparator for the sorting
73 // and uniqueness tests.
74 template <typename T, typename LessFunc>
75 inline void STLStableSortAndRemoveDuplicates(T* v, const LessFunc& less_func) {
76  std::stable_sort(v->begin(), v->end(), less_func);
77  v->erase(std::unique(v->begin(), v->end(),
79  v->end());
80 }
81 // Stable sorts and removes duplicates from a sequence container, retaining
82 // the first equivalent element for each equivalence set, using < comparison and
83 // == equivalence testing.
84 template <typename T>
86  std::stable_sort(v->begin(), v->end());
87  v->erase(std::unique(v->begin(), v->end()), v->end());
88 }
89 
90 // Remove every occurrence of element e in v. See
91 // http://en.wikipedia.org/wiki/Erase-remove_idiom.
92 template <typename T, typename E>
93 void STLEraseAllFromSequence(T* v, const E& e) {
94  v->erase(std::remove(v->begin(), v->end(), e), v->end());
95 }
96 template <typename T, typename A, typename E>
97 void STLEraseAllFromSequence(std::list<T, A>* c, const E& e) {
98  c->remove(e);
99 }
100 template <typename T, typename A, typename E>
101 void STLEraseAllFromSequence(std::forward_list<T, A>* c, const E& e) {
102  c->remove(e);
103 }
104 
105 // Remove each element e in v satisfying pred(e).
106 template <typename T, typename P>
107 void STLEraseAllFromSequenceIf(T* v, P pred) {
108  v->erase(std::remove_if(v->begin(), v->end(), pred), v->end());
109 }
110 template <typename T, typename A, typename P>
111 void STLEraseAllFromSequenceIf(std::list<T, A>* c, P pred) {
112  c->remove_if(pred);
113 }
114 template <typename T, typename A, typename P>
115 void STLEraseAllFromSequenceIf(std::forward_list<T, A>* c, P pred) {
116  c->remove_if(pred);
117 }
118 
119 // Clears internal memory of an STL object by swapping the argument with a new,
120 // empty object. STL clear()/reserve(0) does not always free internal memory
121 // allocated.
122 template <typename T>
123 void STLClearObject(T* obj) {
124  T tmp;
125  tmp.swap(*obj);
126  // This reserve(0) is needed because "T tmp" sometimes allocates memory (arena
127  // implementation?), even though this may not always work.
128  obj->reserve(0);
129 }
130 // STLClearObject overload for deque, which is missing reserve().
131 template <typename T, typename A>
132 void STLClearObject(std::deque<T, A>* obj) {
133  std::deque<T, A> tmp;
134  tmp.swap(*obj);
135 }
136 
137 // Calls STLClearObject() if the object is bigger than the specified limit,
138 // otherwise calls the object's clear() member. This can be useful if you want
139 // to allow the object to hold on to its allocated memory as long as it's not
140 // too much.
141 //
142 // Note: The name is misleading since the object is always cleared, regardless
143 // of its size.
144 template <typename T>
145 inline void STLClearIfBig(T* obj, size_t limit = 1 << 20) {
146  if (obj->capacity() >= limit) {
147  STLClearObject(obj);
148  } else {
149  obj->clear();
150  }
151 }
152 // STLClearIfBig overload for deque, which is missing capacity().
153 template <typename T, typename A>
154 inline void STLClearIfBig(std::deque<T, A>* obj, size_t limit = 1 << 20) {
155  if (obj->size() >= limit) {
156  STLClearObject(obj);
157  } else {
158  obj->clear();
159  }
160 }
161 
162 // Removes all elements and reduces the number of buckets in a hash_set or
163 // hash_map back to the default if the current number of buckets is "limit" or
164 // more.
165 //
166 // Adding items to a hash container may add buckets, but removing items or
167 // calling clear() does not necessarily reduce the number of buckets. Having
168 // lots of buckets is good if you insert comparably many items in every
169 // iteration because you'll reduce collisions and table resizes. But having lots
170 // of buckets is bad if you insert few items in most subsequent iterations,
171 // because repeatedly clearing out all those buckets can get expensive.
172 //
173 // One solution is to call STLClearHashIfBig() with a "limit" value that is a
174 // small multiple of the typical number of items in your table. In the common
175 // case, this is equivalent to an ordinary clear. In the rare case where you
176 // insert a lot of items, the number of buckets is reset to the default to keep
177 // subsequent clear operations cheap. Note that the default number of buckets is
178 // 193 in the Gnu library implementation as of Jan '08.
179 template <typename T>
180 inline void STLClearHashIfBig(T* obj, size_t limit) {
181  if (obj->bucket_count() >= limit) {
182  T tmp;
183  tmp.swap(*obj);
184  } else {
185  obj->clear();
186  }
187 }
188 
189 // Reserves space in the given string only if the existing capacity is not
190 // already enough. This is useful for strings because string::reserve() may
191 // *shrink* the capacity in some cases, which is usually not what users want.
192 // The behavior of this function is similar to that of vector::reserve() but for
193 // string.
194 inline void STLStringReserveIfNeeded(std::string* s, size_t min_capacity) {
195  if (min_capacity > s->capacity()) s->reserve(min_capacity);
196 }
197 
198 // Like str->resize(new_size), except any new characters added to "*str" as a
199 // result of resizing may be left uninitialized, rather than being filled with
200 // '0' bytes. Typically used when code is then going to overwrite the backing
201 // store of the string with known data.
202 template <typename T, typename Traits, typename Alloc>
203 inline void STLStringResizeUninitialized(std::basic_string<T, Traits, Alloc>* s,
204  size_t new_size) {
206 }
207 
208 // Returns true if the string implementation supports a resize where
209 // the new characters added to the string are left untouched.
210 //
211 // (A better name might be "STLStringSupportsUninitializedResize", alluding to
212 // the previous function.)
213 template <typename T, typename Traits, typename Alloc>
215  const std::basic_string<T, Traits, Alloc>& s) {
217 }
218 
219 // Assigns the n bytes starting at ptr to the given string. This is intended to
220 // be faster than string::assign() in SOME cases, however, it's actually slower
221 // in some cases as well.
222 //
223 // Just use string::assign directly unless you have benchmarks showing that this
224 // function makes your code faster. (Even then, a future version of
225 // string::assign() may be faster than this.)
226 inline void STLAssignToString(std::string* str, const char* ptr, size_t n) {
228  if (n == 0) return;
229  memcpy(&*str->begin(), ptr, n);
230 }
231 
232 // Appends the n bytes starting at ptr to the given string. This is intended to
233 // be faster than string::append() in SOME cases, however, it's actually slower
234 // in some cases as well.
235 //
236 // Just use string::append directly unless you have benchmarks showing that this
237 // function makes your code faster. (Even then, a future version of
238 // string::append() may be faster than this.)
239 inline void STLAppendToString(std::string* str, const char* ptr, size_t n) {
240  if (n == 0) return;
241  size_t old_size = str->size();
242  STLStringResizeUninitialized(str, old_size + n);
243  memcpy(&*str->begin() + old_size, ptr, n);
244 }
245 
246 // Returns a mutable char* pointing to a string's internal buffer, which may not
247 // be null-terminated. Returns nullptr for an empty string. If not non-null,
248 // writing through this pointer will modify the string.
249 //
250 // string_as_array(&str)[i] is valid for 0 <= i < str.size() until the
251 // next call to a string method that invalidates iterators.
252 //
253 // In C++11 you may simply use &str[0] to get a mutable char*.
254 //
255 // Prior to C++11, there was no standard-blessed way of getting a mutable
256 // reference to a string's internal buffer. The requirement that string be
257 // contiguous is officially part of the C++11 standard [string.require]/5.
258 // According to Matt Austern, this should already work on all current C++98
259 // implementations.
260 inline char* string_as_array(std::string* str) {
261  // DO NOT USE const_cast<char*>(str->data())! See the unittest for why.
262  return str->empty() ? nullptr : &*str->begin();
263 }
264 
265 // Tests two hash maps/sets for equality. This exists because operator== in the
266 // STL can return false when the maps/sets contain identical elements. This is
267 // because it compares the internal hash tables which may be different if the
268 // order of insertions and deletions differed.
269 template <typename HashSet>
270 inline bool HashSetEquality(const HashSet& set_a, const HashSet& set_b) {
271  if (set_a.size() != set_b.size()) return false;
272  for (typename HashSet::const_iterator i = set_a.begin(); i != set_a.end();
273  ++i)
274  if (set_b.find(*i) == set_b.end()) return false;
275  return true;
276 }
277 
278 // WARNING: Using HashMapEquality for multiple-associative containers like
279 // multimap and hash_multimap will result in wrong behavior.
280 
281 template <typename HashMap, typename BinaryPredicate>
282 inline bool HashMapEquality(const HashMap& map_a, const HashMap& map_b,
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();
286  ++i) {
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;
290  }
291  return true;
292 }
293 
294 // We overload for 'map' without a specialized functor and simply use its
295 // operator== function.
296 template <typename K, typename V, typename C, typename A>
297 inline bool HashMapEquality(const std::map<K, V, C, A>& map_a,
298  const std::map<K, V, C, A>& map_b) {
299  return map_a == map_b;
300 }
301 
302 template <typename HashMap>
303 inline bool HashMapEquality(const HashMap& a, const HashMap& b) {
304  using Mapped = typename HashMap::mapped_type;
305  return HashMapEquality(a, b, std::equal_to<Mapped>());
306 }
307 
308 // Calls delete (non-array version) on pointers in the range [begin, end).
309 //
310 // Note: If you're calling this on an entire container, you probably want to
311 // call STLDeleteElements(&container) instead (which also clears the container),
312 // or use an ElementDeleter.
313 template <typename ForwardIterator>
314 void STLDeleteContainerPointers(ForwardIterator begin, ForwardIterator end) {
315  while (begin != end) {
316  auto temp = begin;
317  ++begin;
318  delete *temp;
319  }
320 }
321 
322 // Calls delete (non-array version) on BOTH items (pointers) in each pair in the
323 // range [begin, end).
324 template <typename ForwardIterator>
325 void STLDeleteContainerPairPointers(ForwardIterator begin,
326  ForwardIterator end) {
327  while (begin != end) {
328  auto temp = begin;
329  ++begin;
330  delete temp->first;
331  delete temp->second;
332  }
333 }
334 
335 // Calls delete (non-array version) on the FIRST item (pointer) in each pair in
336 // the range [begin, end).
337 template <typename ForwardIterator>
338 void STLDeleteContainerPairFirstPointers(ForwardIterator begin,
339  ForwardIterator end) {
340  while (begin != end) {
341  auto temp = begin;
342  ++begin;
343  delete temp->first;
344  }
345 }
346 
347 // Calls delete (non-array version) on the SECOND item (pointer) in each pair in
348 // the range [begin, end).
349 //
350 // Note: If you're calling this on an entire container, you probably want to
351 // call STLDeleteValues(&container) instead, or use ValueDeleter.
352 template <typename ForwardIterator>
353 void STLDeleteContainerPairSecondPointers(ForwardIterator begin,
354  ForwardIterator end) {
355  while (begin != end) {
356  auto temp = begin;
357  ++begin;
358  delete temp->second;
359  }
360 }
361 
362 // Deletes all the elements in an STL container and clears the container. This
363 // function is suitable for use with a vector, set, hash_set, or any other STL
364 // container which defines sensible begin(), end(), and clear() methods.
365 //
366 // If container is nullptr, this function is a no-op.
367 //
368 // As an alternative to calling STLDeleteElements() directly, consider
369 // ElementDeleter (defined below), which ensures that your container's elements
370 // are deleted when the ElementDeleter goes out of scope.
371 template <typename T>
372 void STLDeleteElements(T* container) {
373  if (!container) return;
374  STLDeleteContainerPointers(container->begin(), container->end());
375  container->clear();
376 }
377 
378 // Given an STL container consisting of (key, value) pairs, STLDeleteValues
379 // deletes all the "value" components and clears the container. Does nothing in
380 // the case it's given a nullptr.
381 template <typename T>
382 void STLDeleteValues(T* v) {
383  if (!v) return;
384  (STLDeleteContainerPairSecondPointers)(v->begin(), v->end());
385  v->clear();
386 }
387 
388 // A very simple interface that simply provides a virtual destructor. It is used
389 // as a non-templated base class for the TemplatedElementDeleter and
390 // TemplatedValueDeleter classes.
391 //
392 // Clients should NOT use this class directly.
393 class BaseDeleter {
394  public:
395  virtual ~BaseDeleter() {}
396  BaseDeleter(const BaseDeleter&) = delete;
397  void operator=(const BaseDeleter&) = delete;
398 
399  protected:
401 };
402 
403 // Given a pointer to an STL container, this class will delete all the element
404 // pointers when it goes out of scope.
405 //
406 // Clients should NOT use this class directly. Use ElementDeleter instead.
407 template <typename STLContainer>
409  public:
410  explicit TemplatedElementDeleter(STLContainer* ptr) : container_ptr_(ptr) {}
411 
412  virtual ~TemplatedElementDeleter() { STLDeleteElements(container_ptr_); }
413 
415  void operator=(const TemplatedElementDeleter&) = delete;
416 
417  private:
418  STLContainer* container_ptr_;
419 };
420 
421 // ElementDeleter is an RAII (go/raii) object that deletes the elements in the
422 // given container when it goes out of scope. This is similar to
423 // std::unique_ptr<> except that a container's elements will be deleted rather
424 // than the container itself.
425 //
426 // Example:
427 // std::vector<MyProto*> tmp_proto;
428 // ElementDeleter d(&tmp_proto);
429 // if (...) return false;
430 // ...
431 // return success;
432 //
433 // Since C++11, consider using containers of std::unique_ptr instead.
435  public:
436  template <typename STLContainer>
437  explicit ElementDeleter(STLContainer* ptr)
438  : deleter_(new TemplatedElementDeleter<STLContainer>(ptr)) {}
439 
440  ~ElementDeleter() { delete deleter_; }
441 
442  ElementDeleter(const ElementDeleter&) = delete;
443  void operator=(const ElementDeleter&) = delete;
444 
445  private:
446  BaseDeleter* deleter_;
447 };
448 
449 // Given a pointer to an STL container this class will delete all the value
450 // pointers when it goes out of scope.
451 //
452 // Clients should NOT use this class directly. Use ValueDeleter instead.
453 template <typename STLContainer>
455  public:
456  explicit TemplatedValueDeleter(STLContainer* ptr) : container_ptr_(ptr) {}
457 
458  virtual ~TemplatedValueDeleter() { STLDeleteValues(container_ptr_); }
459 
461  void operator=(const TemplatedValueDeleter&) = delete;
462 
463  private:
464  STLContainer* container_ptr_;
465 };
466 
467 // ValueDeleter is an RAII (go/raii) object that deletes the 'second' member in
468 // the given container of std::pair<>s when it goes out of scope.
469 //
470 // Example:
471 // std::map<std::string, Foo*> foo_map;
472 // ValueDeleter d(&foo_map);
473 // if (...) return false;
474 // ...
475 // return success;
477  public:
478  template <typename STLContainer>
479  explicit ValueDeleter(STLContainer* ptr)
480  : deleter_(new TemplatedValueDeleter<STLContainer>(ptr)) {}
481 
482  ~ValueDeleter() { delete deleter_; }
483 
484  ValueDeleter(const ValueDeleter&) = delete;
485  void operator=(const ValueDeleter&) = delete;
486 
487  private:
488  BaseDeleter* deleter_;
489 };
490 
491 // RAII (go/raii) object that deletes elements in the given container when it
492 // goes out of scope. Like ElementDeleter (above) except that this class is
493 // templated and doesn't have a virtual destructor.
494 //
495 // New code should prefer ElementDeleter.
496 template <typename STLContainer>
498  public:
499  STLElementDeleter(STLContainer* ptr) : container_ptr_(ptr) {}
500  ~STLElementDeleter() { STLDeleteElements(container_ptr_); }
501 
502  private:
503  STLContainer* container_ptr_;
504 };
505 
506 // RAII (go/raii) object that deletes the values in the given container of
507 // std::pair<>s when it goes out of scope. Like ValueDeleter (above) except that
508 // this class is templated and doesn't have a virtual destructor.
509 //
510 // New code should prefer ValueDeleter.
511 template <typename STLContainer>
513  public:
514  STLValueDeleter(STLContainer* ptr) : container_ptr_(ptr) {}
515  ~STLValueDeleter() { STLDeleteValues(container_ptr_); }
516 
517  private:
518  STLContainer* container_ptr_;
519 };
520 
521 // Sets the referenced pointer to nullptr and returns its original value. This
522 // can be a convenient way to remove a pointer from a container to avoid the
523 // eventual deletion by an ElementDeleter.
524 //
525 // Example:
526 //
527 // std::vector<Foo*> v{new Foo, new Foo, new Foo};
528 // ElementDeleter d(&v);
529 // Foo* safe = release_ptr(&v[1]);
530 // // v[1] is now nullptr and the Foo it previously pointed to is now
531 // // stored in "safe"
532 template <typename T>
533 ABSL_MUST_USE_RESULT T* release_ptr(T** ptr) {
534  assert(ptr);
535  T* tmp = *ptr;
536  *ptr = nullptr;
537  return tmp;
538 }
539 
540 namespace stl_util_internal {
541 
542 // Like std::less, but allows heterogeneous arguments.
544  template <typename T>
545  bool operator()(const T& a, const T& b) const {
546  // std::less is better than '<' here, because it can order pointers.
547  return std::less<T>()(a, b);
548  }
549  template <typename T1, typename T2>
550  bool operator()(const T1& a, const T2& b) const {
551  return a < b;
552  }
553 };
554 
555 // Trait to detect whether a type T is an hash table.
556 // The heuristic used is that the type contains an inner type `hasher` and does
557 // not contain an inner type `reverse_iterator`.
558 // If the container is iterable in reverse, then order might actually matter.
559 template <typename, typename = void, typename = void>
560 struct Unordered : std::false_type {};
561 
562 template <typename T>
563 struct Unordered<T, absl::void_t<typename T::hasher>> : std::true_type {};
564 
565 template <typename T>
566 struct Unordered<T, absl::void_t<typename T::hasher>,
567  absl::void_t<typename T::reverse_iterator>> : std::false_type {
568 };
569 
570 } // namespace stl_util_internal
571 
572 // STLSetDifference:
573 //
574 // In1 STLSetDifference(a, b);
575 // In1 STLSetDifference(a, b, compare);
576 // void STLSetDifference(a, b, &out);
577 // void STLSetDifference(a, b, &out, compare);
578 // Out STLSetDifferenceAs<Out>(a, b);
579 // Out STLSetDifferenceAs<Out>(a, b, compare);
580 //
581 // Appends the elements in "a" that are not in "b" to an output container.
582 // Optionally specify a comparator, or '<' is used by default. Both input
583 // containers must be sorted with respect to the comparator. If specified,
584 // the output container must be distinct from both "a" and "b".
585 //
586 // If an output container pointer is not given, a container will be returned
587 // by value. The return type can be explicitly specified by calling
588 // STLSetDifferenceAs, but it defaults to the type of argument "a".
589 //
590 // See std::set_difference() for details on how set difference is computed.
591 //
592 // The form taking 4 arguments. All other forms call into this one.
593 // Explicit comparator, append to output container.
594 template <typename In1, typename In2, typename Out, typename Compare>
595 void STLSetDifference(const In1& a, const In2& b, Out* out, Compare 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);
606 }
607 // Append to output container, Implicit comparator.
608 // Note: The 'enable_if' keeps this overload from participating in
609 // overload resolution if 'out' is a function pointer, gracefully forcing
610 // the 3-argument overload that treats the third argument as a comparator.
611 template <typename In1, typename In2, typename Out>
613 STLSetDifference(const In1& a, const In2& b, Out* out) {
615 }
616 // Explicit comparator, explicit return type.
617 template <typename Out, typename In1, typename In2, typename Compare>
618 Out STLSetDifferenceAs(const In1& a, const In2& b, Compare compare) {
619  Out out;
620  STLSetDifference(a, b, &out, compare);
621  return out;
622 }
623 // Implicit comparator, explicit return type.
624 template <typename Out, typename In1, typename In2>
625 Out STLSetDifferenceAs(const In1& a, const In2& b) {
626  return STLSetDifferenceAs<Out>(a, b,
628 }
629 // Explicit comparator, implicit return type.
630 template <typename In1, typename In2, typename Compare>
631 In1 STLSetDifference(const In1& a, const In2& b, Compare compare) {
632  return STLSetDifferenceAs<In1>(a, b, compare);
633 }
634 // Implicit comparator, implicit return type.
635 template <typename In1, typename In2>
636 In1 STLSetDifference(const In1& a, const In2& b) {
638 }
639 template <typename In1>
640 In1 STLSetDifference(const In1& a, const In1& b) {
642 }
643 
644 // STLSetUnion:
645 //
646 // In1 STLSetUnion(a, b);
647 // In1 STLSetUnion(a, b, compare);
648 // void STLSetUnion(a, b, &out);
649 // void STLSetUnion(a, b, &out, compare);
650 // Out STLSetUnionAs<Out>(a, b);
651 // Out STLSetUnionAs<Out>(a, b, compare);
652 // Appends the elements in one or both of the input containers to output
653 // container "out". Both input containers must be sorted with operator '<',
654 // or with the comparator if specified. "out" must be distinct from both "a"
655 // and "b".
656 //
657 // See std::set_union() for how set union is computed.
658 template <typename In1, typename In2, typename Out, typename Compare>
659 void STLSetUnion(const In1& a, const In2& b, Out* out, Compare 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);
670 }
671 // Note: The 'enable_if' keeps this overload from participating in
672 // overload resolution if 'out' is a function pointer, gracefully forcing
673 // the 3-argument overload that treats the third argument as a comparator.
674 template <typename In1, typename In2, typename Out>
676  const In1& a, const In2& b, Out* out) {
678 }
679 template <typename Out, typename In1, typename In2, typename Compare>
680 Out STLSetUnionAs(const In1& a, const In2& b, Compare compare) {
681  Out out;
682  STLSetUnion(a, b, &out, compare);
683  return out;
684 }
685 template <typename Out, typename In1, typename In2>
686 Out STLSetUnionAs(const In1& a, const In2& b) {
687  return STLSetUnionAs<Out>(a, b, gtl::stl_util_internal::TransparentLess());
688 }
689 template <typename In1, typename In2, typename Compare>
690 In1 STLSetUnion(const In1& a, const In2& b, Compare compare) {
691  return STLSetUnionAs<In1>(a, b, compare);
692 }
693 template <typename In1, typename In2>
694 In1 STLSetUnion(const In1& a, const In2& b) {
696 }
697 template <typename In1>
698 In1 STLSetUnion(const In1& a, const In1& b) {
700 }
701 
702 // STLSetSymmetricDifference:
703 //
704 // In1 STLSetSymmetricDifference(a, b);
705 // In1 STLSetSymmetricDifference(a, b, compare);
706 // void STLSetSymmetricDifference(a, b, &out);
707 // void STLSetSymmetricDifference(a, b, &out, compare);
708 // Out STLSetSymmetricDifferenceAs<Out>(a, b);
709 // Out STLSetSymmetricDifferenceAs<Out>(a, b, compare);
710 //
711 // Appends the elements in "a" that are not in "b", and the elements in "b"
712 // that are not in "a", to output container "out". Both input containers
713 // must be sorted with operator '<', or with the comparator if specified.
714 // "out" must be distinct from both "a" and "b".
715 //
716 // See std::set_symmetric_difference() for how these elements are selected.
717 template <typename In1, typename In2, typename Out, typename Compare>
718 void STLSetSymmetricDifference(const In1& a, const In2& b, Out* out,
719  Compare 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);
730 }
731 // Note: The 'enable_if' keeps this overload from participating in
732 // overload resolution if 'out' is a function pointer, gracefully forcing
733 // the 3-argument overload that treats the third argument as a comparator.
734 template <typename In1, typename In2, typename Out>
736 STLSetSymmetricDifference(const In1& a, const In2& b, Out* out) {
737  return STLSetSymmetricDifference(a, b, out,
739 }
740 template <typename Out, typename In1, typename In2, typename Compare>
741 Out STLSetSymmetricDifferenceAs(const In1& a, const In2& b, Compare comp) {
742  Out out;
743  STLSetSymmetricDifference(a, b, &out, comp);
744  return out;
745 }
746 template <typename Out, typename In1, typename In2>
747 Out STLSetSymmetricDifferenceAs(const In1& a, const In2& b) {
748  return STLSetSymmetricDifferenceAs<Out>(
750 }
751 template <typename In1, typename In2, typename Compare>
752 In1 STLSetSymmetricDifference(const In1& a, const In2& b, Compare comp) {
753  return STLSetSymmetricDifferenceAs<In1>(a, b, comp);
754 }
755 template <typename In1, typename In2>
756 In1 STLSetSymmetricDifference(const In1& a, const In2& b) {
757  return STLSetSymmetricDifference(a, b,
759 }
760 template <typename In1>
761 In1 STLSetSymmetricDifference(const In1& a, const In1& b) {
762  return STLSetSymmetricDifference(a, b,
764 }
765 
766 // STLSetIntersection:
767 //
768 // In1 STLSetIntersection(a, b);
769 // In1 STLSetIntersection(a, b, compare);
770 // void STLSetIntersection(a, b, &out);
771 // void STLSetIntersection(a, b, &out, compare);
772 // Out STLSetIntersectionAs<Out>(a, b);
773 // Out STLSetIntersectionAs<Out>(a, b, compare);
774 //
775 // Appends the elements that are in both "a" and "b" to output container
776 // "out". Both input containers must be sorted with operator '<' or with
777 // "compare" if specified. "out" must be distinct from both "a" and "b".
778 //
779 // See std::set_intersection() for how set intersection is computed.
780 template <typename In1, typename In2, typename Out, typename Compare>
781 void STLSetIntersection(const In1& a, const In2& b, Out* out, Compare 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);
792 }
793 // Note: The 'enable_if' keeps this overload from participating in
794 // overload resolution if 'out' is a function pointer, gracefully forcing
795 // the 3-argument overload that treats the third argument as a comparator.
796 template <typename In1, typename In2, typename Out>
798 STLSetIntersection(const In1& a, const In2& b, Out* out) {
799  return STLSetIntersection(a, b, out,
801 }
802 template <typename Out, typename In1, typename In2, typename Compare>
803 Out STLSetIntersectionAs(const In1& a, const In2& b, Compare compare) {
804  Out out;
805  STLSetIntersection(a, b, &out, compare);
806  return out;
807 }
808 template <typename Out, typename In1, typename In2>
809 Out STLSetIntersectionAs(const In1& a, const In2& b) {
810  return STLSetIntersectionAs<Out>(a, b,
812 }
813 template <typename In1, typename In2, typename Compare>
814 In1 STLSetIntersection(const In1& a, const In2& b, Compare compare) {
815  return STLSetIntersectionAs<In1>(a, b, compare);
816 }
817 template <typename In1, typename In2>
818 In1 STLSetIntersection(const In1& a, const In2& b) {
820 }
821 template <typename In1>
822 In1 STLSetIntersection(const In1& a, const In1& b) {
824 }
825 
826 // Returns true iff every element in "b" is also in "a". Both containers
827 // must be sorted by the specified comparator, or by '<' if none is given.
828 template <typename In1, typename In2, typename Compare>
829 bool STLIncludes(const In1& a, const In2& b, Compare 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);
837 }
838 template <typename In1, typename In2>
839 bool STLIncludes(const In1& a, const In2& b) {
841 }
842 
843 // SortedRangesHaveIntersection:
844 //
845 // bool SortedRangesHaveIntersection(begin1, end1, begin2, end2);
846 // bool SortedRangesHaveIntersection(begin1, end1, begin2, end2,
847 // comparator);
848 //
849 // Returns true iff any element in the sorted range [begin1, end1) is
850 // equivalent to any element in the sorted range [begin2, end2). The iterators
851 // themselves do not have to be the same type, but the value types must be
852 // sorted either by the specified comparator, or by '<' if no comparator is
853 // given.
854 // [Two elements a,b are considered equivalent if !(a < b) && !(b < a) ].
855 template <typename InputIterator1, typename InputIterator2, typename Comp>
856 bool SortedRangesHaveIntersection(InputIterator1 begin1, InputIterator1 end1,
857  InputIterator2 begin2, InputIterator2 end2,
858  Comp comparator) {
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)) {
863  ++begin1;
864  continue;
865  }
866  if (comparator(*begin2, *begin1)) {
867  ++begin2;
868  continue;
869  }
870  return true;
871  }
872  return false;
873 }
874 template <typename InputIterator1, typename InputIterator2>
875 bool SortedRangesHaveIntersection(InputIterator1 begin1, InputIterator1 end1,
876  InputIterator2 begin2, InputIterator2 end2) {
878  begin1, end1, begin2, end2, gtl::stl_util_internal::TransparentLess());
879 }
880 
881 // Returns true iff the ordered containers 'in1' and 'in2' have a non-empty
882 // intersection. The container elements do not have to be the same type, but the
883 // elements must be sorted either by the specified comparator, or by '<' if no
884 // comparator is given.
885 template <typename In1, typename In2, typename Comp>
886 bool SortedContainersHaveIntersection(const In1& in1, const In2& in2,
887  Comp comparator) {
888  return SortedRangesHaveIntersection(in1.begin(), in1.end(), in2.begin(),
889  in2.end(), comparator);
890 }
891 template <typename In1, typename In2>
892 bool SortedContainersHaveIntersection(const In1& in1, const In2& in2) {
895 }
896 
897 // An std::allocator<T> subclass that keeps count of the active bytes allocated
898 // by this class of allocators. This allocator is thread compatible
899 // (go/thread-compatible). This should only be used in situations where you can
900 // ensure that only a single thread performs allocation and deallocation.
901 //
902 // Example:
903 // using MyAlloc = STLCountingAllocator<std::string>;
904 // int64 bytes = 0;
905 // std::vector<std::string, MyAlloc> v(MyAlloc(&bytes));
906 // v.push_back("hi");
907 // LOG(INFO) << "Bytes allocated " << bytes;
908 //
909 template <typename T, typename Alloc = std::allocator<T>>
910 class STLCountingAllocator : public Alloc {
911  public:
912  using Base = Alloc;
913  using pointer = typename Alloc::pointer;
914  using size_type = typename Alloc::size_type;
915 
916  STLCountingAllocator() : bytes_used_(nullptr) {}
917  explicit STLCountingAllocator(int64* b) : bytes_used_(b) {}
918 
919  // Constructor used for rebinding
920  template <typename U, typename B>
922  : Alloc(x), bytes_used_(x.bytes_used()) {}
923 
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);
929  }
930 
932  Alloc::deallocate(p, n);
933  assert(bytes_used_ != nullptr);
934  *bytes_used_ -= n * sizeof(T);
935  }
936 
937  // Rebind allows an std::allocator<T> to be used for a different type
938  template <typename U>
939  class rebind {
940  using OtherA = typename Alloc::template rebind<U>::other;
941 
942  public:
944  };
945 
946  int64* bytes_used() const { return bytes_used_; }
947 
948  private:
949  int64* bytes_used_;
950 };
951 
952 template <typename A>
953 class STLCountingAllocator<void, A> : public A {
954  public:
955  STLCountingAllocator() : bytes_used_(nullptr) {}
956  explicit STLCountingAllocator(int64* b) : bytes_used_(b) {}
957 
958  // Constructor used for rebinding
959  template <typename U, typename B>
961  : A(x), bytes_used_(x.bytes_used()) {}
962 
963  template <typename U>
964  class rebind {
965  using OtherA = typename A::template rebind<U>::other;
966 
967  public:
969  };
970  int64* bytes_used() const { return bytes_used_; }
971 
972  private:
973  int64* bytes_used_;
974 };
975 
976 template <typename T, typename A>
978  const STLCountingAllocator<T, A>& b) {
979  using Base = typename STLCountingAllocator<T, A>::Base;
980  return static_cast<const Base&>(a) == static_cast<const Base&>(b) &&
981  a.bytes_used() == b.bytes_used();
982 }
983 
984 template <typename T, typename A>
986  const STLCountingAllocator<T, A>& b) {
987  return !(a == b);
988 }
989 
990 } // namespace gtl
991 #endif // OR_TOOLS_BASE_STL_UTIL_H_
gtl::ElementDeleter::ElementDeleter
ElementDeleter(STLContainer *ptr)
Definition: stl_util.h:437
gtl::STLStringSupportsNontrashingResize
bool STLStringSupportsNontrashingResize(const std::basic_string< T, Traits, Alloc > &s)
Definition: stl_util.h:214
gtl::operator!=
bool operator!=(const STLCountingAllocator< T, A > &a, const STLCountingAllocator< T, A > &b)
Definition: stl_util.h:985
integral_types.h
gtl::STLDeleteContainerPairPointers
void STLDeleteContainerPairPointers(ForwardIterator begin, ForwardIterator end)
Definition: stl_util.h:325
gtl::STLElementDeleter
Definition: stl_util.h:497
gtl::SortedRangesHaveIntersection
bool SortedRangesHaveIntersection(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, Comp comparator)
Definition: stl_util.h:856
gtl::stl_util_internal::Unordered
Definition: stl_util.h:560
gtl::BaseDeleter
Definition: stl_util.h:393
gtl::ValueDeleter::~ValueDeleter
~ValueDeleter()
Definition: stl_util.h:482
gtl::ElementDeleter::operator=
void operator=(const ElementDeleter &)=delete
gtl::STLClearObject
void STLClearObject(T *obj)
Definition: stl_util.h:123
gtl::TemplatedElementDeleter::TemplatedElementDeleter
TemplatedElementDeleter(const TemplatedElementDeleter &)=delete
gtl::BaseDeleter::BaseDeleter
BaseDeleter()
Definition: stl_util.h:400
value
int64 value
Definition: demon_profiler.cc:43
gtl::STLAssignToString
void STLAssignToString(std::string *str, const char *ptr, size_t n)
Definition: stl_util.h:226
gtl::stl_util_internal::TransparentLess
Definition: stl_util.h:543
gtl::internal::Equiv::Equiv
Equiv(const LessFunc &f)
Definition: stl_util.h:43
gtl::STLValueDeleter::~STLValueDeleter
~STLValueDeleter()
Definition: stl_util.h:515
gtl::STLSetUnion
void STLSetUnion(const In1 &a, const In2 &b, Out *out, Compare compare)
Definition: stl_util.h:659
macros.h
gtl::STLValueDeleter
Definition: stl_util.h:512
gtl::STLCountingAllocator::STLCountingAllocator
STLCountingAllocator(int64 *b)
Definition: stl_util.h:917
int64
int64_t int64
Definition: integral_types.h:34
gtl::ElementDeleter::ElementDeleter
ElementDeleter(const ElementDeleter &)=delete
gtl::BaseDeleter::~BaseDeleter
virtual ~BaseDeleter()
Definition: stl_util.h:395
gtl::STLCountingAllocator::size_type
typename Alloc::size_type size_type
Definition: stl_util.h:914
gtl::STLElementDeleter::~STLElementDeleter
~STLElementDeleter()
Definition: stl_util.h:500
gtl::STLCountingAllocator::pointer
typename Alloc::pointer pointer
Definition: stl_util.h:913
gtl::ValueDeleter
Definition: stl_util.h:476
gtl::TemplatedValueDeleter::TemplatedValueDeleter
TemplatedValueDeleter(STLContainer *ptr)
Definition: stl_util.h:456
gtl::STLSetSymmetricDifference
void STLSetSymmetricDifference(const In1 &a, const In2 &b, Out *out, Compare compare)
Definition: stl_util.h:718
gtl::STLIncludes
bool STLIncludes(const In1 &a, const In2 &b, Compare compare)
Definition: stl_util.h:829
gtl::STLSetDifference
void STLSetDifference(const In1 &a, const In2 &b, Out *out, Compare compare)
Definition: stl_util.h:595
a
int64 a
Definition: constraint_solver/table.cc:42
gtl::STLAppendToString
void STLAppendToString(std::string *str, const char *ptr, size_t n)
Definition: stl_util.h:239
gtl::BaseDeleter::BaseDeleter
BaseDeleter(const BaseDeleter &)=delete
gtl::HashSetEquality
bool HashSetEquality(const HashSet &set_a, const HashSet &set_b)
Definition: stl_util.h:270
gtl::internal::Equiv
Definition: stl_util.h:41
gtl::STLDeleteContainerPairFirstPointers
void STLDeleteContainerPairFirstPointers(ForwardIterator begin, ForwardIterator end)
Definition: stl_util.h:338
gtl
Definition: container_logging.h:46
gtl::STLCountingAllocator::bytes_used
int64 * bytes_used() const
Definition: stl_util.h:946
gtl::TemplatedElementDeleter::~TemplatedElementDeleter
virtual ~TemplatedElementDeleter()
Definition: stl_util.h:412
gtl::operator==
bool operator==(const STLCountingAllocator< T, A > &a, const STLCountingAllocator< T, A > &b)
Definition: stl_util.h:977
gtl::STLSortAndRemoveDuplicates
void STLSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
Definition: stl_util.h:58
gtl::STLValueDeleter::STLValueDeleter
STLValueDeleter(STLContainer *ptr)
Definition: stl_util.h:514
gtl::STLDeleteContainerPairSecondPointers
void STLDeleteContainerPairSecondPointers(ForwardIterator begin, ForwardIterator end)
Definition: stl_util.h:353
gtl::TemplatedElementDeleter
Definition: stl_util.h:408
gtl::string_as_array
char * string_as_array(std::string *str)
Definition: stl_util.h:260
gtl::STLSetDifferenceAs
Out STLSetDifferenceAs(const In1 &a, const In2 &b, Compare compare)
Definition: stl_util.h:618
gtl::STLCountingAllocator::allocate
pointer allocate(size_type n, std::allocator< void >::const_pointer hint=nullptr)
Definition: stl_util.h:924
gtl::STLCountingAllocator< void, A >::bytes_used
int64 * bytes_used() const
Definition: stl_util.h:970
gtl::stl_util_internal::TransparentLess::operator()
bool operator()(const T1 &a, const T2 &b) const
Definition: stl_util.h:550
gtl::ValueDeleter::ValueDeleter
ValueDeleter(const ValueDeleter &)=delete
gtl::ValueDeleter::operator=
void operator=(const ValueDeleter &)=delete
gtl::STLElementDeleter::STLElementDeleter
STLElementDeleter(STLContainer *ptr)
Definition: stl_util.h:499
gtl::ElementDeleter::~ElementDeleter
~ElementDeleter()
Definition: stl_util.h:440
gtl::TemplatedValueDeleter::operator=
void operator=(const TemplatedValueDeleter &)=delete
gtl::STLCountingAllocator::deallocate
void deallocate(pointer p, size_type n)
Definition: stl_util.h:931
gtl::STLSetIntersectionAs
Out STLSetIntersectionAs(const In1 &a, const In2 &b, Compare compare)
Definition: stl_util.h:803
gtl::HashMapEquality
bool HashMapEquality(const HashMap &map_a, const HashMap &map_b, BinaryPredicate mapped_type_equal)
Definition: stl_util.h:282
gtl::TemplatedValueDeleter::TemplatedValueDeleter
TemplatedValueDeleter(const TemplatedValueDeleter &)=delete
gtl::STLCountingAllocator::rebind
Definition: stl_util.h:939
gtl::STLCountingAllocator::STLCountingAllocator
STLCountingAllocator(const STLCountingAllocator< U, B > &x)
Definition: stl_util.h:921
gtl::STLDeleteContainerPointers
void STLDeleteContainerPointers(ForwardIterator begin, ForwardIterator end)
Definition: stl_util.h:314
gtl::STLStringReserveIfNeeded
void STLStringReserveIfNeeded(std::string *s, size_t min_capacity)
Definition: stl_util.h:194
gtl::STLStringResizeUninitialized
void STLStringResizeUninitialized(std::basic_string< T, Traits, Alloc > *s, size_t new_size)
Definition: stl_util.h:203
gtl::STLClearHashIfBig
void STLClearHashIfBig(T *obj, size_t limit)
Definition: stl_util.h:180
gtl::STLSetIntersection
void STLSetIntersection(const In1 &a, const In2 &b, Out *out, Compare compare)
Definition: stl_util.h:781
gtl::TemplatedElementDeleter::TemplatedElementDeleter
TemplatedElementDeleter(STLContainer *ptr)
Definition: stl_util.h:410
b
int64 b
Definition: constraint_solver/table.cc:43
gtl::internal::Equiv::operator()
bool operator()(const T &a, const T &b) const
Definition: stl_util.h:45
gtl::STLStableSortAndRemoveDuplicates
void STLStableSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
Definition: stl_util.h:75
internal
Definition: bop_parameters.pb.h:39
gtl::STLEraseAllFromSequence
void STLEraseAllFromSequence(T *v, const E &e)
Definition: stl_util.h:93
gtl::STLCountingAllocator< void, A >::STLCountingAllocator
STLCountingAllocator(const STLCountingAllocator< U, B > &x)
Definition: stl_util.h:960
absl
Definition: cleanup.h:22
gtl::STLDeleteElements
void STLDeleteElements(T *container)
Definition: stl_util.h:372
gtl::STLClearIfBig
void STLClearIfBig(T *obj, size_t limit=1<< 20)
Definition: stl_util.h:145
gtl::ElementDeleter
Definition: stl_util.h:434
gtl::TemplatedElementDeleter::operator=
void operator=(const TemplatedElementDeleter &)=delete
gtl::STLSetUnionAs
Out STLSetUnionAs(const In1 &a, const In2 &b, Compare compare)
Definition: stl_util.h:680
gtl::STLCountingAllocator< void, A >::STLCountingAllocator
STLCountingAllocator()
Definition: stl_util.h:955
gtl::STLCountingAllocator::STLCountingAllocator
STLCountingAllocator()
Definition: stl_util.h:916
gtl::STLSetSymmetricDifferenceAs
Out STLSetSymmetricDifferenceAs(const In1 &a, const In2 &b, Compare comp)
Definition: stl_util.h:741
gtl::ValueDeleter::ValueDeleter
ValueDeleter(STLContainer *ptr)
Definition: stl_util.h:479
gtl::release_ptr
ABSL_MUST_USE_RESULT T * release_ptr(T **ptr)
Definition: stl_util.h:533
gtl::STLEraseAllFromSequenceIf
void STLEraseAllFromSequenceIf(T *v, P pred)
Definition: stl_util.h:107
gtl::STLCountingAllocator::Base
Alloc Base
Definition: stl_util.h:912
gtl::STLCountingAllocator< void, A >::STLCountingAllocator
STLCountingAllocator(int64 *b)
Definition: stl_util.h:956
gtl::STLCountingAllocator
Definition: stl_util.h:910
gtl::TemplatedValueDeleter
Definition: stl_util.h:454
gtl::STLDeleteValues
void STLDeleteValues(T *v)
Definition: stl_util.h:382
gtl::stl_util_internal::TransparentLess::operator()
bool operator()(const T &a, const T &b) const
Definition: stl_util.h:545
gtl::SortedContainersHaveIntersection
bool SortedContainersHaveIntersection(const In1 &in1, const In2 &in2, Comp comparator)
Definition: stl_util.h:886
gtl::TemplatedValueDeleter::~TemplatedValueDeleter
virtual ~TemplatedValueDeleter()
Definition: stl_util.h:458
gtl::BaseDeleter::operator=
void operator=(const BaseDeleter &)=delete