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::map、std::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::map或std::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::begin和std::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::begin和std::end - 统一处理容器和数组的开始和结束
   • std::all_of、std::any_of和std::none_of - 检查元素是否满足条件
   • std::find_if_not - 寻找不满足条件的元素
   • std::iota - 用递增值填充范围
   • std::minmax和std::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++ Reference
• C++11 Standard
• The C++ Programming Language by Bjarne Stroustrup
• Effective Modern C++ by Scott Meyers

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