Empirical
ra_set.h
Go to the documentation of this file.
1 
11 #ifndef EMP_RA_SET_H
12 #define EMP_RA_SET_H
13 
14 #include <map>
15 
16 #include "../base/vector.h"
17 
18 namespace emp {
19 
25 
26  template <typename T>
27  class ra_set {
28  private:
29  std::map<T,size_t> id_map;
30  emp::vector<T> vals;
31 
32  public:
33  ra_set() : id_map(), vals() { }
34  ra_set(const ra_set &) = default;
35  ra_set(ra_set &&) = default;
36  ra_set<T> & operator=(const ra_set &) = default;
37  ra_set<T> & operator=(ra_set &&) = default;
38 
39  using value_type = T;
40 
42  bool empty() const { return id_map.size() == 0; }
43 
45  size_t size() const { return id_map.size(); }
46 
48  const T & operator[](size_t pos) const { return vals[pos]; }
49 
51  void clear() { id_map.clear(); vals.resize(0); }
52 
54  void insert(const T & v) {
55  if (count(v)) return; // Already in set.
56  const size_t pos = vals.size();
57  vals.push_back(v);
58  id_map[v] = pos;
59  }
60 
62  bool erase(const T & v) {
63  if (!count(v)) return false; // Not in set.
64 
65  // Find out where v is in id_map and clear it.
66  const size_t pos = id_map[v];
67  id_map.erase(v);
68 
69  // Move the former last value to the now-empty spot.
70  const size_t last_pos = vals.size() - 1;
71  if (pos != last_pos) {
72  vals[pos] = vals[last_pos];
73  id_map[vals[pos]] = pos;
74  }
75  vals.resize(last_pos);
76  return true;
77  }
78 
80  size_t count(const T & v) const { return id_map.count(v); }
81  };
82 
83 }
84 
85 #endif
ra_set()
Definition: ra_set.h:33
size_t size() const
How many elements are in this set?
Definition: ra_set.h:45
T value_type
Definition: ra_set.h:39
bool erase(const T &v)
Erase a specific value from the container.
Definition: ra_set.h:62
void push_back(PB_Ts &&...args)
Definition: vector.h:189
void insert(const T &v)
Insert a new value into container.
Definition: ra_set.h:54
size_t size() const
Definition: vector.h:151
void clear()
Remove all values from this container.
Definition: ra_set.h:51
Definition: ra_set.h:27
size_t count(const T &v) const
Count the number of times a particular value in in the container (0 or 1).
Definition: ra_set.h:80
void resize(size_t new_size)
Definition: vector.h:161
If we are in emscripten, make sure to include the header.
Definition: array.h:37
bool empty() const
Are there any values in this ra_set?
Definition: ra_set.h:42
const T & operator[](size_t pos) const
Index into the ra_set, similar to a vector.
Definition: ra_set.h:48
ra_set< T > & operator=(const ra_set &)=default