跳到主要内容

C++ 11新容器和算法

C++11标准为C++语言带来了丰富的新特性,其中包括若干新增的容器和算法,大大提升了C++的编程效率和代码表达能力。本文将介绍这些新容器和算法,帮助初学者理解并掌握如何在实际编程中运用它们。

新增容器

C++11在原有STL容器的基础上,引入了几个非常实用的新容器类型,包括无序容器、数组容器和元组。

std::array

std::array 是一个固定大小的数组,它提供了STL容器的接口,同时保持了C风格数组的性能特性。

cpp
#include <iostream>
#include <array>

int main() {
// 声明一个包含5个int的array
std::array<int, 5> arr = {1, 2, 3, 4, 5};

// 使用at访问元素(带边界检查)
std::cout << "arr.at(2) = " << arr.at(2) << std::endl;

// 使用[]访问元素(无边界检查)
std::cout << "arr[4] = " << arr[4] << std::endl;

// 获取数组大小
std::cout << "Size: " << arr.size() << std::endl;

// 迭代所有元素
std::cout << "Elements: ";
for (const auto& elem : arr) {
std::cout << elem << " ";
}
std::cout << std::endl;

return 0;
}

输出:

arr.at(2) = 3
arr[4] = 5
Size: 5
Elements: 1 2 3 4 5
提示

与C风格数组相比,std::array提供了更安全且更功能丰富的接口,同时不损失性能。它知道自己的大小,可以使用STL算法,并且提供了边界检查方法。

std::forward_list

std::forward_list 是一个单向链表,比 std::list(双向链表)占用更少的内存,在只需要从前向后遍历的情况下性能更好。

cpp
#include <iostream>
#include <forward_list>

int main() {
std::forward_list<int> flist = {1, 2, 3, 4, 5};

// 在开头添加元素
flist.push_front(0);

// 在特定位置之后插入元素
auto it = flist.begin();
flist.insert_after(it, 10);

// 打印所有元素
std::cout << "Elements: ";
for (const auto& elem : flist) {
std::cout << elem << " ";
}
std::cout << std::endl;

return 0;
}

输出:

Elements: 0 10 1 2 3 4 5

无序关联容器

C++11引入了四种基于哈希表实现的无序关联容器:

  • std::unordered_map:键值对的无序集合,每个键对应一个值
  • std::unordered_multimap:允许重复键的unordered_map
  • std::unordered_set:唯一键的无序集合
  • std::unordered_multiset:允许重复键的unordered_set

这些容器相比于有序版本(std::mapstd::set等),在查找、插入和删除操作上通常有更好的平均性能(常数时间复杂度)。

cpp
#include <iostream>
#include <unordered_map>
#include <string>

int main() {
// 创建一个无序映射表,键是字符串,值是整数
std::unordered_map<std::string, int> scores;

// 插入元素
scores["Alice"] = 95;
scores["Bob"] = 89;
scores["Charlie"] = 92;

// 检查元素是否存在
if (scores.find("Bob") != scores.end()) {
std::cout << "Bob's score: " << scores["Bob"] << std::endl;
}

// 遍历所有键值对
std::cout << "All scores:\n";
for (const auto& pair : scores) {
std::cout << pair.first << ": " << pair.second << std::endl;
}

return 0;
}

输出(因为是无序的,实际输出顺序可能不同):

Bob's score: 89
All scores:
Charlie: 92
Bob: 89
Alice: 95
备注

无序容器基于哈希表实现,所以元素顺序不固定,也不会按照键排序。如果需要排序的集合,应使用std::mapstd::set

std::tuple

std::tuple是一个固定大小的异构集合,可以存储不同类型的对象。它是std::pair的泛化版本,可以保存任意数量的元素。

cpp
#include <iostream>
#include <tuple>
#include <string>

int main() {
// 创建一个包含三个不同类型元素的元组
std::tuple<std::string, int, double> person("Alice", 25, 1.68);

// 使用std::get<>()访问元素
std::cout << "Name: " << std::get<0>(person) << std::endl;
std::cout << "Age: " << std::get<1>(person) << std::endl;
std::cout << "Height: " << std::get<2>(person) << " m" << std::endl;

// 使用std::tie解包元组
std::string name;
int age;
double height;
std::tie(name, age, height) = person;

std::cout << "After unpacking - Name: " << name << std::endl;

return 0;
}

输出:

