WPILibC++  2018.4.1-20180729184725-1146-g6db5f80
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Modules Pages
UidVector.h
1 /*----------------------------------------------------------------------------*/
2 /* Copyright (c) 2017-2018 FIRST. All Rights Reserved. */
3 /* Open Source Software - may be modified and shared by FRC teams. The code */
4 /* must be accompanied by the FIRST BSD license file in the root directory of */
5 /* the project. */
6 /*----------------------------------------------------------------------------*/
7 
8 #ifndef WPIUTIL_WPI_UIDVECTOR_H_
9 #define WPIUTIL_WPI_UIDVECTOR_H_
10 
11 #include <utility>
12 #include <vector>
13 
14 namespace wpi {
15 
16 // Vector which provides an integrated freelist for removal and reuse of
17 // individual elements.
18 // @tparam T element type; must be default-constructible and evaluate in
19 // boolean context to false when "empty"
20 // @tparam reuse_threshold how many free elements to store up before starting
21 // to recycle them
22 template <typename T, typename std::vector<T>::size_type reuse_threshold>
23 class UidVector {
24  public:
25  typedef typename std::vector<T>::size_type size_type;
26 
27  bool empty() const { return m_active_count == 0; }
28  size_type size() const { return m_vector.size(); }
29  T& operator[](size_type i) { return m_vector[i]; }
30  const T& operator[](size_type i) const { return m_vector[i]; }
31 
32  // Add a new T to the vector. If there are elements on the freelist,
33  // reuses the last one; otherwise adds to the end of the vector.
34  // Returns the resulting element index.
35  template <class... Args>
36  size_type emplace_back(Args&&... args) {
37  size_type uid;
38  if (m_free.size() < reuse_threshold) {
39  uid = m_vector.size();
40  m_vector.emplace_back(std::forward<Args>(args)...);
41  } else {
42  uid = m_free.front();
43  m_free.erase(m_free.begin());
44  m_vector[uid] = T(std::forward<Args>(args)...);
45  }
46  ++m_active_count;
47  return uid;
48  }
49 
50  // Removes the identified element by replacing it with a default-constructed
51  // one. The element is added to the freelist for later reuse.
52  void erase(size_type uid) {
53  if (uid >= m_vector.size() || !m_vector[uid]) return;
54  m_free.push_back(uid);
55  m_vector[uid] = T();
56  --m_active_count;
57  }
58 
59  private:
60  std::vector<T> m_vector;
61  std::vector<size_type> m_free;
62  size_type m_active_count{0};
63 };
64 
65 } // namespace wpi
66 
67 #endif // WPIUTIL_WPI_UIDVECTOR_H_
WPILib C++ utilities (wpiutil) namespace.
Definition: SmallString.h:21
Definition: UidVector.h:23