OR-Tools  8.2
strong_vector.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 // This file provides the StrongVector container that wraps around the STL
15 // std::vector.
16 // The wrapper restricts indexing to a pre-specified type-safe integer type or
17 // IntType (see int_type.h). It prevents accidental indexing
18 // by different "logical" integer-like types (e.g. another IntType) or native
19 // integer types. The wrapper is useful as C++ and the standard template
20 // library allows the user to mix "logical" integral indices that might have a
21 // different role.
22 //
23 // The container can only be indexed by an instance of an IntType class, which
24 // can be declared as:
25 //
26 // DEFINE_INT_TYPE(IntTypeName, IntTypeValueType);
27 //
28 // where IntTypeName is the desired name for the "logical" integer-like type
29 // and the ValueType is a supported native integer type such as int or
30 // uint64 (see int_type.h for details).
31 //
32 // The wrapper exposes all public methods of STL vector and behaves mostly as
33 // pass-through. The only method modified to ensure type-safety is the operator
34 // [] and the at() method.
35 //
36 // EXAMPLES --------------------------------------------------------------------
37 //
38 // DEFINE_INT_TYPE(PhysicalChildIndex, int32);
39 // absl::StrongVector<PhysicalChildIndex, ChildStats*> vec;
40 //
41 // PhysicalChildIndex physical_index;
42 // vec[physical_index] = ...; <-- index type match: compiles properly.
43 // vec.at(physical_index) = ...; <-- index type match: compiles properly.
44 //
45 // int32 physical_index;
46 // vec[physical_index] = ...; <-- fails to compile.
47 // vec.at(physical_index) = ...; <-- fails to compile.
48 //
49 // DEFINE_INT_TYPE(LogicalChildIndex, int32);
50 // int32 logical_index;
51 // vec[logical_index] = ...; <-- fails to compile.
52 // vec.at(logical_index) = ...; <-- fails to compile.
53 //
54 // NB: Iterator arithmetic is not allowed as the iterators are not wrapped
55 // themselves. Therefore, the following caveat is possible:
56 // *(vec.begin() + 0) = ...;
57 
58 #ifndef OR_TOOLS_BASE_STRONG_VECTOR_H_
59 #define OR_TOOLS_BASE_STRONG_VECTOR_H_
60 
61 #include <stddef.h>
62 
63 #include <initializer_list>
64 #include <string>
65 #include <type_traits>
66 #include <utility>
67 #include <vector>
68 
69 #include "ortools/base/int_type.h"
70 #include "ortools/base/macros.h"
71 
72 namespace absl {
73 
74 // STL vector ------------------------------------------------------------------
75 template <typename IntType, typename T, typename Alloc = std::allocator<T> >
76 class StrongVector {
77  public:
78  typedef IntType IndexType;
79  typedef std::vector<T, Alloc> ParentType;
80 
81  typedef typename ParentType::size_type size_type;
82  typedef typename ParentType::allocator_type allocator_type;
83  typedef typename ParentType::value_type value_type;
84  typedef typename ParentType::difference_type difference_type;
85  typedef typename ParentType::reference reference;
86  typedef typename ParentType::const_reference const_reference;
87  typedef typename ParentType::pointer pointer;
88  typedef typename ParentType::const_pointer const_pointer;
89  typedef typename ParentType::iterator iterator;
90  typedef typename ParentType::const_iterator const_iterator;
91  typedef typename ParentType::reverse_iterator reverse_iterator;
92  typedef typename ParentType::const_reverse_iterator const_reverse_iterator;
93 
94  public:
96 
97  explicit StrongVector(const allocator_type& a) : v_(a) {}
98  explicit StrongVector(size_type n) : v_(n) {}
99 
101  const allocator_type& a = allocator_type())
102  : v_(n, v, a) {}
103 
105  std::initializer_list<value_type> il) // NOLINT(runtime/explicit)
106  : v_(il) {}
107 
108  template <typename InputIteratorType>
109  StrongVector(InputIteratorType first, InputIteratorType last,
110  const allocator_type& a = allocator_type())
111  : v_(first, last, a) {}
112 
113  // -- Accessors --------------------------------------------------------------
114  // This const accessor is useful in defining the comparison operators below.
115  const ParentType& get() const { return v_; }
116  // The mutable accessor is useful when using auxiliar methods relying on
117  // vector parameters such as JoinUsing(), SplitStringUsing(), etc. Methods
118  // relying solely on iterators (e.g. STLDeleteElements) should work just fine
119  // without the need for mutable_get(). NB: It should be used only in this
120  // case and thus should not be abused to index the underlying vector without
121  // the appropriate IntType.
122  ParentType* mutable_get() { return &v_; }
123 
124  // -- Modified methods -------------------------------------------------------
125  reference operator[](IndexType i) { return v_[Value(i)]; }
126  const_reference operator[](IndexType i) const { return v_[Value(i)]; }
127  reference at(IndexType i) { return v_.at(Value(i)); }
128  const_reference at(IndexType i) const { return v_.at(Value(i)); }
129 
130  // -- Pass-through methods to STL vector -------------------------------------
131  void assign(size_type n, const value_type& val) { v_.assign(n, val); }
132  template <typename InputIt>
133  void assign(InputIt f, InputIt l) {
134  v_.assign(f, l);
135  }
136  void assign(std::initializer_list<value_type> ilist) { v_.assign(ilist); }
137 
138  iterator begin() { return v_.begin(); }
139  const_iterator begin() const { return v_.begin(); }
140  iterator end() { return v_.end(); }
141  const_iterator end() const { return v_.end(); }
142  reverse_iterator rbegin() { return v_.rbegin(); }
143  const_reverse_iterator rbegin() const { return v_.rbegin(); }
144  reverse_iterator rend() { return v_.rend(); }
145  const_reverse_iterator rend() const { return v_.rend(); }
146 
147  size_type size() const { return v_.size(); }
148  size_type max_size() const { return v_.max_size(); }
149 
150  void resize(size_type new_size) { v_.resize(new_size); }
151  void resize(size_type new_size, const value_type& x) {
152  v_.resize(new_size, x);
153  }
154 
155  size_type capacity() const { return v_.capacity(); }
156  bool empty() const { return v_.empty(); }
157  void reserve(size_type n) { v_.reserve(n); }
158  void push_back(const value_type& x) { v_.push_back(x); }
159  void push_back(value_type&& x) { v_.push_back(std::move(x)); } // NOLINT
160  template <typename... Args>
161  void emplace_back(Args&&... args) {
162  v_.emplace_back(std::forward<Args>(args)...);
163  }
164  template <typename... Args>
165  iterator emplace(const_iterator pos, Args&&... args) {
166  return v_.emplace(pos, std::forward<Args>(args)...);
167  }
168  void pop_back() { v_.pop_back(); }
169  void swap(StrongVector& x) { v_.swap(x.v_); }
170  void clear() { v_.clear(); }
171 
172  reference front() { return v_.front(); }
173  const_reference front() const { return v_.front(); }
174  reference back() { return v_.back(); }
175  const_reference back() const { return v_.back(); }
176  pointer data() { return v_.data(); }
177  const_pointer data() const { return v_.data(); }
178 
179  iterator erase(const_iterator pos) { return v_.erase(pos); }
181  return v_.erase(first, last);
182  }
184  return v_.insert(pos, x);
185  }
186  iterator insert(const_iterator pos, value_type&& x) { // NOLINT
187  return v_.insert(pos, std::move(x));
188  }
190  return v_.insert(pos, n, x);
191  }
192  template <typename IIt>
193  iterator insert(const_iterator pos, IIt first, IIt last) {
194  return v_.insert(pos, first, last);
195  }
196  iterator insert(const_iterator pos, std::initializer_list<value_type> ilist) {
197  return v_.insert(pos, ilist);
198  }
199 
200  friend bool operator==(const StrongVector& x, const StrongVector& y) {
201  return x.get() == y.get();
202  }
203  friend bool operator!=(const StrongVector& x, const StrongVector& y) {
204  return x.get() != y.get();
205  }
206  friend bool operator<(const StrongVector& x, const StrongVector& y) {
207  return x.get() < y.get();
208  }
209  friend bool operator>(const StrongVector& x, const StrongVector& y) {
210  return x.get() > y.get();
211  }
212  friend bool operator<=(const StrongVector& x, const StrongVector& y) {
213  return x.get() <= y.get();
214  }
215  friend bool operator>=(const StrongVector& x, const StrongVector& y) {
216  return x.get() >= y.get();
217  }
218  friend void swap(StrongVector& x, StrongVector& y) { x.swap(y); }
219 
220  template <typename H>
221  friend H AbslHashValue(H h, const StrongVector& v) {
222  return H::combine(std::move(h), v.v_);
223  }
224 
225  private:
226  static size_type Value(IndexType i) { return i.template value<size_type>(); }
227 
228  ParentType v_;
229 
231  int_type_indexed_vector_must_have_integral_index);
232 };
233 
234 } // namespace absl
235 
236 #endif // OR_TOOLS_BASE_STRONG_VECTOR_H_
ParentType::size_type size_type
Definition: strong_vector.h:81
const_reverse_iterator rend() const
friend H AbslHashValue(H h, const StrongVector &v)
friend bool operator!=(const StrongVector &x, const StrongVector &y)
const_reference front() const
ParentType::allocator_type allocator_type
Definition: strong_vector.h:82
StrongVector(size_type n, const value_type &v, const allocator_type &a=allocator_type())
void assign(size_type n, const value_type &val)
void resize(size_type new_size, const value_type &x)
StrongVector(std::initializer_list< value_type > il)
const_iterator begin() const
iterator erase(const_iterator pos)
reference operator[](IndexType i)
reference at(IndexType i)
const_pointer data() const
ParentType::reverse_iterator reverse_iterator
Definition: strong_vector.h:91
void assign(InputIt f, InputIt l)
ParentType * mutable_get()
iterator insert(const_iterator pos, const value_type &x)
friend bool operator>=(const StrongVector &x, const StrongVector &y)
void resize(size_type new_size)
friend bool operator==(const StrongVector &x, const StrongVector &y)
void reserve(size_type n)
iterator insert(const_iterator pos, size_type n, const value_type &x)
iterator emplace(const_iterator pos, Args &&... args)
size_type size() const
iterator insert(const_iterator pos, std::initializer_list< value_type > ilist)
const_reference back() const
friend bool operator>(const StrongVector &x, const StrongVector &y)
bool empty() const
reverse_iterator rend()
StrongVector(InputIteratorType first, InputIteratorType last, const allocator_type &a=allocator_type())
friend void swap(StrongVector &x, StrongVector &y)
iterator insert(const_iterator pos, IIt first, IIt last)
ParentType::const_reverse_iterator const_reverse_iterator
Definition: strong_vector.h:92
ParentType::value_type value_type
Definition: strong_vector.h:83
const ParentType & get() const
const_reference at(IndexType i) const
void push_back(value_type &&x)
ParentType::const_reference const_reference
Definition: strong_vector.h:86
void push_back(const value_type &x)
ParentType::iterator iterator
Definition: strong_vector.h:89
size_type max_size() const
ParentType::difference_type difference_type
Definition: strong_vector.h:84
ParentType::const_iterator const_iterator
Definition: strong_vector.h:90
iterator erase(const_iterator first, const_iterator last)
void swap(StrongVector &x)
void assign(std::initializer_list< value_type > ilist)
ParentType::const_pointer const_pointer
Definition: strong_vector.h:88
StrongVector(const allocator_type &a)
Definition: strong_vector.h:97
friend bool operator<=(const StrongVector &x, const StrongVector &y)
void emplace_back(Args &&... args)
const_iterator end() const
reverse_iterator rbegin()
const_reference operator[](IndexType i) const
size_type capacity() const
friend bool operator<(const StrongVector &x, const StrongVector &y)
const_reverse_iterator rbegin() const
StrongVector(size_type n)
Definition: strong_vector.h:98
iterator insert(const_iterator pos, value_type &&x)
ParentType::reference reference
Definition: strong_vector.h:85
std::vector< T, Alloc > ParentType
Definition: strong_vector.h:79
ParentType::pointer pointer
Definition: strong_vector.h:87
int64 value
Definition: cleanup.h:22