| 1 |
// RUN: %check_clang_tidy %s performance-inefficient-algorithm %t |
| 2 |
|
| 3 |
namespace std { |
| 4 |
template <typename T> struct less { |
| 5 |
bool operator()(const T &lhs, const T &rhs) { return lhs < rhs; } |
| 6 |
}; |
| 7 |
|
| 8 |
template <typename T> struct greater { |
| 9 |
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> |
| 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 |
|
| 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 |
|
| 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 { |
| 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 |
|
| 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 |
} |