1 // RUN: %check_clang_tidy %s performance-inefficient-algorithm %t
2 
3 namespace std {
4 template <typename T> struct less {
operator ()std::less5   bool operator()(const T &lhs, const T &rhs) { return lhs < rhs; }
6 };
7 
8 template <typename T> struct greater {
operator ()std::greater9   bool operator()(const T &lhs, const T &rhs) { return lhs > rhs; }
10 };
11 
12 struct iterator_type {};
13 
14 template <typename K, typename Cmp = less<K>> struct set {
15   typedef iterator_type iterator;
16   iterator find(const K &k);
17   unsigned count(const K &k);
18 
19   iterator begin();
20   iterator end();
21   iterator begin() const;
22   iterator end() const;
23 };
24 
25 struct other_iterator_type {};
26 
27 template <typename K, typename V, typename Cmp = less<K>> struct map {
28   typedef other_iterator_type iterator;
29   iterator find(const K &k);
30   unsigned count(const K &k);
31 
32   iterator begin();
33   iterator end();
34   iterator begin() const;
35   iterator end() const;
36 };
37 
38 template <typename K, typename V> struct multimap : map<K, V> {};
39 template <typename K> struct unordered_set : set<K> {};
40 template <typename K, typename V> struct unordered_map : map<K, V> {};
41 template <typename K> struct unordered_multiset : set<K> {};
42 template <typename K, typename V> struct unordered_multimap : map<K, V> {};
43 
44 template <typename K, typename Cmp = less<K>> struct multiset : set<K, Cmp> {};
45 
46 template <typename FwIt, typename K>
47 FwIt find(FwIt, FwIt end, const K &) { return end; }
48 
49 template <typename FwIt, typename K, typename Cmp>
50 FwIt find(FwIt, FwIt end, const K &, Cmp) { return end; }
51 
52 template <typename FwIt, typename Pred>
53 FwIt find_if(FwIt, FwIt end, Pred) { return end; }
54 
55 template <typename FwIt, typename K>
count(FwIt,FwIt,const K &)56 unsigned count(FwIt, FwIt, const K &) { return 0; }
57 
58 template <typename FwIt, typename K>
59 FwIt lower_bound(FwIt, FwIt end, const K &) { return end; }
60 
61 template <typename FwIt, typename K, typename Ord>
62 FwIt lower_bound(FwIt, FwIt end, const K &, Ord) { return end; }
63 }
64 
65 #define FIND_IN_SET(x) find(x.begin(), x.end(), 10)
66 // CHECK-FIXES: #define FIND_IN_SET(x) find(x.begin(), x.end(), 10)
67 
f(const T & t)68 template <typename T> void f(const T &t) {
69   std::set<int> s;
70   find(s.begin(), s.end(), 46);
71   // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be
72   // CHECK-FIXES: {{^  }}s.find(46);{{$}}
73 
74   find(t.begin(), t.end(), 46);
75   // CHECK-FIXES: {{^  }}find(t.begin(), t.end(), 46);{{$}}
76 }
77 
main()78 int main() {
79   std::set<int> s;
80   auto it = std::find(s.begin(), s.end(), 43);
81   // CHECK-MESSAGES: :[[@LINE-1]]:13: warning: this STL algorithm call should be replaced with a container method [performance-inefficient-algorithm]
82   // CHECK-FIXES: {{^  }}auto it = s.find(43);{{$}}
83   auto c = count(s.begin(), s.end(), 43);
84   // CHECK-MESSAGES: :[[@LINE-1]]:12: warning: this STL algorithm call should be
85   // CHECK-FIXES: {{^  }}auto c = s.count(43);{{$}}
86 
87 #define SECOND(x, y, z) y
88   SECOND(q,std::count(s.begin(), s.end(), 22),w);
89   // CHECK-MESSAGES: :[[@LINE-1]]:12: warning: this STL algorithm call should be
90   // CHECK-FIXES: {{^  }}SECOND(q,s.count(22),w);{{$}}
91 
92   it = find_if(s.begin(), s.end(), [](int) { return false; });
93 
94   std::multiset<int> ms;
95   find(ms.begin(), ms.end(), 46);
96   // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be
97   // CHECK-FIXES: {{^  }}ms.find(46);{{$}}
98 
99   const std::multiset<int> &msref = ms;
100   find(msref.begin(), msref.end(), 46);
101   // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be
102   // CHECK-FIXES: {{^  }}msref.find(46);{{$}}
103 
104   std::multiset<int> *msptr = &ms;
105   find(msptr->begin(), msptr->end(), 46);
106   // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be
107   // CHECK-FIXES: {{^  }}msptr->find(46);{{$}}
108 
109   it = std::find(s.begin(), s.end(), 43, std::greater<int>());
110   // CHECK-MESSAGES: :[[@LINE-1]]:42: warning: different comparers used in the algorithm and the container [performance-inefficient-algorithm]
111 
112   FIND_IN_SET(s);
113   // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be
114   // CHECK-FIXES: {{^  }}FIND_IN_SET(s);{{$}}
115 
116   f(s);
117 
118   std::unordered_set<int> us;
119   lower_bound(us.begin(), us.end(), 10);
120   // CHECK-FIXES: {{^  }}lower_bound(us.begin(), us.end(), 10);{{$}}
121   find(us.begin(), us.end(), 10);
122   // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be
123   // CHECK-FIXES: {{^  }}us.find(10);{{$}}
124 
125   std::unordered_multiset<int> ums;
126   find(ums.begin(), ums.end(), 10);
127   // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be
128   // CHECK-FIXES: {{^  }}ums.find(10);{{$}}
129 
130   std::map<int, int> intmap;
131   find(intmap.begin(), intmap.end(), 46);
132   // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be
133   // CHECK-FIXES: {{^  }}find(intmap.begin(), intmap.end(), 46);{{$}}
134 
135   std::multimap<int, int> intmmap;
136   find(intmmap.begin(), intmmap.end(), 46);
137   // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be
138   // CHECK-FIXES: {{^  }}find(intmmap.begin(), intmmap.end(), 46);{{$}}
139 
140   std::unordered_map<int, int> umap;
141   find(umap.begin(), umap.end(), 46);
142   // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be
143   // CHECK-FIXES: {{^  }}find(umap.begin(), umap.end(), 46);{{$}}
144 
145   std::unordered_multimap<int, int> ummap;
146   find(ummap.begin(), ummap.end(), 46);
147   // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be
148   // CHECK-FIXES: {{^  }}find(ummap.begin(), ummap.end(), 46);{{$}}
149 }
150 
151 struct Value {
152   int value;
153 };
154 
155 struct Ordering {
operator ()Ordering156   bool operator()(const Value &lhs, const Value &rhs) const {
157     return lhs.value < rhs.value;
158   }
operator ()Ordering159   bool operator()(int lhs, const Value &rhs) const { return lhs < rhs.value; }
160 };
161 
g(std::set<Value,Ordering> container,int value)162 void g(std::set<Value, Ordering> container, int value) {
163   lower_bound(container.begin(), container.end(), value, Ordering());
164   // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be
165   // CHECK-FIXES: {{^  }}lower_bound(container.begin(), container.end(), value, Ordering());{{$}}
166 }
167