167 lines · cpp
1// RUN: %check_clang_tidy %s performance-inefficient-algorithm %t2 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(), s.end(), 46);71 // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be72 // 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(), 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 be85 // CHECK-FIXES: auto c = s.count(43);86 87#define SECOND(x, y, z) y88 SECOND(q,std::count(s.begin(), s.end(), 22),w);89 // CHECK-MESSAGES: :[[@LINE-1]]:12: warning: this STL algorithm call should be90 // 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 be97 // 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 be102 // 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 be107 // 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 be114 // 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 be123 // 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 be128 // 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 be133 // 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 be138 // 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 be143 // 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 be148 // 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(), container.end(), value, Ordering());164 // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be165 // CHECK-FIXES: lower_bound(container.begin(), container.end(), value, Ordering());166}167