1 //===--- iwyu_stl_util.h - STL-like utilities for include-what-you-use ----===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 // Utilities that make it easier to work with STL.
11
12 #ifndef INCLUDE_WHAT_YOU_USE_IWYU_STL_UTIL_H_
13 #define INCLUDE_WHAT_YOU_USE_IWYU_STL_UTIL_H_
14
15 #include <algorithm> // for find
16 #include <map> // for map, multimap
17 #include <set> // for set
18 #include <vector> // for vector
19
20 namespace include_what_you_use {
21
22 using std::map;
23 using std::multimap;
24 using std::set;
25 using std::vector;
26
27 // Returns true if the associative container (e.g. set or map)
28 // contains the given key.
29 template <class AssociativeContainer>
ContainsKey(const AssociativeContainer & container,const typename AssociativeContainer::key_type & key)30 bool ContainsKey(const AssociativeContainer& container,
31 const typename AssociativeContainer::key_type& key) {
32 return container.find(key) != container.end();
33 }
34
35 // Returns true if the container contains the given value.
36 template <class Container>
ContainsValue(const Container & container,const typename Container::value_type & value)37 bool ContainsValue(const Container& container,
38 const typename Container::value_type& value) {
39 return (std::find(container.begin(), container.end(), value)
40 != container.end());
41 }
42
43 // For maps, we also let you check if the key exists with the given value.
44 template <class Container, typename K, typename V>
ContainsKeyValue(const Container & container,const K & key,const V & value)45 bool ContainsKeyValue(const Container& container,
46 const K& key, const V& value) {
47 for (typename Container::const_iterator it = container.lower_bound(key),
48 end = container.upper_bound(key); it != end; ++it) {
49 if (it->second == value)
50 return true;
51 }
52 return false;
53 }
54
55 // Returns true if the associative container contains any key in the
56 // given set.
57 template <class AssociativeContainer>
ContainsAnyKey(const AssociativeContainer & container,const set<typename AssociativeContainer::key_type> & keys)58 bool ContainsAnyKey(
59 const AssociativeContainer& container,
60 const set<typename AssociativeContainer::key_type>& keys) {
61 for (const auto& key : keys) {
62 if (ContainsKey(container, key))
63 return true;
64 }
65 return false;
66 }
67
68 // Returns a_map[key] if key is in a_map; otherwise returns default_value.
69 template <class Map>
GetOrDefault(const Map & a_map,const typename Map::key_type & key,const typename Map::mapped_type & default_value)70 const typename Map::mapped_type& GetOrDefault(
71 const Map& a_map, const typename Map::key_type& key,
72 const typename Map::mapped_type& default_value) {
73 if (ContainsKey(a_map, key))
74 return a_map.find(key)->second;
75 return default_value;
76 }
77
78 // Returns a pointer to (*a_map)[key] if key is in *a_map; otherwise
79 // returns nullptr.
80 template <typename K, typename V>
FindInMap(const map<K,V> * a_map,const K & key)81 const V* FindInMap(const map<K, V>* a_map, const K& key) {
82 const typename map<K, V>::const_iterator it = a_map->find(key);
83 return it == a_map->end() ? nullptr : &it->second;
84 }
85 template <typename K, typename V>
FindInMap(map<K,V> * a_map,const K & key)86 V* FindInMap(map<K, V>* a_map, const K& key) {
87 const typename map<K, V>::iterator it = a_map->find(key);
88 return it == a_map->end() ? nullptr : &it->second;
89 }
90
91 // Returns all values associated with the given key in the multimap.
92 template <typename K, typename V>
FindInMultiMap(const multimap<K,V> & a_multimap,const K & key)93 vector<V> FindInMultiMap(const multimap<K, V>& a_multimap, const K& key) {
94 vector<V> retval;
95 for (typename multimap<K, V>::const_iterator it = a_multimap.lower_bound(key),
96 end = a_multimap.upper_bound(key); it != end; ++it) {
97 retval.push_back(it->second);
98 }
99 return retval;
100 }
101
102 // Removes all elements in source from target.
103 template <class SourceContainer, class TargetContainer>
RemoveAllFrom(const SourceContainer & source,TargetContainer * target)104 void RemoveAllFrom(const SourceContainer& source, TargetContainer* target) {
105 for (typename SourceContainer::const_iterator it = source.begin();
106 it != source.end(); ++it) {
107 target->erase(*it);
108 }
109 }
110
111 // Inserts all elements from source into target.
112 template <class SourceContainer, class TargetContainer>
InsertAllInto(const SourceContainer & source,TargetContainer * target)113 void InsertAllInto(const SourceContainer& source, TargetContainer* target) {
114 target->insert(source.begin(), source.end());
115 }
116
117 // Appends all elements from source to the end of target. The target
118 // type must support inserting a range at the end, which probably
119 // means it's a vector.
120 template <class TargetContainer, class SourceContainer>
Extend(TargetContainer * target,const SourceContainer & source)121 void Extend(TargetContainer* target, const SourceContainer& source) {
122 target->insert(target->end(), source.begin(), source.end());
123 }
124
125 // Returns the union of the two given sets.
126 template <typename T>
Union(const set<T> & lhs,const set<T> & rhs)127 set<T> Union(const set<T>& lhs, const set<T>& rhs) {
128 set<T> retval(lhs);
129 InsertAllInto(rhs, &retval);
130 return retval;
131 }
132
133 // Returns a vector v with all duplicates removed, but order otherwise
134 // maintained.
135 template <typename T>
GetUniqueEntries(const vector<T> & v)136 vector<T> GetUniqueEntries(const vector<T>& v) {
137 set<T> seen;
138 vector<T> retval;
139 for (typename vector<T>::const_iterator it = v.begin(); it != v.end(); ++it) {
140 if (!ContainsKey(seen, *it)) {
141 retval.push_back(*it);
142 seen.insert(*it);
143 }
144 }
145 return retval;
146 }
147
148 } // namespace include_what_you_use
149
150 #endif // INCLUDE_WHAT_YOU_USE_IWYU_STL_UTIL_H_
151