[C++知识库]c++ stl常用算法总结

std::sort

• 将容器元素进行排序, 会改变容器顺序, 默认从小到大排序

  void sort( RandomIt first, RandomIt last );
  

• comp: returns true if the first argument is less than the second.

  struct {
       bool operator()(int a, int b) const { return a < b; }
   } customLess;
  

• 算法复杂度: nlogn

std::partial_sort

• 将容器中的[first, middle)元素进行排序, 会改变容器顺序, 默认从小到大排序

  void partial_sort( RandomIt first, RandomIt middle, RandomIt last );
  

• comp: returns true if the first argument is less than the second.

• 算法复杂度: Approximately (last-first)log(middle-first) applications of cmp.

std::nth_element

• 找到容器中假设从小到大排序的第n个元素, 会改变容器顺序, 一般用于找中位数

  void nth_element( RandomIt first, RandomIt nth, RandomIt last );
  

• comp: returns true if the first argument is less than the second.

• 算法复杂度: Linear in std::distance(first, last) on average.

std::partition

• 将容器中满足条件的放在一边, 不满足条件的放在另一边, 返回两边中间另一边开始前的指针, 会改变容器顺序

• UnaryPredicate: unary predicate which returns true if the element should be ordered before other elements.

  auto it = std::partition(v.begin(), v.end(), [](int i){return i % 2 == 0;});
  

• 算法复杂度: n

std::lower_bound

• 找到容器中第一个大于等于一个值的元素, 不会改变容器顺序, 要求容器有序
  Returns an iterator pointing to the first element in the range [first, last) that does not satisfy element < value (or comp(element, value)),
  (i.e. greater or equal to), or last if no such element is found.

  ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
  

• comp: binary predicate which returns true if the first argument is less than the second.

  auto prc_info = std::lower_bound(prices.begin(), prices.end(), to_find,
          [](const PriceInfo& info, double value)
          {
              return info.price < value;
          });
  

• 算法复杂度: logn

std::upper_bound

• 找到容器中第一个大于一个值的元素, 不会改变容器顺序, 要求容器有序
  Returns an iterator pointing to the first element in the range [first, last) such that value < element
  (or comp(value, element)) is true (i.e. strictly greater), or last if no such element is found.

  ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );
  

• comp: binary predicate which returns true if the first argument is less than the second.

  auto prc_info = std::upper_bound(prices.begin(), prices.end(), to_find,
            [](double value, const PriceInfo& info)
            {
                return value < info.price;
            });
  

• 算法复杂度: logn

std::equal_range

• Returns a range containing all elements equivalent to value in the range [first, last). 要求容器有序

  Possible implementation:

  template<class ForwardIt, class T>
  std::pair<ForwardIt, ForwardIt>
      equal_range(ForwardIt first, ForwardIt last, const T& value) {
      return std::make_pair(std::lower_bound(first, last, value),
                            std::upper_bound(first, last, value));
  }
  

• comp: binary predicate which returns true if the first argument is less than the second.

• 算法复杂度: 2 * logn

std::binary_search

• 二分法查找element equivalent to value, 要求容器有序, 不会改变容器顺序
  Possible implementation:

  template<class ForwardIt, class T>
  bool binary_search(ForwardIt first, ForwardIt last, const T& value)
  {
    first = std::lower_bound(first, last, value);
    return (!(first == last) && !(value < *first));
  }
  

• comp: binary predicate which returns true if the first argument is less than the second.

• 算法复杂度: logn

std::transform

• 将一个容器中的元素施加某种算法后, 并作用于另一个容器上

• unary_op/binary_op:

  std::transform(s.cbegin(), s.cend(),
                  s.begin(), // write to the same location
                  [](unsigned char c) { return std::toupper(c); });
  
  std::transform(s.cbegin(), s.cend(), std::back_inserter(ordinals),
   [](unsigned char c) { return c; });
  
  std::transform(ordinals.cbegin(), ordinals.cend(), ordinals.cbegin(),
                  ordinals.begin(), std::plus<>{});
  

• 算法复杂度: n

std::unique

• 去除器中相邻的两个equivalent elements中的一个, 通常与erase联合使用, 完成真正意义上的删除, 不要求容器有序

  left_boundary.erase(std::unique(left_boundary.begin(), left_boundary.end()),
                    left_boundary.end());
  

• BinaryPredicate: binary predicate which returns true if the elements should be treated as equal.

• 算法复杂度: n

std::remove/std::remove_if

• 去除容器中满足特定条件的元素, 通常与erase联合使用, 完成真正意义上的删除, 不要求容器有序

  auto noSpaceEnd = std::remove(str1.begin(), str1.end(), ' ');
  str1.erase(noSpaceEnd, str1.end());
  

• UnaryPredicate: unary predicate which returns true if the element should be removed.

  str2.erase(std::remove_if(str2.begin(),
                             str2.end(),
                             [](unsigned char x){return std::isspace(x);}),
              str2.end());
  

• 算法复杂度: n

std::for_each

• 对一个容器循环调用某个函数

  std::for_each(nums.begin(), nums.end(), [](int &n){ n++; });
  

  因为c++11引入了for(auto var : vars)基于范围的for循环语法, 使得for_each的语义表达相形见绌了许多, 大多数情况可以不用for_each

• 算法复杂度: n

std::min_element/std::max_element

• 找到容器中最大/最小元素, 默认使用<比较

• comp: comparison function object (i.e. an object that satisfies the requirements of Compare) which returns true if the first argument is less than the second.

  result = std::max_element(v.begin(), v.end(), [](int a, int b) {
       return std::abs(a) < std::abs(b);
   });
  

• 算法复杂度: n