retdec
container.h
Go to the documentation of this file.
1 
7 #ifndef RETDEC_UTILS_CONTAINER_H
8 #define RETDEC_UTILS_CONTAINER_H
9 
10 #include <algorithm>
11 #include <cassert>
12 #include <cstddef>
13 #include <iterator>
14 #include <list>
15 #include <map>
16 #include <queue>
17 #include <set>
18 #include <stack>
19 #include <string>
20 #include <unordered_set>
21 #include <vector>
22 
24 
25 namespace retdec {
26 namespace utils {
27 
30 
40 // Note to developers: For sequential containers that don't have the find()
41 // member function, like std::vector or std::list, add a "specialization" which
42 // uses std::find() from the <algorithm> header file.
43 template<class Container, typename Item>
44 bool hasItem(const Container &container, const Item &item) {
45  return container.find(item) != container.end();
46 }
47 
51 template<typename Item>
52 bool hasItem(const std::list<Item> &container, const Item &item) {
53  // std::list doesn't have the find() member function.
54  return find(container.begin(), container.end(), item) != container.end();
55 }
56 
60 template<typename Item>
61 bool hasItem(const std::vector<Item> &container, const Item &item) {
62  // std::vector doesn't have the find() member function.
63  return find(container.begin(), container.end(), item) != container.end();
64 }
65 
74 template<typename Item>
75 const Item &getNthItem(const std::vector<Item> &container, std::size_t n) {
76  assert(1 <= n && n <= container.size() && "n is out of bounds");
77 
78  return container[n - 1];
79 }
80 
89 template<typename Item>
90 const Item &getNthItem(const std::list<Item> &container, std::size_t n) {
91  assert(1 <= n && n <= container.size() && "n is out of bounds");
92 
93  auto itemIt = container.begin();
94  std::advance(itemIt, n - 1);
95  return *itemIt;
96 }
97 
108 // Note to developers: For sequential containers that don't have the find()
109 // member function, like std::vector or std::list, add a "specialization" which
110 // uses std::find() from the <algorithm> header file.
111 template<class Container, typename Item>
112 Item getValueOrDefault(const Container &container, const Item &item,
113  Item defaultValue = Item()) {
114  auto i = container.find(item);
115  return i != container.end() ? *i : defaultValue;
116 }
117 
121 template<typename Item>
122 Item getValueOrDefault(const std::list<Item> &container,
123  const Item &item, Item defaultValue = Item()) {
124  // std::list doesn't have the find() member function.
125  auto i = std::find(container.begin(), container.end(), item);
126  return i != container.end() ? *i : defaultValue;
127 }
128 
132 template<typename Item>
133 Item getValueOrDefault(const std::vector<Item> &container,
134  const Item &item, Item defaultValue = Item()) {
135  // std::vector doesn't have the find() member function.
136  auto i = std::find(container.begin(), container.end(), item);
137  return i != container.end() ? *i : defaultValue;
138 }
139 
145 template<typename Item>
146 void removeItem(std::vector<Item> &v, const Item &item) {
147  // std::vector does not provide erase() that takes an item as its argument,
148  // so we have to use the following idiom, called "erase-remove".
149  v.erase(std::remove(v.begin(), v.end(), item), v.end());
150 }
151 
157 template<class Container>
158 void clear(Container &container) {
159  container.clear();
160 }
161 
165 template<typename Item>
166 void clear(std::queue<Item> &q) {
167  // std::queue doesn't provide the clear() member function.
168  while (!q.empty()) {
169  q.pop();
170  }
171 }
172 
176 template<typename Item>
177 void clear(std::stack<Item> &s) {
178  // std::stack doesn't provide the clear() member function.
179  while (!s.empty()) {
180  s.pop();
181  }
182 }
183 
200 template<typename OutputContainer, typename InputContainer, typename Predicate>
201 OutputContainer filterTo(const InputContainer &input, const Predicate &predicate) {
203  decltype(begin) end(input.end());
204  return {begin, end};
205 }
206 
222 template<typename Container, typename Predicate>
223 Container filter(const Container &input, const Predicate &predicate) {
224  return filterTo<Container>(input, predicate);
225 }
226 
228 
231 
237 template<typename T>
238 void addToSet(const std::set<T> &from, std::set<T> &to) {
239  to.insert(from.begin(), from.end());
240 }
241 
250 template<typename T>
251 std::set<T> setUnion(const std::set<T> &s1, const std::set<T> &s2) {
252  std::set<T> result;
253  std::set_union(s1.begin(), s1.end(), s2.begin(), s2.end(),
254  std::inserter(result, result.end()));
255  return result;
256 }
257 
266 template<typename T>
267 std::set<T> setIntersection(const std::set<T> &s1, const std::set<T> &s2) {
268  std::set<T> result;
269  std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
270  std::inserter(result, result.end()));
271  return result;
272 }
273 
282 template<typename T>
283 std::set<T> setDifference(const std::set<T> &s1, const std::set<T> &s2) {
284  std::set<T> result;
285  std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
286  std::inserter(result, result.end()));
287  return result;
288 }
289 
295 template<typename T>
296 void removeFromSet(std::set<T> &from, const std::set<T> &toRemove) {
297  // The solution using std::set_difference<> is slightly faster
298  // than this manual loop:
299  //
300  // for (auto &item : toRemove) {
301  // from.erase(item);
302  // }
303  //
304  // Timings (containers with 10000000 elements):
305  //
306  // T | std::set_difference | for loop |
307  // ------------|---------------------|----------|
308  // int | 3.08s | 4.43s |
309  // std::string | 3.74s | 6.87s |
310  //
311  from = setDifference(from, toRemove);
312 }
313 
319 template<typename T>
320 bool areDisjoint(const std::set<T> &s1, const std::set<T> &s2) {
321  // s1 and s2 are disjoint iff s1 \cap s2 = \emptyset
322  // (see http://en.wikipedia.org/wiki/Disjoint_set)
323  return setIntersection(s1, s2).empty();
324 }
325 
331 template<typename T>
332 bool shareSomeItem(const std::set<T> &s1, const std::set<T> &s2) {
333  return !areDisjoint(s1, s2);
334 }
335 
337 
340 
347 template<typename Map>
348 std::set<typename Map::key_type> getKeysFromMap(const Map &m) {
349  std::set<typename Map::key_type> keys;
350  for (auto &p : m) {
351  keys.insert(p.first);
352  }
353  return keys;
354 }
355 
362 template<typename Map>
363 std::set<typename Map::mapped_type> getValuesFromMap(const Map &m) {
364  std::set<typename Map::mapped_type> keys;
365  for (auto &p : m) {
366  keys.insert(p.second);
367  }
368  return keys;
369 }
370 
378 template<typename Map>
379 bool mapHasKey(const Map &m, const typename Map::key_type &k) {
380  return m.find(k) != m.end();
381 }
382 
390 template<typename Map>
391 bool mapHasValue(const Map &m, const typename Map::mapped_type &v) {
392  for (auto &p : m) {
393  if (p.second == v) {
394  return true;
395  }
396  }
397  return false;
398 }
399 
407 template<typename Map>
408 typename Map::mapped_type mapGetValueOrDefault(
409  const Map &m,
410  const typename Map::key_type &key,
411  typename Map::mapped_type defaultValue = typename Map::mapped_type()) {
412  auto i = m.find(key);
413  return i != m.end() ? i->second : defaultValue;
414 }
415 
422 template<typename Map>
423 typename Map::mapped_type mapGetMaxValue(const Map &m) {
424  auto max = std::max_element(m.begin(), m.end(),
425  [] (const auto &p1, const auto &p2) { return p1.second < p2.second; });
426  return max != m.end() ? max->second : typename Map::mapped_type();
427 }
428 
444 template<typename Map>
445 typename Map::mapped_type &addToMap(
446  const typename Map::key_type &key,
447  const typename Map::mapped_type &value,
448  Map &m) {
449  auto i = m.find(key);
450  if (i != m.end()) {
451  i->second = value;
452  return i->second;
453  }
454  return m.emplace(key, value).first->second;
455 }
456 
469 template<typename K, typename V>
470 std::map<V, K> getMapWithSwappedKeysAndValues(const std::map<K, V> &m) {
471  std::map<V, K> result;
472  for (const auto &p : m) {
473  result.emplace(p.second, p.first);
474  }
475  return result;
476 }
477 
479 
490 
491 template <class Elem>
493  public:
495  {
496 
497  }
498  NonIterableSet(std::initializer_list<Elem> il) :
499  _data(il)
500  {
501 
502  }
503 
504  void clear() {
505  _data.clear();
506  }
507 
508  std::pair<Elem, bool> insert(const Elem& val) {
509  auto p = _data.insert(val);
510  return {*p.first, p.second};
511  }
512 
513  bool has(const Elem& val) const {
514  return _data.find(val) != _data.end();
515  }
516 
517  bool hasNot(const Elem& val) const {
518  return _data.find(val) == _data.end();
519  }
520 
521  protected:
522  std::set<Elem> _data;
523 };
524 
526 
543 
545 {
546  template <typename T>
547  std::size_t operator()(T t) const
548  {
549  return static_cast<std::size_t>(t);
550  }
551 };
552 
554 
555 } // namespace utils
556 } // namespace retdec
557 
558 #endif
An adapter of an iterator range in which some elements of the range are skipped.
Definition: filter_iterator.h:40
Definition: container.h:492
std::pair< Elem, bool > insert(const Elem &val)
Definition: container.h:508
void clear()
Definition: container.h:504
bool has(const Elem &val) const
Definition: container.h:513
NonIterableSet()
Definition: container.h:494
std::set< Elem > _data
Definition: container.h:522
NonIterableSet(std::initializer_list< Elem > il)
Definition: container.h:498
bool hasNot(const Elem &val) const
Definition: container.h:517
An adapter of an iterator range in which some elements of the range are skipped.
const Item & getNthItem(const std::vector< Item > &container, std::size_t n)
Returns the n-th item in container.
Definition: container.h:75
std::set< typename Map::mapped_type > getValuesFromMap(const Map &m)
Returns all values in the given map m.
Definition: container.h:363
bool shareSomeItem(const std::set< T > &s1, const std::set< T > &s2)
Returns true if s1 and s2 have at least one item in common.
Definition: container.h:332
Container filter(const Container &input, const Predicate &predicate)
Returns Container with items from input that satistfy predicate.
Definition: container.h:223
void removeItem(std::vector< Item > &v, const Item &item)
Removes all occurrences of the given item from the given vector.
Definition: container.h:146
bool hasItem(const Container &container, const Item &item)
Returns true if container contains item, false otherwise.
Definition: container.h:44
std::set< T > setIntersection(const std::set< T > &s1, const std::set< T > &s2)
Returns the set intersection s1 \cap s2.
Definition: container.h:267
Item getValueOrDefault(const Container &container, const Item &item, Item defaultValue=Item())
Returns the found value if container contains item, defaultValue otherwise.
Definition: container.h:112
bool mapHasValue(const Map &m, const typename Map::mapped_type &v)
Returns true if the given map m has a value v, false otherwise.
Definition: container.h:391
Map::mapped_type mapGetValueOrDefault(const Map &m, const typename Map::key_type &key, typename Map::mapped_type defaultValue=typename Map::mapped_type())
Returns the value associated to the given key in m, or defaultValue if there is no key in m.
Definition: container.h:408
Map::mapped_type & addToMap(const typename Map::key_type &key, const typename Map::mapped_type &value, Map &m)
Adds the pair <key, value> to map m.
Definition: container.h:445
void clear(Container &container)
Clears the given container.
Definition: container.h:158
std::set< T > setUnion(const std::set< T > &s1, const std::set< T > &s2)
Returns the set union s1 \cup s2.
Definition: container.h:251
std::set< T > setDifference(const std::set< T > &s1, const std::set< T > &s2)
Returns the set difference s1 \setminus s2.
Definition: container.h:283
bool areDisjoint(const std::set< T > &s1, const std::set< T > &s2)
Returns true if s1 is disjoint with s2.
Definition: container.h:320
OutputContainer filterTo(const InputContainer &input, const Predicate &predicate)
Returns OutputContainer with items from input that satistfy predicate.
Definition: container.h:201
Map::mapped_type mapGetMaxValue(const Map &m)
Returns the maximum value from m.
Definition: container.h:423
std::set< typename Map::key_type > getKeysFromMap(const Map &m)
Returns all keys in the given map m.
Definition: container.h:348
bool mapHasKey(const Map &m, const typename Map::key_type &k)
Returns true if the given map m has a key k, false otherwise.
Definition: container.h:379
void removeFromSet(std::set< T > &from, const std::set< T > &toRemove)
Removes all values that are in toRemove from from.
Definition: container.h:296
std::map< V, K > getMapWithSwappedKeysAndValues(const std::map< K, V > &m)
Returns a new map that has swapped keys and values.
Definition: container.h:470
void addToSet(const std::set< T > &from, std::set< T > &to)
Adds all values from from into to.
Definition: container.h:238
Definition: archive_wrapper.h:19
Definition: container.h:545
std::size_t operator()(T t) const
Definition: container.h:547