1// RUN: %check_clang_tidy %s performance-inefficient-algorithm %t
2
3namespace std {
4template <typename T> struct less {
5 bool operator()(const T &lhs, const T &rhs) { return lhs < rhs; }
6};
7
8template <typename T> struct greater {
9 bool operator()(const T &lhs, const T &rhs) { return lhs > rhs; }
10};
11
12struct iterator_type {};
13
14template <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
25struct other_iterator_type {};
26
27template <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
38template <typename K, typename V> struct multimap : map<K, V> {};
39template <typename K> struct unordered_set : set<K> {};
40template <typename K, typename V> struct unordered_map : map<K, V> {};
41template <typename K> struct unordered_multiset : set<K> {};
42template <typename K, typename V> struct unordered_multimap : map<K, V> {};
43
44template <typename K, typename Cmp = less<K>> struct multiset : set<K, Cmp> {};
45
46template <typename FwIt, typename K>
47FwIt find(FwIt, FwIt end, const K &) { return end; }
48
49template <typename FwIt, typename K, typename Cmp>
50FwIt find(FwIt, FwIt end, const K &, Cmp) { return end; }
51
52template <typename FwIt, typename Pred>
53FwIt find_if(FwIt, FwIt end, Pred) { return end; }
54
55template <typename FwIt, typename K>
56unsigned count(FwIt, FwIt, const K &) { return 0; }
57
58template <typename FwIt, typename K>
59FwIt lower_bound(FwIt, FwIt end, const K &) { return end; }
60
61template <typename FwIt, typename K, typename Ord>
62FwIt 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
68template <typename T> void f(const T &t) {
69 std::set<int> s;
70 find(s.begin(), end: 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
78int main() {
79 std::set<int> s;
80 auto it = std::find(s.begin(), end: 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(), end: s.end(), [](int) { return false; });
93
94 std::multiset<int> ms;
95 find(ms.begin(), end: 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(), end: 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(), end: 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(), end: 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(t: s);
117
118 std::unordered_set<int> us;
119 lower_bound(us.begin(), end: us.end(), 10);
120 // CHECK-FIXES: {{^ }}lower_bound(us.begin(), us.end(), 10);{{$}}
121 find(us.begin(), end: 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(), end: 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(), end: 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(), end: 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(), end: 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(), end: 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
151struct Value {
152 int value;
153};
154
155struct Ordering {
156 bool operator()(const Value &lhs, const Value &rhs) const {
157 return lhs.value < rhs.value;
158 }
159 bool operator()(int lhs, const Value &rhs) const { return lhs < rhs.value; }
160};
161
162void g(std::set<Value, Ordering> container, int value) {
163 lower_bound(container.begin(), end: 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

source code of clang-tools-extra/test/clang-tidy/checkers/performance/inefficient-algorithm.cpp