Line data Source code
1 : // The libMesh Finite Element Library.
2 : // Copyright (C) 2002-2025 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 :
34 : /**
35 : * This \p vectormap templated class is intended to provide the
36 : * performance characteristics of a sorted std::vector with an
37 : * interface more closely resembling that of a std::map, for use in
38 : * particular when memory is tight.
39 : *
40 : * This class is limited in its applicability. The typical use case is:
41 : *
42 : * \verbatim
43 : * vectormap<KeyType,ValType> vmap;
44 : * for ( ; ;)
45 : * vmap.insert (std::make_pair(key,val));
46 : *
47 : * val1 = vmap[key1];
48 : * val2 = vmap[key2];
49 : * \endverbatim
50 : *
51 : * \note The two-phase usage. It is not advised to do intermediate
52 : * insert/lookups, as each time an insertion is done the sort is
53 : * invalidated, and must be reperformed. Additionally, during the
54 : * insertion phase, there is no accounting for duplicate keys. Each
55 : * insertion is accepted regardless of key value, and then duplicate
56 : * keys are removed later.
57 : *
58 : * \author Benjamin S. Kirk
59 : */
60 : template <typename Key, typename Tp>
61 8000 : 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 :
76 : /**
77 : * Strict weak ordering, based solely on first element in a pair.
78 : */
79 : struct FirstOrder
80 : {
81 109867451 : bool operator()(const value_type & lhs,
82 : const value_type & rhs) const
83 514832932 : { return lhs.first < rhs.first; }
84 : };
85 :
86 : /**
87 : * Equality comparison, based solely on first element in a pair.
88 : */
89 : struct FirstCompare
90 : {
91 1038528 : bool operator()(const value_type & lhs,
92 : const value_type & rhs) const
93 11593206 : { return lhs.first == rhs.first; }
94 : };
95 :
96 : public:
97 :
98 : /**
99 : * Default constructor. Initializes sorted member to false.
100 : */
101 233031 : vectormap() :
102 233031 : _sorted(false)
103 8000 : {}
104 :
105 : /**
106 : * Copy constructor.
107 : */
108 : vectormap(const vectormap<Key,Tp> & other) :
109 : std::vector<std::pair<Key, Tp>> (other),
110 : _sorted(other._sorted)
111 : {}
112 :
113 : /**
114 : * Inserts \p x into the vectormap.
115 : */
116 : void insert (const value_type & x)
117 : {
118 : _sorted = false;
119 : this->push_back(x);
120 : }
121 :
122 : /**
123 : * Inserts \p x into the vector map, using "args" to construct it
124 : * in-place.
125 : */
126 : template<class... Args>
127 1046528 : void emplace(Args&&... args)
128 : {
129 12864767 : _sorted = false;
130 12864767 : this->emplace_back(args...);
131 11818237 : }
132 :
133 : /**
134 : * Sort & unique the vectormap, preparing for use.
135 : */
136 233031 : void sort()
137 : {
138 233031 : std::sort (this->begin(), this->end(), FirstOrder());
139 :
140 233031 : this->erase (std::unique (this->begin(), this->end(), FirstCompare()), this->end());
141 :
142 233031 : _sorted = true;
143 233031 : }
144 :
145 : /**
146 : * \returns The value corresponding to \p key
147 : */
148 27345262 : const Tp & operator[](const key_type & key) const
149 : {
150 27345262 : if (!_sorted)
151 229031 : const_cast<vectormap<Key, Tp> *>(this)->sort();
152 :
153 4121137 : libmesh_assert (_sorted);
154 :
155 23224119 : value_type to_find;
156 27345262 : to_find.first = key;
157 :
158 27345262 : const_iterator lower_bound = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());
159 :
160 27345262 : libmesh_error_msg_if(lower_bound == this->end() || lower_bound->first != key,
161 : "Error in vectormap::operator[], key not found. "
162 : "If you are searching for values you aren't sure exist, try vectormap::find() instead.");
163 :
164 27345262 : return lower_bound->second;
165 : }
166 :
167 : /**
168 : * \returns An iterator corresponding to key, or the end iterator if
169 : * not found.
170 : */
171 1187 : iterator find (const key_type & key)
172 : {
173 1187 : if (!_sorted)
174 0 : this->sort();
175 :
176 251 : libmesh_assert (_sorted);
177 :
178 936 : value_type to_find;
179 1187 : to_find.first = key;
180 :
181 936 : iterator lb = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());
182 :
183 : // If we didn't find the key, return end()
184 1187 : if (lb == this->end() || lb->first != key)
185 0 : return this->end();
186 :
187 1187 : return lb;
188 : }
189 :
190 : /**
191 : * \returns An iterator corresponding to key, or the end iterator if
192 : * not found.
193 : */
194 : const_iterator find (const key_type & key) const
195 : {
196 : // This function isn't really const, we might have to sort the
197 : // underlying container before we can search in it.
198 : if (!_sorted)
199 : const_cast<vectormap<Key, Tp> *>(this)->sort();
200 :
201 : libmesh_assert (_sorted);
202 :
203 : value_type to_find;
204 : to_find.first = key;
205 :
206 : const_iterator lb = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());
207 :
208 : // If we didn't find the key, return end()
209 : if (lb == this->end() || lb->first != key)
210 : return this->end();
211 :
212 : return lb;
213 : }
214 :
215 : /**
216 : * \returns The number of occurrences of \p key.
217 : *
218 : * For a map-like object, this should be 1 or 0.
219 : */
220 : difference_type
221 20385418 : count (const key_type & key) const
222 : {
223 20385418 : if (!_sorted)
224 4000 : const_cast<vectormap<Key, Tp> *>(this)->sort();
225 :
226 5207510 : libmesh_assert (_sorted);
227 :
228 16224428 : value_type to_find;
229 20385418 : to_find.first = key;
230 :
231 20385418 : const_iterator lb = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());
232 :
233 : // If we didn't find the key, the count is 0.
234 20385418 : if (lb == this->end() || lb->first != key)
235 0 : return 0;
236 :
237 5207510 : return 1;
238 : }
239 :
240 :
241 : private:
242 :
243 : bool _sorted;
244 : };
245 :
246 : } // namespace libMesh
247 :
248 : #endif // LIBMESH_VECTORMAP_H
|
