Doxygen
linkedmap.h
浏览该文件的文档.
1 /******************************************************************************
2  *
3  * Copyright (C) 1997-2020 by Dimitri van Heesch.
4  *
5  * Permission to use, copy, modify, and distribute this software and its
6  * documentation under the terms of the GNU General Public License is hereby
7  * granted. No representations are made about the suitability of this software
8  * for any purpose. It is provided "as is" without express or implied warranty.
9  * See the GNU General Public License for more details.
10  *
11  * Documents produced by Doxygen are derivative works derived from the
12  * input used in their production; they are not affected by this license.
13  *
14  */
15 
16 #ifndef LINKEDMAP_H
17 #define LINKEDMAP_H
18 
19 #include <unordered_map>
20 #include <vector>
21 #include <memory>
22 #include <string>
23 #include <algorithm>
24 #include <cctype>
25 
26 #include "qcstring.h"
27 
28 //! @brief Container class representing a vector of objects with keys.
29 //! @details Objects can efficiently be looked up given the key.
30 //! Objects are owned by the container.
31 //! When adding objects the order of addition is kept, and used while iterating.
32 template<class T, class Hash = std::hash<std::string>,
33  class KeyEqual = std::equal_to<std::string>,
34  class Map = std::unordered_map<std::string,T*,Hash,KeyEqual > >
35 class LinkedMap
36 {
37  public:
38  using Ptr = std::unique_ptr<T>;
39  using Vec = std::vector<Ptr>;
40  using iterator = typename Vec::iterator;
41  using const_iterator = typename Vec::const_iterator;
42  using reverse_iterator = typename Vec::reverse_iterator;
43  using const_reverse_iterator = typename Vec::const_reverse_iterator;
44 
45  //! Find an object given the key.
46  //! Returns a pointer to the element if found or nullptr if it is not found.
47  const T *find(const std::string &key) const
48  {
49  auto it = m_lookup.find(key);
50  return it!=m_lookup.end() ? it->second : nullptr;
51  }
52 
53  //! Find an object given the key.
54  //! Returns a pointer to the element if found or nullptr if it is not found.
55  const T *find(const QCString &key) const
56  {
57  auto it = m_lookup.find(key.str());
58  return it!=m_lookup.end() ? it->second : nullptr;
59  }
60 
61  //! Find an object given the key.
62  //! Returns a pointer to the element if found or nullptr if it is not found.
63  const T *find(const char *key) const
64  {
65  return find(std::string(key ? key : ""));
66  }
67 
68  //! A non-const wrapper for find() const
69  T* find(const char *key)
70  {
71  return const_cast<T*>(static_cast<const LinkedMap&>(*this).find(key));
72  }
73 
74  //! A non-const wrapper for find() const
75  T* find(const QCString &key)
76  {
77  return const_cast<T*>(static_cast<const LinkedMap&>(*this).find(key));
78  }
79 
80  //! A non-const wrapper for find() const
81  T* find(const std::string &key)
82  {
83  return const_cast<T*>(static_cast<const LinkedMap&>(*this).find(key));
84  }
85 
86  //! Adds a new object to the ordered vector if it was not added already.
87  //! Return a non-owning pointer to the newly added object, or to the existing object if
88  //! it was already inserted before under the given key.
89  template<class...Args>
90  T *add(const char *k, Args&&... args)
91  {
92  T *result = find(k);
93  if (result==nullptr)
94  {
95  std::string key(k ? k : "");
96  Ptr ptr = std::make_unique<T>(QCString(k),std::forward<Args>(args)...);
97  result = ptr.get();
98  m_lookup.insert({key,result});
99  m_entries.push_back(std::move(ptr));
100  }
101  return result;
102  }
103 
104  template<class...Args>
105  T *add(const QCString &k, Args&&... args)
106  {
107  std::string key = k.str();
108  T *result = find(key);
109  if (result==nullptr)
110  {
111  Ptr ptr = std::make_unique<T>(k,std::forward<Args>(args)...);
112  result = ptr.get();
113  m_lookup.insert({key,result});
114  m_entries.push_back(std::move(ptr));
115  }
116  return result;
117  }
118 
119  //! Adds an existing object to the ordered vector (unless another object was already
120  //! added under the same key). Ownership is transferred.
121  //! Return a non-owning pointer to the newly added object, or to the existing object if
122  //! it was already inserted before under the given key.
123  T *add(const char *k, Ptr &&ptr)
124  {
125  T *result = find(k);
126  if (result==nullptr)
127  {
128  std::string key(k ? k : "");
129  result = ptr.get();
130  m_lookup.insert({key,result});
131  m_entries.push_back(std::move(ptr));
132  }
133  return result;
134  }
135 
136  T *add(const QCString &k, Ptr &&ptr)
137  {
138  std::string key = k.str();
139  T *result = find(key);
140  if (result==nullptr)
141  {
142  result = ptr.get();
143  m_lookup.insert({key,result});
144  m_entries.push_back(std::move(ptr));
145  }
146  return result;
147  }
148 
149  //! Prepends a new object to the ordered vector if it was not added already.
150  //! Return a non-owning pointer to the newly added object, or to the existing object if
151  //! it was already inserted before under the given key.
152  template<class...Args>
153  T *prepend(const char *k, Args&&... args)
154  {
155  T *result = find(k);
156  if (result==nullptr)
157  {
158  std::string key(k ? k : "");
159  Ptr ptr = std::make_unique<T>(key.c_str(),std::forward<Args>(args)...);
160  result = ptr.get();
161  m_lookup.insert({key,result});
162  m_entries.push_front(std::move(ptr));
163  }
164  return result;
165  }
166 
167  template<class...Args>
168  T *prepend(const QCString &key, Args&&... args)
169  {
170  T *result = find(key);
171  if (result==nullptr)
172  {
173  Ptr ptr = std::make_unique<T>(key,std::forward<Args>(args)...);
174  result = ptr.get();
175  m_lookup.insert({key.str(),result});
176  m_entries.push_front(std::move(ptr));
177  }
178  return result;
179  }
180 
181  //! Removes an object from the container and deletes it.
182  //! Returns true if the object was deleted or false it is was not found.
183  bool del(const QCString &key)
184  {
185  auto it = m_lookup.find(key.str());
186  if (it!=m_lookup.end())
187  {
188  auto vecit = std::find_if(m_entries.begin(),m_entries.end(),[obj=it->second](auto &el) { return el.get()==obj; });
189  if (vecit!=m_entries.end()) // should always be true
190  {
191  m_entries.erase(vecit);
192  m_lookup.erase(it);
193  return true;
194  }
195  }
196  return false;
197  }
198 
199  Ptr &operator[](size_t pos) { return m_entries[pos]; }
200  const Ptr &operator[](size_t pos) const { return m_entries[pos]; }
201  iterator begin() { return m_entries.begin(); }
202  iterator end() { return m_entries.end(); }
203  const_iterator begin() const { return m_entries.cbegin(); }
204  const_iterator end() const { return m_entries.cend(); }
205  reverse_iterator rbegin() { return m_entries.rbegin(); }
206  reverse_iterator rend() { return m_entries.rend(); }
207  const_reverse_iterator rbegin() const { return m_entries.crbegin(); }
208  const_reverse_iterator rend() const { return m_entries.crend(); }
209  bool empty() const { return m_entries.empty(); }
210  size_t size() const { return m_entries.size(); }
211 
212  void clear()
213  {
214  m_entries.clear();
215  m_lookup.clear();
216  }
217 
218  private:
219 
220  Map m_lookup;
222 };
223 
224 //! @brief Container class representing a vector of objects with keys.
225 //! @details Objects can be efficiently be looked up given the key.
226 //! Objects are \e not owned by the container, the container will only hold references.
227 //! When adding objects the order of addition is kept, and used while iterating.
228 template<class T, class Hash = std::hash<std::string>,
229  class KeyEqual = std::equal_to<std::string>,
230  class Map = std::unordered_map<std::string,T*,Hash,KeyEqual > >
232 {
233  public:
234  using Ptr = T*;
235  using Vec = std::vector<Ptr>;
236  using iterator = typename Vec::iterator;
237  using const_iterator = typename Vec::const_iterator;
238  using reverse_iterator = typename Vec::reverse_iterator;
239  using const_reverse_iterator = typename Vec::const_reverse_iterator;
240 
241  //! find an object given the key.
242  //! Returns a pointer to the object if found or nullptr if it is not found.
243  const T *find(const std::string &key) const
244  {
245  auto it = m_lookup.find(key);
246  return it!=m_lookup.end() ? it->second : nullptr;
247  }
248 
249  //! find an object given the key.
250  //! Returns a pointer to the object if found or nullptr if it is not found.
251  const T *find(const QCString &key) const
252  {
253  auto it = m_lookup.find(key.str());
254  return it!=m_lookup.end() ? it->second : nullptr;
255  }
256 
257  //! find an object given the key.
258  //! Returns a pointer to the object if found or nullptr if it is not found.
259  const T *find(const char *key) const
260  {
261  return find(std::string(key ? key : ""));
262  }
263 
264  //! non-const wrapper for find() const
265  T* find(const char *key)
266  {
267  return const_cast<T*>(static_cast<const LinkedRefMap&>(*this).find(key));
268  }
269 
270  T* find(const QCString &key)
271  {
272  return const_cast<T*>(static_cast<const LinkedRefMap&>(*this).find(key));
273  }
274 
275  //! non-const wrapper for find() const
276  T* find(const std::string &key)
277  {
278  return const_cast<T*>(static_cast<const LinkedRefMap&>(*this).find(key));
279  }
280 
281  //! Adds an object reference to the ordered vector if it was not added already.
282  //! Return true if the reference was added, and false if an object with the same key
283  //! was already added before
284  bool add(const char *k, T* obj)
285  {
286  if (find(k)==nullptr) // new element
287  {
288  std::string key(k ? k : "");
289  m_lookup.insert({key,obj});
290  m_entries.push_back(obj);
291  return true;
292  }
293  else // already existing, don't add
294  {
295  return false;
296  }
297  }
298 
299  bool add(const QCString &k, T* obj)
300  {
301  std::string key = k.str();
302  if (find(key)==nullptr) // new element
303  {
304  m_lookup.insert({key,obj});
305  m_entries.push_back(obj);
306  return true;
307  }
308  else // already existing, don't add
309  {
310  return false;
311  }
312  }
313 
314  //! Prepends an object reference to the ordered vector if it was not added already.
315  //! Return true if the reference was added, and false if an object with the same key
316  //! was already added before
317  bool prepend(const char *k, T* obj)
318  {
319  if (find(k)==nullptr) // new element
320  {
321  std::string key(k ? k : "");
322  m_lookup.insert({key,obj});
323  m_entries.insert(m_entries.begin(),obj);
324  return true;
325  }
326  else // already existing, don't add
327  {
328  return false;
329  }
330  }
331 
332  bool prepend(const QCString &key, T* obj)
333  {
334  if (find(key)==nullptr) // new element
335  {
336  m_lookup.insert({key.str(),obj});
337  m_entries.insert(m_entries.begin(),obj);
338  return true;
339  }
340  else // already existing, don't add
341  {
342  return false;
343  }
344  }
345 
346  //! Removes an object from the container and deletes it.
347  //! Returns true if the object was deleted or false it is was not found.
348  bool del(const QCString &key)
349  {
350  auto it = m_lookup.find(key.str());
351  if (it!=m_lookup.end())
352  {
353  auto vecit = std::find_if(m_entries.begin(),m_entries.end(),[obj=it->second](auto &el) { return el.get()==obj; });
354  if (vecit!=m_entries.end()) // should always be true
355  {
356  m_entries.erase(vecit);
357  m_lookup.erase(it);
358  return true;
359  }
360  }
361  return false;
362  }
363 
364  Ptr &operator[](size_t pos) { return m_entries[pos]; }
365  const Ptr &operator[](size_t pos) const { return m_entries[pos]; }
366  iterator begin() { return m_entries.begin(); }
367  iterator end() { return m_entries.end(); }
368  const_iterator begin() const { return m_entries.cbegin(); }
369  const_iterator end() const { return m_entries.cend(); }
370  reverse_iterator rbegin() { return m_entries.rbegin(); }
371  reverse_iterator rend() { return m_entries.rend(); }
372  const_reverse_iterator rbegin() const { return m_entries.crbegin(); }
373  const_reverse_iterator rend() const { return m_entries.crend(); }
374  bool empty() const { return m_entries.empty(); }
375  size_t size() const { return m_entries.size(); }
376 
377  void clear()
378  {
379  m_entries.clear();
380  m_lookup.clear();
381  }
382 
383  private:
384  Map m_lookup;
386 };
387 
388 
389 #endif
LinkedRefMap::add
bool add(const char *k, T *obj)
Adds an object reference to the ordered vector if it was not added already.
Definition: linkedmap.h:284
LinkedRefMap::empty
bool empty() const
Definition: linkedmap.h:374
LinkedRefMap
Container class representing a vector of objects with keys.
Definition: linkedmap.h:231
LinkedRefMap::find
const T * find(const QCString &key) const
find an object given the key.
Definition: linkedmap.h:251
LinkedRefMap::operator[]
Ptr & operator[](size_t pos)
Definition: linkedmap.h:364
ConceptDef
Definition: conceptdef.h:22
LinkedRefMap::find
T * find(const QCString &key)
Definition: linkedmap.h:270
LinkedMap::const_iterator
typename Vec::const_iterator const_iterator
Definition: linkedmap.h:54
LinkedMap::const_reverse_iterator
typename Vec::const_reverse_iterator const_reverse_iterator
Definition: linkedmap.h:56
LinkedMap::add
T * add(const char *k, Ptr &&ptr)
Adds an existing object to the ordered vector (unless another object was already added under the same...
Definition: linkedmap.h:136
LinkedMap::empty
bool empty() const
Definition: linkedmap.h:222
LinkedRefMap::add
bool add(const QCString &k, T *obj)
Definition: linkedmap.h:299
LinkedMap::del
bool del(const QCString &key)
Removes an object from the container and deletes it.
Definition: linkedmap.h:196
LinkedMap::add
T * add(const char *k, Args &&... args)
Adds a new object to the ordered vector if it was not added already.
Definition: linkedmap.h:103
LinkedRefMap::rbegin
reverse_iterator rbegin()
Definition: linkedmap.h:370
QCString::str
std::string str() const
Definition: qcstring.h:442
LinkedMap::Ptr
std::unique_ptr< T > Ptr
Definition: linkedmap.h:51
LinkedRefMap::del
bool del(const QCString &key)
Removes an object from the container and deletes it.
Definition: linkedmap.h:348
LinkedMap::reverse_iterator
typename Vec::reverse_iterator reverse_iterator
Definition: linkedmap.h:55
LinkedMap::operator[]
Ptr & operator[](size_t pos)
Definition: linkedmap.h:212
qcstring.h
LinkedRefMap::find
const T * find(const char *key) const
find an object given the key.
Definition: linkedmap.h:259
LinkedRefMap::prepend
bool prepend(const char *k, T *obj)
Prepends an object reference to the ordered vector if it was not added already.
Definition: linkedmap.h:317
LinkedMap::begin
iterator begin()
Definition: linkedmap.h:214
LinkedRefMap::find
T * find(const std::string &key)
non-const wrapper for find() const
Definition: linkedmap.h:276
LinkedRefMap< const ConceptDef >::const_reverse_iterator
typename Vec::const_reverse_iterator const_reverse_iterator
Definition: linkedmap.h:239
LinkedMap::iterator
typename Vec::iterator iterator
Definition: linkedmap.h:53
LinkedRefMap::operator[]
const Ptr & operator[](size_t pos) const
Definition: linkedmap.h:365
LinkedRefMap::end
const_iterator end() const
Definition: linkedmap.h:369
LinkedRefMap::m_lookup
Map m_lookup
Definition: linkedmap.h:384
LinkedMap::Vec
std::vector< Ptr > Vec
Definition: linkedmap.h:52
LinkedRefMap< const ConceptDef >::Vec
std::vector< Ptr > Vec
Definition: linkedmap.h:235
LinkedRefMap::begin
const_iterator begin() const
Definition: linkedmap.h:368
LinkedMap::rbegin
reverse_iterator rbegin()
Definition: linkedmap.h:218
LinkedMap::find
const T * find(const std::string &key) const
Find an object given the key.
Definition: linkedmap.h:60
LinkedRefMap::begin
iterator begin()
Definition: linkedmap.h:366
LinkedMap::rend
reverse_iterator rend()
Definition: linkedmap.h:219
LinkedMap::prepend
T * prepend(const char *k, Args &&... args)
Prepends a new object to the ordered vector if it was not added already.
Definition: linkedmap.h:166
LinkedMap::end
iterator end()
Definition: linkedmap.h:215
LinkedMap::m_entries
Vec m_entries
Definition: linkedmap.h:234
LinkedRefMap::clear
void clear()
Definition: linkedmap.h:377
LinkedRefMap::end
iterator end()
Definition: linkedmap.h:367
LinkedRefMap::rbegin
const_reverse_iterator rbegin() const
Definition: linkedmap.h:372
LinkedRefMap::m_entries
Vec m_entries
Definition: linkedmap.h:385
LinkedRefMap::prepend
bool prepend(const QCString &key, T *obj)
Definition: linkedmap.h:332
LinkedMap
Container class representing a vector of objects with keys.
Definition: linkedmap.h:35
LinkedRefMap::find
T * find(const char *key)
non-const wrapper for find() const
Definition: linkedmap.h:265
LinkedRefMap< const ConceptDef >::const_iterator
typename Vec::const_iterator const_iterator
Definition: linkedmap.h:237
LinkedRefMap::rend
const_reverse_iterator rend() const
Definition: linkedmap.h:373
LinkedRefMap::find
const T * find(const std::string &key) const
find an object given the key.
Definition: linkedmap.h:243
LinkedRefMap< const ConceptDef >::iterator
typename Vec::iterator iterator
Definition: linkedmap.h:236
LinkedMap::clear
void clear()
Definition: linkedmap.h:225
LinkedRefMap< const ConceptDef >::reverse_iterator
typename Vec::reverse_iterator reverse_iterator
Definition: linkedmap.h:238
LinkedMap::m_lookup
Map m_lookup
Definition: linkedmap.h:233
LinkedRefMap::size
size_t size() const
Definition: linkedmap.h:375
LinkedRefMap::rend
reverse_iterator rend()
Definition: linkedmap.h:371
LinkedMap::size
size_t size() const
Definition: linkedmap.h:223
QCString
This is an alternative implementation of QCString.
Definition: qcstring.h:108