Vcsn  2.3a
Be Rational
sparse-map.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <boost/optional.hpp>
4 
5 #include <vector>
6 
7 namespace vcsn
8 {
14  template <typename Key, typename Value>
15  class sparse_map
16  {
18  static_assert(std::is_unsigned<Key>::value,
19  "sparse-set: requires unsigned indexes");
20 
21  public:
22  sparse_map(size_t max_size = 0)
23  : dense_{}
24  , sparse_{}
25  {
26  set_max_size(max_size);
27  }
28 
29  void set_max_size(size_t max_size)
30  {
31  sparse_.resize(max_size);
32  }
33 
34  template <typename K, typename V>
35  bool emplace(K&& k, V&& v)
36  {
37  return insert(std::make_pair(k, v));
38  }
39 
43  // already present in the set.
44  bool insert(const std::pair<Key, Value>& p)
45  {
46  if (has(p.first))
47  return false;
48  else
49  {
50  if (sparse_.size() <= p.first)
51  sparse_.resize(p.first + 1);
52  if (curr_ < dense_.size())
53  dense_[curr_] = p;
54  else
55  dense_.push_back(p);
56  sparse_[p.first] = curr_;
57  ++curr_;
58  return true;
59  }
60  }
61 
62  bool has(Key k) const
63  {
64  return (k < sparse_.capacity()
65  && sparse_[k] < curr_
66  && dense_[sparse_[k]].first == k);
67  }
68 
72  Value& operator[](Key k)
73  {
74  if (!has(k))
75  emplace(k, Value());
76  return dense_[sparse_[k]].second;
77  }
78 
82  void erase(Key k)
83  {
84  if (has(k))
85  {
86  Key last = dense_[curr_ - 1].first;
87  dense_[sparse_[k]].first = last;
88  sparse_[last] = sparse_[k];
89  curr_--;
90  }
91  }
92 
94  void clear()
95  {
96  curr_ = 0;
97  }
98 
99  auto begin()
100  {
101  return dense_.begin();
102  }
103 
104  auto end()
105  {
106  return dense_.begin() + curr_;
107  }
108 
109  auto begin() const
110  {
111  return dense_.begin();
112  }
113 
114  auto end() const
115  {
116  return dense_.begin() + curr_;
117  }
118 
119  private:
120 
121  std::vector<std::pair<Key, Value>> dense_;
122  std::vector<Key> sparse_;
123  Key curr_ = 0;
124  };
125 
126  template <typename Key, typename Value>
127  bool
128  has(const sparse_map<Key, Value>& s, Key k)
129  {
130  return s.has(k);
131  }
132 }
std::vector< std::pair< Key, Value > > dense_
Definition: sparse-map.hh:121
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
Definition: setalpha.hh:25
Value & operator[](Key k)
Access an element.
Definition: sparse-map.hh:72
return v
Definition: multiply.hh:361
Definition: a-star.hh:8
bool emplace(K &&k, V &&v)
Definition: sparse-map.hh:35
#define V(S)
Display S and its value.
Definition: show.hh:10
auto end() const
Definition: sparse-map.hh:114
sparse_map(size_t max_size=0)
The Keys correspond to indexes so they have to be unsigned.
Definition: sparse-map.hh:22
void erase(Key k)
Erase an element.
Definition: sparse-map.hh:82
Sparse Map implementation.
Definition: sparse-map.hh:15
bool insert(const std::pair< Key, Value > &p)
Insert new value.
Definition: sparse-map.hh:44
void clear()
Flush all elements from the set.
Definition: sparse-map.hh:94
void set_max_size(size_t max_size)
Definition: sparse-map.hh:29
bool has(Key k) const
Definition: sparse-map.hh:62
std::vector< Key > sparse_
Definition: sparse-map.hh:122
auto begin() const
Definition: sparse-map.hh:109