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
70#include "ortools/base/macros.h"
71
72namespace absl {
73
74// STL vector ------------------------------------------------------------------
75template <typename IntType, typename T, typename Alloc = std::allocator<T> >
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
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,
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 }
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_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
const ParentType & get() 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