WPILibC++  unspecified
UidVector.h
1 /*----------------------------------------------------------------------------*/
2 /* Copyright (c) FIRST 2017. 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_SUPPORT_UIDVECTOR_H_
9 #define WPIUTIL_SUPPORT_UIDVECTOR_H_
10 
11 #include <vector>
12 
13 namespace wpi {
14 
15 // Vector which provides an integrated freelist for removal and reuse of
16 // individual elements.
17 // @tparam T element type; must be default-constructible and evaluate in
18 // boolean context to false when "empty"
19 // @tparam reuse_threshold how many free elements to store up before starting
20 // to recycle them
21 template <typename T, typename std::vector<T>::size_type reuse_threshold>
22 class UidVector {
23  public:
24  typedef typename std::vector<T>::size_type size_type;
25 
26  bool empty() const { return m_active_count == 0; }
27  size_type size() const { return m_vector.size(); }
28  T& operator[](size_type i) { return m_vector[i]; }
29  const T& operator[](size_type i) const { return m_vector[i]; }
30 
31  // Add a new T to the vector. If there are elements on the freelist,
32  // reuses the last one; otherwise adds to the end of the vector.
33  // Returns the resulting element index.
34  template <class... Args>
35  size_type emplace_back(Args&&... args) {
36  size_type uid;
37  if (m_free.size() < reuse_threshold) {
38  uid = m_vector.size();
39  m_vector.emplace_back(std::forward<Args>(args)...);
40  } else {
41  uid = m_free.front();
42  m_free.erase(m_free.begin());
43  m_vector[uid] = T(std::forward<Args>(args)...);
44  }
45  ++m_active_count;
46  return uid;
47  }
48 
49  // Removes the identified element by replacing it with a default-constructed
50  // one. The element is added to the freelist for later reuse.
51  void erase(size_type uid) {
52  if (uid >= m_vector.size() || !m_vector[uid]) return;
53  m_free.push_back(uid);
54  m_vector[uid] = T();
55  --m_active_count;
56  }
57 
58  private:
59  std::vector<T> m_vector;
60  std::vector<size_type> m_free;
61  size_type m_active_count{0};
62 };
63 
64 } // namespace wpi
65 
66 #endif // WPIUTIL_SUPPORT_UIDVECTOR_H_
Definition: SocketError.cpp:18
Definition: UidVector.h:22