C++ 11新容器和算法
C++11标准为C++语言带来了丰富的新特性,其中包括若干新增的容器和算法,大大提升了C++的编程效率和代码表达能力。本文将介绍这些新容器和算法,帮助初学者理解并掌握如何在实际编程中运用它们。
新增容器
C++11在原有STL容器的基础上,引入了几个非常实用的新容器类型,包括无序容器、数组容器和元组。
std::array
std::array
是一个固定大小的数组,它提供了STL容器的接口,同时保持了C风格数组的性能特性。
#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
(双向链表)占用更少的内存,在只需要从前向后遍历的情况下性能更好。
#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::map
、std::set
等),在查找、插入和删除操作上通常有更好的平均性能(常数时间复杂度)。
#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::map
或std::set
。
std::tuple
std::tuple
是一个固定大小的异构集合,可以存储不同类型的对象。它是std::pair
的泛化版本,可以保存任意数量的元素。
#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::begin
和std::end
,使得无论是使用STL容器还是原生数组,我们都可以用统一的方式获取开始和结束迭代器。
#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
这三个算法让我们可以轻松地检查容器中元素是否满足特定条件。
#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
算法寻找第一个不满足指定条件的元素。
#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
算法用递增的值填充范围。
#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
这两个算法分别用于获取两个值的最小和最大值,以及范围内的最小和最大元素。
#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
来统计文本中每个单词出现频率的例子:
#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坐标点:
#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++标准库的功能和使用灵活性:
-
新增容器:
std::array
- 固定大小的数组,结合C风格数组的性能与STL容器的便利std::forward_list
- 单向链表,比双向链表更节省内存- 无序关联容器(unordered_map/set系列)- 基于哈希表,提供常数时间的查找复杂度
std::tuple
- 异构固定大小集合,可以存储不同类型的元素
-
新增算法:
std::begin
和std::end
- 统一处理容器和数组的开始和结束std::all_of
、std::any_of
和std::none_of
- 检查元素是否满足条件std::find_if_not
- 寻找不满足条件的元素std::iota
- 用递增值填充范围std::minmax
和std::minmax_element
- 同时获取最小和最大值
这些新特性使代码更加简洁、可读性更强,同时提高了执行效率。
练习
-
创建一个程序,使用
std::array
存储十个整数,然后使用std::minmax_element
找出最大和最小值。 -
实现一个简单的电话簿程序,使用
std::unordered_map
存储姓名和电话号码。 -
使用
std::tuple
存储学生信息(姓名、学号、成绩),并编写函数计算班级平均成绩。 -
创建一个程序,使用
std::all_of
检查容器中所有数字是否为质数。 -
实现一个函数,使用
std::iota
创建一个包含1到n的数字序列,然后移除所有不是质数的数字。
参考资源
- C++ Reference
- C++11 Standard
- The C++ Programming Language by Bjarne Stroustrup
- Effective Modern C++ by Scott Meyers
通过掌握这些新容器和算法,你将能够编写更高效、更简洁的C++代码,并为进一步学习C++11及更新标准打下坚实基础。