1#ifndef DBALLE_CORE_SMALLSET_H
2#define DBALLE_CORE_SMALLSET_H
10template<
typename T>
inline const T& smallset_default_get_value(
const T& val) {
return val; }
15template<
typename Item,
typename Value=Item, const Value& (*get_value)(const Item&)=smallset_default_get_value>
18 mutable std::vector<Item> items;
19 mutable size_t dirty = 0;
21 typedef typename std::vector<Item>::const_iterator const_iterator;
22 typedef typename std::vector<Item>::iterator iterator;
23 typedef typename std::vector<Item>::const_reverse_iterator const_reverse_iterator;
24 typedef typename std::vector<Item>::reverse_iterator reverse_iterator;
26 iterator begin() {
return items.begin(); }
27 iterator end() {
return items.end(); }
28 const_iterator begin()
const {
return items.begin(); }
29 const_iterator end()
const {
return items.end(); }
30 reverse_iterator rbegin() {
return items.rbegin(); }
31 reverse_iterator rend() {
return items.rend(); }
32 const_reverse_iterator rbegin()
const {
return items.rbegin(); }
33 const_reverse_iterator rend()
const {
return items.rend(); }
34 size_t size()
const {
return items.size(); }
35 bool empty()
const {
return items.empty(); }
37 bool operator==(
const SmallSet& o)
const
39 if (dirty) rearrange_dirty();
40 if (o.dirty) o.rearrange_dirty();
41 return items == o.items;
44 bool operator!=(
const SmallSet& o)
const
46 if (dirty) rearrange_dirty();
47 if (o.dirty) o.rearrange_dirty();
48 return items == o.items;
57 int binary_search(
const Value& value)
const
60 begin = -1, end = items.size();
61 while (end - begin > 1)
63 int cur = (end + begin) / 2;
64 if (value < get_value(items[cur]))
69 if (begin == -1 || get_value(items[begin]) != value)
75 const_iterator find(
const Value& value)
const
77 if (items.empty())
return end();
82 for (
auto it = std::begin(items); it != std::end(items); ++it)
83 if (get_value(*it) == value)
92 std::sort(items.begin(), items.end(), [](
const Item& a,
const Item& b) {
93 return get_value(a) < get_value(b);
102 int pos = binary_search(value);
106 return items.begin() + pos;
109 iterator find(
const Value& value)
111 if (items.empty())
return end();
114 if (items.size() < 6)
116 for (
auto it = std::begin(items); it != std::end(items); ++it)
117 if (get_value(*it) == value)
126 std::sort(items.begin(), items.end(), [](
const Item& a,
const Item& b) {
127 return get_value(a) < get_value(b);
136 int pos = binary_search(value);
140 return items.begin() + pos;
143 Item& add(
const Item& item)
146 items.emplace_back(item);
152 void rearrange_dirty()
const
155 for (
size_t i = items.size() - dirty; i < items.size(); ++i)
156 for (
size_t j = i; j > 0 && get_value(items[j]) < get_value(items[j - 1]); --j)
157 std::swap(items[j], items[j - 1]);
163template<
typename Value>
180 void add(
const Value& val)
182 auto i = this->find(val);
183 if (i != this->end())
return;
187 bool has(
const Value& val)
const
189 return this->find(val) != this->end();
194template<
typename Value>
197 typedef typename SmallUniqueValueSet<Value>::iterator iterator;
198 typedef typename SmallUniqueValueSet<Value>::const_iterator const_iterator;
199 typedef typename SmallUniqueValueSet<Value>::reverse_iterator reverse_iterator;
200 typedef typename SmallUniqueValueSet<Value>::const_reverse_iterator const_reverse_iterator;
211 if (this->dirty) this->rearrange_dirty();
214 const_iterator begin()
const
216 if (this->dirty) this->rearrange_dirty();
219 reverse_iterator rbegin()
221 if (this->dirty) this->rearrange_dirty();
224 const_reverse_iterator rbegin()
const
226 if (this->dirty) this->rearrange_dirty();
230 void add(
const Value& val)
232 auto i = this->find(val);
233 if (i != this->end())
return;
237 bool has(
const Value& val)
const
239 return this->find(val) != this->end();
Container for a wreport::Var pointer.
Definition: value.h:19
Set structure optimized for a small number of items.
Definition: smallset.h:17
Definition: smallset.h:165
Definition: smallset.h:196