Name: Alice
Age: 25
Height: 1.68 m
After unpacking - Name: Alice

新增和改进的算法

std::begin 和 std::end

C++11引入了全局函数std::beginstd::end,使得无论是使用STL容器还是原生数组,我们都可以用统一的方式获取开始和结束迭代器。

cpp
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
// STL容器
std::vector<int> vec = {5, 2, 8, 1, 9};

// 原生数组
int arr[] = {5, 2, 8, 1, 9};

// 使用std::begin和std::end排序
std::sort(std::begin(vec), std::end(vec));
std::sort(std::begin(arr), std::end(arr));

// 输出排序后的vector
std::cout << "Sorted vector: ";
for (auto& elem : vec) {
std::cout << elem << " ";
}
std::cout << std::endl;

// 输出排序后的数组
std::cout << "Sorted array: ";
for (auto& elem : arr) {
std::cout << elem << " ";
}
std::cout << std::endl;

return 0;
}

输出:

Sorted vector: 1 2 5 8 9 
Sorted array: 1 2 5 8 9

std::all_of, std::any_of, std::none_of

这三个算法让我们可以轻松地检查容器中元素是否满足特定条件。

cpp
#include <iostream>
#include <vector>
#include <algorithm>

bool isEven(int n) {
return n % 2 == 0;
}

int main() {
std::vector<int> vec1 = {2, 4, 6, 8, 10};
std::vector<int> vec2 = {1, 2, 3, 4, 5};
std::vector<int> vec3 = {1, 3, 5, 7, 9};

// 检查是否所有元素都是偶数
bool allEven = std::all_of(vec1.begin(), vec1.end(), isEven);
std::cout << "All elements in vec1 are even: " << (allEven ? "Yes" : "No") << std::endl;

// 检查是否至少有一个元素是偶数
bool anyEven = std::any_of(vec2.begin(), vec2.end(), isEven);
std::cout << "At least one element in vec2 is even: " << (anyEven ? "Yes" : "No") << std::endl;

// 检查是否没有元素是偶数
bool noneEven = std::none_of(vec3.begin(), vec3.end(), isEven);
std::cout << "None of the elements in vec3 is even: " << (noneEven ? "Yes" : "No") << std::endl;

return 0;
}

输出:

All elements in vec1 are even: Yes
At least one element in vec2 is even: Yes
None of the elements in vec3 is even: Yes

std::find_if_not

std::find_if_not算法寻找第一个不满足指定条件的元素。

cpp
#include <iostream>
#include <vector>
#include <algorithm>

bool isPositive(int n) {
return n > 0;
}

int main() {
std::vector<int> vec = {5, 3, 8, -2, 4};

// 查找第一个非正数
auto it = std::find_if_not(vec.begin(), vec.end(), isPositive);

if (it != vec.end()) {
std::cout << "First non-positive number: " << *it
<< " at position " << (it - vec.begin()) << std::endl;
} else {
std::cout << "All numbers are positive" << std::endl;
}

return 0;
}

输出:

First non-positive number: -2 at position 3

std::iota

std::iota 算法用递增的值填充范围。

cpp
#include <iostream>
#include <vector>
#include <numeric> // 包含std::iota

int main() {
std::vector<int> vec(10);

// 用从1开始递增的值填充容器
std::iota(vec.begin(), vec.end(), 1);

// 输出结果
std::cout << "Vector filled with std::iota: ";
for (const auto& elem : vec) {
std::cout << elem << " ";
}
std::cout << std::endl;

return 0;
}

输出:

Vector filled with std::iota: 1 2 3 4 5 6 7 8 9 10 

std::minmax 和 std::minmax_element

这两个算法分别用于获取两个值的最小和最大值,以及范围内的最小和最大元素。

cpp
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
// 使用std::minmax获取两个值的最大和最小值
auto result1 = std::minmax(5, 10);
std::cout << "Min: " << result1.first << ", Max: " << result1.second << std::endl;

// 使用std::minmax_element获取范围内最大和最小的元素
std::vector<int> vec = {3, 9, 1, 7, 5};
auto result2 = std::minmax_element(vec.begin(), vec.end());

std::cout << "Min element: " << *result2.first
<< " at position " << (result2.first - vec.begin()) << std::endl;
std::cout << "Max element: " << *result2.second
<< " at position " << (result2.second - vec.begin()) << std::endl;

return 0;
}

输出:

Min: 5, Max: 10
Min element: 1 at position 2
Max element: 9 at position 1

