C++ 容器排序技巧 |21xrx.com

C++ 容器排序技巧

2023-07-09 06:02:13 深夜i 10 0

C++ 容器排序技巧数据结构

C++ 提供了多种容器来存储和操作数据，如 vector、list、map、set 等，它们各有特点和用途。在实际开发中，我们常常需要对容器中的元素进行排序，以满足不同需求。本文将介绍一些 C++ 容器排序的技巧，帮助你轻松应对排序问题。

1. sort() 函数

sort() 函数是 C++ 标准库中的排序函数，可以对数组或容器进行排序。它使用快速排序算法实现，时间复杂度为 O(nlogn)。排序时需要传入两个迭代器，分别指向待排序区间的起始位置和终止位置。例如，对一个 vector 容器进行从小到大排序，可以使用以下代码：

#include <vector>
#include <algorithm>
std::vector<int> vec5;
std::sort(vec.begin(), vec.end());  // 排序
for (int num : vec)
  std::cout << num << " ";
// 输出：1 2 3 4 5

2. 自定义比较函数

sort() 函数默认按照升序排列，如果需要进行降序排序或按照其他规则排序，可以使用自定义比较函数。比较函数是一个可调用对象，接受两个参数，返回一个 bool 值，表示第一个参数是否小于第二个参数。以下是一个降序排列的例子：

#include <algorithm>
bool compare(int a, int b)
  return a > b;
std::vector<int> vec 1;
std::sort(vec.begin(), vec.end(), compare);  // 排序
for (int num : vec)
  std::cout << num << " ";
// 输出：5 4 3 2 1

3. stable_sort() 函数

sort() 函数排序时不保证相等元素的相对顺序，如果需要保留相等元素的相对顺序，可以使用 stable_sort() 函数。stable_sort() 函数使用归并排序算法实现，时间复杂度为 O(n log n)。以下是一个使用 stable_sort() 函数对一个 vector 容器进行排序的例子：

#include <iostream>
#include <vector>
#include <algorithm>
struct Student
  int id;
  std::string name;
  int score;
;
bool compare(const Student& a, const Student& b)
  return a.score < b.score;
int main() {
  std::vector<Student> students{ "Tom", "John", "Alice",
                  70, "Mary"};
  std::stable_sort(students.begin(), students.end(), compare);  // 按照分数升序排列
  for (const Student& s : students)
    std::cout << s.id << " " << s.name << " " << s.score << std::endl;
  
  /*
  输出：
  4 Peter 70
  2 John 80
  5 Mary 80
  1 Tom 90
  3 Alice 90
  */
  return 0;
}

4. set 和 map 的排序

set 和 map 是基于红黑树实现的容器，它们内部元素已经按照 key 值进行了排序。因此，对于 set 和 map 容器，不需要调用 sort() 函数进行排序，只需要直接遍历元素即可按照 key 值的顺序访问。以下是一个 set 遍历的例子：

#include <iostream>
#include <set>
int main() {
  std::set<int> s 4;
  for (int num : s)
    std::cout << num << " ";
  
  // 输出：1 2 3 4 5
  return 0;
}

5. 使用 Lambda 表达式

Lambda 表达式是 C++11 新增的特性，它允许定义匿名函数，并作为参数传递给另一个函数。Lambda 表达式可以轻松实现自定义比较函数，例如：

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
  std::vector<int> vec 2;
  std::sort(vec.begin(), vec.end(), [](int a, int b)
    return a > b;
  );  // 降序排列
  for (int num : vec)
    std::cout << num << " ";
  
  // 输出：5 4 3 2 1
  return 0;
}

以上就是 C++ 容器排序的几个技巧，希望能对你有所帮助。需要注意的是，排序函数会改变容器中元素的顺序，因此在使用前需要进行备份或谨慎使用。

上一篇: idea打包java可执行jar包

下一篇: C++新经典：模板与泛型编程PDF

评论区

相似文章