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"
23
24namespace 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.
29template <class T>
30class 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 std::vector< T > & list() const
Definition: vector_map.h:90
const_reverse_iterator rend() const
Definition: vector_map.h:107
const T & Element(int index) const
Definition: vector_map.h:72
const T & operator[](int index) const
Definition: vector_map.h:78
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
int IndexOrDie(const T &element) const
Definition: vector_map.h:55
void Add(const std::vector< T > &elements)
Definition: vector_map.h:48
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
const Collection::value_type::second_type & FindOrDie(const Collection &collection, const typename Collection::value_type::first_type &key)
Definition: map_util.h:176
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
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int index
Definition: pack.cc:508