libMesh
vectormap.h
Go to the documentation of this file.
1 // The libMesh Finite Element Library.
2 // Copyright (C) 2002-2017 Benjamin S. Kirk, John W. Peterson, Roy H. Stogner
3 
4 // This library is free software; you can redistribute it and/or
5 // modify it under the terms of the GNU Lesser General Public
6 // License as published by the Free Software Foundation; either
7 // version 2.1 of the License, or (at your option) any later version.
8 
9 // This library is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 // Lesser General Public License for more details.
13 
14 // You should have received a copy of the GNU Lesser General Public
15 // License along with this library; if not, write to the Free Software
16 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 
18 
19 
20 #ifndef LIBMESH_VECTORMAP_H
21 #define LIBMESH_VECTORMAP_H
22 
23 // C++ Includes -----------------------------------
24 #include <vector>
25 #include <algorithm>
26 
27 // libMesh includes
28 #include "libmesh/libmesh_common.h"
29 
30 
31 namespace libMesh
32 {
33 
60 template <typename Key, typename Tp>
61 class vectormap : public std::vector<std::pair<Key, Tp>>
62 {
63 
64 public:
65 
66  typedef Key key_type;
67  typedef Tp mapped_type;
68  typedef std::pair<Key, Tp> value_type;
69  typedef std::vector<value_type> vector_type;
70  typedef typename vector_type::difference_type difference_type;
71  typedef typename vector_type::iterator iterator;
72  typedef typename vector_type::const_iterator const_iterator;
73 
74 private:
75 
79  struct FirstOrder
80  {
81  bool operator()(const value_type & lhs,
82  const value_type & rhs) const
83  { return lhs.first < rhs.first; }
84  };
85 
89  struct FirstCompare
90  {
91  bool operator()(const value_type & lhs,
92  const value_type & rhs) const
93  { return lhs.first == rhs.first; }
94  };
95 
96 public:
97 
102  _sorted(false)
103  {}
104 
108  vectormap(const vectormap<Key,Tp> & other) :
109  std::vector<std::pair<Key, Tp>> (other),
110  _sorted(other._sorted)
111  {}
112 
116  void insert (const value_type & x)
117  {
118  _sorted = false;
119  this->push_back(x);
120  }
121 
125  void sort()
126  {
127  std::sort (this->begin(), this->end(), FirstOrder());
128 
129  this->erase (std::unique (this->begin(), this->end(), FirstCompare()), this->end());
130 
131  _sorted = true;
132  }
133 
137  const Tp & operator[](const key_type & key) const
138  {
139  if (!_sorted)
140  const_cast<vectormap<Key, Tp> *>(this)->sort();
141 
143 
144  value_type to_find;
145  to_find.first = key;
146 
147  const_iterator lower_bound = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());
148 
149  if (lower_bound == this->end() || lower_bound->first != key)
150  libmesh_error_msg("Error in vectormap::operator[], key not found. "
151  "If you are searching for values you aren't sure exist, try vectormap::find() instead.");
152 
153  return lower_bound->second;
154  }
155 
160  iterator find (const key_type & key)
161  {
162  if (!_sorted)
163  this->sort();
164 
166 
167  value_type to_find;
168  to_find.first = key;
169 
170  iterator lb = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());
171 
172  // If we didn't find the key, return end()
173  if (lb == this->end() || lb->first != key)
174  return this->end();
175 
176  return lb;
177  }
178 
183  const_iterator find (const key_type & key) const
184  {
185  // This function isn't really const, we might have to sort the
186  // underlying container before we can search in it.
187  if (!_sorted)
188  const_cast<vectormap<Key, Tp> *>(this)->sort();
189 
191 
192  value_type to_find;
193  to_find.first = key;
194 
195  const_iterator lb = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());
196 
197  // If we didn't find the key, return end()
198  if (lb == this->end() || lb->first != key)
199  return this->end();
200 
201  return lb;
202  }
203 
209  difference_type
210  count (const key_type & key) const
211  {
212  if (!_sorted)
213  const_cast<vectormap<Key, Tp> *>(this)->sort();
214 
216 
217  value_type to_find;
218  to_find.first = key;
219 
220  const_iterator lb = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());
221 
222  // If we didn't find the key, the count is 0.
223  if (lb == this->end() || lb->first != key)
224  return 0;
225 
226  return 1;
227  }
228 
229 
230 private:
231 
232  bool _sorted;
233 };
234 
235 } // namespace libMesh
236 
237 #endif // LIBMESH_VECTORMAP_H
iterator find(const key_type &key)
Definition: vectormap.h:160
difference_type count(const key_type &key) const
Definition: vectormap.h:210
std::vector< value_type > vector_type
Definition: vectormap.h:69
bool operator()(const value_type &lhs, const value_type &rhs) const
Definition: vectormap.h:81
std::pair< Key, Tp > value_type
Definition: vectormap.h:68
vector_type::const_iterator const_iterator
Definition: vectormap.h:72
IterBase * end
Also have a polymorphic pointer to the end object, this prevents iterating past the end...
The libMesh namespace provides an interface to certain functionality in the library.
Strict weak ordering, based solely on first element in a pair.
Definition: vectormap.h:79
vectormap()
Default constructor.
Definition: vectormap.h:101
libmesh_assert(j)
PetscErrorCode Vec x
void sort()
Sort & unique the vectormap, preparing for use.
Definition: vectormap.h:125
void insert(const value_type &x)
Inserts x into the vectormap.
Definition: vectormap.h:116
vectormap(const vectormap< Key, Tp > &other)
Copy constructor.
Definition: vectormap.h:108
vector_type::difference_type difference_type
Definition: vectormap.h:70
bool operator()(const value_type &lhs, const value_type &rhs) const
Definition: vectormap.h:91
vector_type::iterator iterator
Definition: vectormap.h:71
Equality comparison, based solely on first element in a pair.
Definition: vectormap.h:89
This vectormap templated class is intended to provide the performance characteristics of a sorted std...
Definition: vectormap.h:61
const Tp & operator[](const key_type &key) const
Definition: vectormap.h:137
const_iterator find(const key_type &key) const
Definition: vectormap.h:183