OR-Tools  8.2
vector_map.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 // Vector with map from element to index in the vector.
15 
16 #ifndef OR_TOOLS_UTIL_VECTOR_MAP_H_
17 #define OR_TOOLS_UTIL_VECTOR_MAP_H_
18 
19 #include <vector>
20 
21 #include "absl/container/flat_hash_map.h"
22 #include "ortools/base/map_util.h"
23 
24 namespace operations_research {
25 
26 // This class stores a vector of distinct elements, as well as a map
27 // from elements to index to find the index in the vector.
28 // This is useful to store mapping between objects and indices.
29 template <class T>
30 class VectorMap {
31  public:
32  // Adds an element if not already present, and returns its index in
33  // the vector-map.
34  int Add(const T& element) {
35  int current_index = Index(element);
36  if (current_index != -1) {
37  return current_index;
38  }
39  const int index = list_.size();
40  CHECK_EQ(index, map_.size());
41  list_.push_back(element);
42  map_[element] = index;
43  return index;
44  }
45  // TODO(user): Use ArraySlice.
46 
47  // Adds all elements of the vector.
48  void Add(const std::vector<T>& elements) {
49  for (int i = 0; i < elements.size(); ++i) {
50  Add(elements[i]);
51  }
52  }
53 
54  // Will return the index of the element if present, or die otherwise.
55  int IndexOrDie(const T& element) const {
56  return gtl::FindOrDie(map_, element);
57  }
58 
59  // Returns -1 if the element is not in the vector, or its unique
60  // index if it is.
61  int Index(const T& element) const {
62  return gtl::FindWithDefault(map_, element, -1);
63  }
64  // TODO(user): explore a int-type version.
65 
66  // Returns whether the element has already been added to the vector-map.
67  bool Contains(const T& element) const {
68  return gtl::ContainsKey(map_, element);
69  }
70 
71  // Returns the element at position index.
72  const T& Element(int index) const {
73  CHECK_GE(index, 0);
74  CHECK_LT(index, list_.size());
75  return list_[index];
76  }
77 
78  const T& operator[](int index) const { return Element(index); }
79 
80  // Returns the number of distinct elements added to the vector-map.
81  int size() const { return list_.size(); }
82 
83  // Clears all the elements added to the vector-map.
84  void clear() {
85  list_.clear();
86  map_.clear();
87  }
88 
89  // Returns a read-only access to the vector of elements.
90  const std::vector<T>& list() const { return list_; }
91 
92  // Standard STL container boilerplate.
93  typedef T value_type;
94  typedef const T* pointer;
95  typedef const T& reference;
96  typedef const T& const_reference;
97  typedef size_t size_type;
98  typedef ptrdiff_t difference_type;
99  static const size_type npos;
100  typedef const T* const_iterator;
101  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
102  const_iterator begin() const { return list_.data(); }
103  const_iterator end() const { return list_.data() + list_.size(); }
105  return const_reverse_iterator(list_.data() + list_.size());
106  }
108  return const_reverse_iterator(list_.data());
109  }
110 
111  private:
112  std::vector<T> list_;
113  absl::flat_hash_map<T, int> map_;
114 };
115 
116 } // namespace operations_research
117 #endif // OR_TOOLS_UTIL_VECTOR_MAP_H_
#define CHECK_LT(val1, val2)
Definition: base/logging.h:700
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
const_reverse_iterator rend() const
Definition: vector_map.h:107
int Add(const T &element)
Definition: vector_map.h:34
const_iterator begin() const
Definition: vector_map.h:102
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: vector_map.h:101
bool Contains(const T &element) const
Definition: vector_map.h:67
const std::vector< T > & list() const
Definition: vector_map.h:90
const T & Element(int index) const
Definition: vector_map.h:72
int IndexOrDie(const T &element) const
Definition: vector_map.h:55
void Add(const std::vector< T > &elements)
Definition: vector_map.h:48
const T & operator[](int index) const
Definition: vector_map.h:78
static const size_type npos
Definition: vector_map.h:99
const_iterator end() const
Definition: vector_map.h:103
const_reverse_iterator rbegin() const
Definition: vector_map.h:104
int Index(const T &element) const
Definition: vector_map.h:61
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
const Collection::value_type::second_type & FindWithDefault(const Collection &collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
Definition: map_util.h:26
const Collection::value_type::second_type & FindOrDie(const Collection &collection, const typename Collection::value_type::first_type &key)
Definition: map_util.h:176
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int index
Definition: pack.cc:508