WPILibC++  2018.4.1-20180927001728-1207-gd5d744a
 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 <iterator>
12 #include <utility>
13 #include <vector>
14 
15 namespace wpi {
16 
17 namespace impl {
18 template <typename It>
20  public:
21  using iterator_type = std::forward_iterator_tag;
22  using value_type = typename It::value_type;
23  using difference_type = typename It::difference_type;
24  using reference = typename It::reference;
25  using pointer = typename It::pointer;
26 
27  UidVectorIterator() = default;
28  explicit UidVectorIterator(It it, It end) : m_it(it), m_end(end) {
29  // advance to first non-empty element
30  while (m_it != m_end && !*m_it) ++m_it;
31  }
32 
33  reference operator*() const noexcept { return *m_it; }
34  pointer operator->() const noexcept { return m_it.operator->(); }
35 
36  UidVectorIterator& operator++() noexcept {
37  // advance past empty elements
38  do {
39  ++m_it;
40  } while (m_it != m_end && !*m_it);
41  return *this;
42  }
43 
44  UidVectorIterator operator++(int)noexcept {
45  UidVectorIterator it = *this;
46  ++it;
47  return it;
48  }
49 
50  bool operator==(const UidVectorIterator& oth) const noexcept {
51  return m_it == oth.m_it;
52  }
53 
54  bool operator!=(const UidVectorIterator& oth) const noexcept {
55  return m_it != oth.m_it;
56  }
57 
58  private:
59  It m_it;
60  It m_end;
61 };
62 } // namespace impl
63 
64 // Vector which provides an integrated freelist for removal and reuse of
65 // individual elements.
66 // @tparam T element type; must be default-constructible and evaluate in
67 // boolean context to false when "empty"
68 // @tparam reuse_threshold how many free elements to store up before starting
69 // to recycle them
70 template <typename T, typename std::vector<T>::size_type reuse_threshold>
71 class UidVector {
72  public:
73  using value_type = T;
74  using pointer = T*;
75  using const_pointer = const T*;
76  using reference = T&;
77  using const_reference = const T&;
78  using size_type = typename std::vector<T>::size_type;
79  using difference_type = typename std::vector<T>::difference_type;
81  using const_iterator =
83 
84  bool empty() const { return m_active_count == 0; }
85  size_type size() const { return m_vector.size(); }
86  T& operator[](size_type i) { return m_vector[i]; }
87  const T& operator[](size_type i) const { return m_vector[i]; }
88 
89  // Add a new T to the vector. If there are elements on the freelist,
90  // reuses the last one; otherwise adds to the end of the vector.
91  // Returns the resulting element index.
92  template <class... Args>
93  size_type emplace_back(Args&&... args) {
94  size_type uid;
95  if (m_free.size() < reuse_threshold) {
96  uid = m_vector.size();
97  m_vector.emplace_back(std::forward<Args>(args)...);
98  } else {
99  uid = m_free.front();
100  m_free.erase(m_free.begin());
101  m_vector[uid] = T(std::forward<Args>(args)...);
102  }
103  ++m_active_count;
104  return uid;
105  }
106 
107  // Removes the identified element by replacing it with a default-constructed
108  // one. The element is added to the freelist for later reuse.
109  void erase(size_type uid) {
110  if (uid >= m_vector.size() || !m_vector[uid]) return;
111  m_free.push_back(uid);
112  m_vector[uid] = T();
113  --m_active_count;
114  }
115 
116  // Removes all elements.
117  void clear() {
118  m_vector.clear();
119  m_free.clear();
120  m_active_count = 0;
121  }
122 
123  // Iterator access
124  iterator begin() noexcept {
125  return iterator(m_vector.begin(), m_vector.end());
126  }
127  const_iterator begin() const noexcept {
128  return const_iterator(m_vector.begin(), m_vector.end());
129  }
130  const_iterator cbegin() const noexcept {
131  return const_iterator(m_vector.begin(), m_vector.end());
132  }
133  iterator end() noexcept { return iterator(m_vector.end(), m_vector.end()); }
134  const_iterator end() const noexcept {
135  return const_iterator(m_vector.end(), m_vector.end());
136  }
137  const_iterator cend() const noexcept {
138  return const_iterator(m_vector.end(), m_vector.end());
139  }
140 
141  private:
142  std::vector<T> m_vector;
143  std::vector<size_type> m_free;
144  size_type m_active_count{0};
145 };
146 
147 } // namespace wpi
148 
149 #endif // WPIUTIL_WPI_UIDVECTOR_H_
WPILib C++ utilities (wpiutil) namespace.
Definition: SmallString.h:21
Definition: UidVector.h:71
Definition: UidVector.h:19