实际应用案例

应用案例1:使用无序容器构建简单的单词计数器

下面是一个使用std::unordered_map来统计文本中每个单词出现频率的例子:

cpp
#include <iostream>
#include <unordered_map>
#include <string>
#include <sstream>
#include <algorithm>

int main() {
std::string text = "the quick brown fox jumps over the lazy dog the fox was quick";

std::unordered_map<std::string, int> wordCount;
std::istringstream iss(text);
std::string word;

// 统计每个单词出现的次数
while (iss >> word) {
++wordCount[word];
}

// 输出结果
std::cout << "Word frequencies:" << std::endl;
for (const auto& pair : wordCount) {
std::cout << pair.first << ": " << pair.second << std::endl;
}

// 找出出现最多的单词
auto maxElement = std::max_element(
wordCount.begin(), wordCount.end(),
[](const auto& a, const auto& b) { return a.second < b.second; }
);

std::cout << "\nMost frequent word: \"" << maxElement->first
<< "\" appears " << maxElement->second << " times." << std::endl;

return 0;
}

输出(顺序可能不同):

Word frequencies:
dog: 1
lazy: 1
jumps: 1
brown: 1
was: 1
over: 1
fox: 2
the: 3
quick: 2

Most frequent word: "the" appears 3 times.

应用案例2:使用tuple存储和处理多维数据

std::tuple在处理多个相关的值时非常有用,例如存储和处理3D坐标点:

cpp
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <cmath>

// 使用tuple表示三维点(x,y,z)
using Point3D = std::tuple<double, double, double>;

// 计算两点之间的欧几里得距离
double distance(const Point3D& p1, const Point3D& p2) {
double dx = std::get<0>(p1) - std::get<0>(p2);
double dy = std::get<1>(p1) - std::get<1>(p2);
double dz = std::get<2>(p1) - std::get<2>(p2);
return std::sqrt(dx*dx + dy*dy + dz*dz);
}

int main() {
std::vector<Point3D> points = {
{1.0, 2.0, 3.0},
{4.0, 5.0, 6.0},
{7.0, 8.0, 9.0},
{2.0, 3.0, 4.0}
};

// 找出距离原点最近的点
Point3D origin = {0.0, 0.0, 0.0};

auto closest = std::min_element(points.begin(), points.end(),
[&origin](const Point3D& p1, const Point3D& p2) {
return distance(origin, p1) < distance(origin, p2);
}
);

std::cout << "Closest point to origin: ("
<< std::get<0>(*closest) << ", "
<< std::get<1>(*closest) << ", "
<< std::get<2>(*closest) << ")" << std::endl;

std::cout << "Distance: " << distance(origin, *closest) << std::endl;

return 0;
}

输出:

Closest point to origin: (1, 2, 3)
Distance: 3.74166

总结

C++11引入的新容器和算法大大丰富了C++标准库的功能和使用灵活性:

  1. 新增容器

    • std::array - 固定大小的数组,结合C风格数组的性能与STL容器的便利
    • std::forward_list - 单向链表,比双向链表更节省内存
    • 无序关联容器(unordered_map/set系列)- 基于哈希表,提供常数时间的查找复杂度
    • std::tuple - 异构固定大小集合,可以存储不同类型的元素
  2. 新增算法

    • std::beginstd::end - 统一处理容器和数组的开始和结束
    • std::all_ofstd::any_ofstd::none_of - 检查元素是否满足条件
    • std::find_if_not - 寻找不满足条件的元素
    • std::iota - 用递增值填充范围
    • std::minmaxstd::minmax_element - 同时获取最小和最大值

这些新特性使代码更加简洁、可读性更强,同时提高了执行效率。

练习

  1. 创建一个程序,使用std::array存储十个整数,然后使用std::minmax_element找出最大和最小值。

  2. 实现一个简单的电话簿程序,使用std::unordered_map存储姓名和电话号码。

  3. 使用std::tuple存储学生信息(姓名、学号、成绩),并编写函数计算班级平均成绩。

  4. 创建一个程序,使用std::all_of检查容器中所有数字是否为质数。

  5. 实现一个函数,使用std::iota创建一个包含1到n的数字序列,然后移除所有不是质数的数字。

参考资源

通过掌握这些新容器和算法,你将能够编写更高效、更简洁的C++代码,并为进一步学习C++11及更新标准打下坚实基础。