CppGuide社区
  • cppinterviewmostaskedquestions
zhangxf
2025-03-27
目录

第十三章 标准模板库

# 第十三章 标准模板库

通过接下来的几个问题，我们将了解标准模板库（Standard Template Library），包括它的历史、概念以及一些算法。

# 问题107：什么是STL？

STL是标准模板库（Standard Template Library）的缩写，但实际上并不存在名为“STL”的库，它是C++标准库的一部分。

STL是一组模板类和函数，用于为常见问题提供解决方案。STL的元素可以分为四类：

  • 算法，例如：std::find、std::copy。
  • 容器，例如：std::vector<T>、std::list<T>。
  • 函数对象，例如：std::greater<T>、std::logical_and<T>。
  • 迭代器，例如：std::iterator、std::back_inserter 。

STL由亚历山大·斯捷潘诺夫（Alexander Stepanov）创建。20世纪70年代，他就有了创建一个通用数据处理库的想法，但当时没有语言支持来实现他的梦想。

到了80年代，他首次尝试用ADA语言来实现，但这种语言除了在国防工业外，并没有得到广泛应用。

一位前同事说服他向C++委员会介绍这个想法，1993年11月，他照做了。随后进展迅速，1994年3月，斯捷潘诺夫提交了正式提案，仅仅4个月就被接受。8月，斯捷潘诺夫的雇主惠普公司发布了STL的首个实现版本。

# 问题108：相较于原生循环，算法有哪些优势？

首先，什么是原生循环？

“原生循环是指函数中，其目的大于循环所实现算法的任何循环。”——肖恩·帕伦特（Sean Parent），《C++调味》

为什么你应该优先使用std算法，而不是这样的原生循环呢？

  1. 算法几乎没有错误：如果你要重复编写某段代码一千次，那么偶尔犯些错误的可能性很大。这很正常，人都会犯错。另一方面，如果你使用的是之前编写并被使用过百万次的函数，就不会遇到任何错误。
  2. 算法性能更好：这一点只在一定程度上正确。在C++中，<algorithms>头文件中的函数并没有针对极端情况进行优化，而是为了在不同系统和容器类型之间实现特定的可移植性进行了优化。你可以在任何STL容器上使用它们，而无需知道容器的确切类型。因此，我们不能认为它们能利用底层数据集的特性。尤其是它们不是直接对容器进行操作，而是通过迭代器来访问背后的数据。我说不能这样认为，是因为实际上很少有人了解编译器底层的运行机制，你可能会发现或编写一个比常见标准库实现大很多，但针对每种容器类型都进行了优化的标准库。

同时，你的for循环很可能也没有经过优化，这也没关系。当然，在编写循环时，你能掌控一切，可以对其进行优化，充分发挥其性能。但对于已经编写好的库函数，即使是标准库函数，你也无法做到这一点。

不过，标准算法已经进行了合理的优化，而我们经常使用的原生循环大多没有这些优化。最终，算法的性能更好。 3. 算法表达性更强：原生循环包含底层代码，而调用算法时，这些调用更具表达性。举个简单的例子，下面这段代码是做什么的呢？

const  std::vector<int> v{1, 2, 3, 4, 5};
auto  ans = false;
for  (const  auto& e : v) {
    if  (e % 2 == 0) {
        ans = true;
        break ;
    }
}
1
2
3
4
5
6
7
8

思考一下后，我们可以说这段代码是用来判断向量v中是否存在偶数元素的。那么如何让它更易读呢？使用算法：

const  std::vector<int> v{1, 2, 3, 4, 5}; 
const  auto  ans = std::any_of(v.begin(), v.end(),
                              [](const  auto& e) {return  e % 2 ==0;});
1
2
3

是不是简单多了？这还只是一个简单的例子。 4. 结论：大多数情况下，算法比普通的for循环更好。与循环相比，算法更不容易出错，因为它们已经编写并经过大量测试。除非你追求极致的性能，否则算法对你来说已经足够好，实际上它们比简单的循环性能更好。

但最重要的是，算法表达性更强。从众多算法中挑选合适的算法并非易事，但通过学习和实践，你将能够轻松找到在大多数情况下可以替代for循环的算法。

# 问题109：算法会验证范围吗？

下面这段代码能编译吗？你认为copiedNumbers的内容会是什么？

auto  numbers21 = { 1, 3 };
auto  numbers22 = { 3, 5 }; 
std::vector<int> copiedNumbers; 
std::copy_if(numbers21.begin(), numbers22.end(),
             std::back_inserter(copiedNumbers),
             [](auto  number) {return  number % 2 == 1;});
1
2
3
4
5
6

std::copy_if接受三个参数，如果第三个参数（函数指针、函数对象或lambda表达式）的求值结果为真，就复制指定范围内的元素。std::copy_if，顺便说一句，<algorithm>头文件中的任何函数都不会也无法判断前两个参数，即起始迭代器和结束迭代器，是否属于同一个容器。确保传入正确的参数是调用者的责任，如果不遵守规则，结果将是可怕的未定义行为。

所以在copy_if内部会发生的情况是，指向当前位置的迭代器会不断递增，直到到达结束迭代器。但如果结束迭代器的地址实际上在起始迭代器之前呢？如果两个容器相邻呢？如果它们之间有一些垃圾数据呢？

这些都属于未定义行为。你可能会得到看似正确的结果，比如两个容器内容的组合，也可能会遇到超时，或者得到一个漂亮的核心转储（core dump）错误。

编译器唯一能验证的是两个迭代器属于同一类型。所以你不能把list和vector组合在一起，也不能把int类型的vector和float类型的vector组合在一起。

你必须始终仔细检查传入的内容是否有效，并遵守给定算法所规定的契约。

# 问题110：可以组合不同大小的容器吗？

解释一下下面这段代码的作用！

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

int  main() {
    std::vector<int> values{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    std::vector<int> otherValues{ 10, 20, 30 };
    std::vector<int> results;

    std::transform(values.begin(), values.end(),
                   otherValues.begin(),
                   std::back_inserter(results),
                   [](int  number, int  otherNumber) {
                       return  number + otherNumber;
                   });

    std::cout << "copied numbers: ";
    for  (const  auto& number : results) {
        std::cout << ' ' << number;
    }
    std::cout << '\n';

    return  0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

首先，这样的代码背后的意图可能是什么呢？通过std::transform，我们试图将两个向量的内容组合起来，将values中的第n个元素与otherValues中的第n个元素相加，并将和存入results向量中。

这段代码很简单，但有个问题。传入的两个范围的元素数量并不相同。

记住，std::transform通过起始迭代器和结束迭代器获取第一个范围，而第二个输入范围（顺便说一句，它不是必需的）仅通过起始迭代器获取。

和<algorithm>头文件中的所有类似函数一样，std::transform假定并实际上期望第二个输入范围的元素数量至少与第一个范围相同。

但如果这个期望没有得到满足会怎样呢？

你可能期望会取一个初始化为零的元素来代替，但事实并非如此，尽管很容易想出一些示例代码来支持这个假设，但实际并非如此。

这属于未定义行为。

在大多数情况下，运行时会直接使用在相邻内存地址找到的任意值，即使该值不属于向量。

所以你必须始终确保仅由起始点定义的第二个输入范围至少与第一个范围一样长。

# 问题111：vector的内存布局是如何组织的？

如果你在栈上局部创建一个vector（不使用new），可能会认为数据也在栈上。但实际上，栈上的vector对象本身很小，它包含一个指针，指向堆上动态分配的内存。

所以在栈上，你会看到上述指针以及其他一些额外变量，用于记录大小和容量。你可以查看这张示意图。

还有其他实现方式，比如迭代器（iterators）分别指向已分配内存的起始位置、当前末尾位置以及总容量的末尾位置。查看这张示意图 。

关键在于，主vector对象中有一些变量，有助于找到实际存储在堆上的数据。堆上的内存必须是连续的，如果vector需要增长扩容，可能需要将全部内容复制到其他地方。

为避免这些额外的复制操作，如果你知道vector会增长到多大，最好在声明后立即调用std::vector<T>::reserve(maxCapacity)预留好容量。

# 问题112：我们可以从标准容器（如std::vector ）继承吗？如果可以，会有什么影响？

标准容器将构造函数声明为公共的且非最终的，所以可以从它们继承。实际上，从强类型容器中获益，这是一种广为人知且常用的技术。

class Squad : public std::vector {
    using std::vector::vector;
    //...
};
1
2
3
4

这种方式简单易懂，但你会在不同论坛上发现很多人说这是严重错误，如果你是一名严谨的开发者，就应该不惜一切代价避免这么做。

他们为什么这么说呢？

主要有两个理由。一是在STL中，算法和容器是明确分离的关注点；二是缺乏虚构造函数。

但这些理由站得住脚吗？或许吧，这要看情况。

我们先从缺乏虚析构函数这个问题说起，它似乎更实际一些。

确实，缺乏虚析构函数可能会导致未定义行为和内存泄漏。这两个问题都很严重，但未定义行为更糟糕，因为它不仅可能导致程序崩溃，甚至可能造成难以检测的内存损坏，最终引发程序出现奇怪的行为。

不过，缺乏虚析构函数并非默认就会导致未定义行为和内存泄漏，而是取决于你使用派生类的方式。

如果你通过指向基类的指针删除对象，而基类的析构函数是非虚的，那你就得承担未定义行为带来的后果。另外，如果派生对象引入了新的成员变量，还会出现内存泄漏问题。但话说回来，相比之下这还是个小问题。

另一方面，这也意味着那些因为未定义行为和内存泄漏，就坚决反对从std::vector （或者任何没有虚析构函数的类）继承的人，他们的观点并不正确。

如果你清楚自己在做什么，并且仅利用这种继承来引入强类型的vector，而不是为容器引入多态行为和额外状态，那么使用这种技术完全没问题。只是你得清楚其中的局限性，不过在公共库中，这可能不是最佳策略，关于这点我们稍后再说。

所以，另一个主要顾虑是，在新对象中你可能会混淆容器和算法。STL的创造者认为这是不好的做法，那又怎样呢？最初设计STL的亚历山大·斯特潘诺夫（Alexander Stepanov） 以及后来为其做出贡献的人都很聪明，他们很可能比我们大多数人都更擅长编程。他们设计的函数和对象在C++社区被广泛使用，可以说几乎人人都在用。

很可能我们的工作并没有那么多限制，我们不是在为整个C++社区开发东西。我们是在开发有特定严格限制的应用程序，我们的代码不会被原样复用，永远不会。我们不是在开发通用库，而是在开发一次性的商业应用。

只要我们能保证代码整洁（不管这意味着什么），提供非通用的解决方案完全没问题。

总之，可以这么说，在应用场景中，只要你不涉及多态，从容器继承来实现强类型是可行的。

# 问题113：执行以下声明后，myCollection的类型是什么？

auto myCollection = {1,2,3};
1

类型是std::initializer_list<int>。int部分可能很容易理解，至于std::initializer_list，你要知道，在使用auto进行类型推导时，如果使用花括号，有两种情况。

如果花括号中没有任何内容，会出现编译错误，因为编译器无法从<brace-enclosed initializer="list"()>推导出std::initializer_list<auto> 。所以不会得到空容器，而是编译错误。

如果花括号中至少有一个元素，类型就是std::initializer_list<int>。

如果你想知道这个类型是什么，要明白它是一个轻量级代理对象，用于访问const T类型的对象数组。在以下情况会自动构造：

  • 使用花括号初始化列表对对象进行列表初始化，且对应的构造函数接受std::initializer_list参数。
  • 花括号初始化列表出现在赋值运算符右侧或作为函数调用参数，且对应的赋值运算符/函数接受std::initializer_list参数。
  • 花括号初始化列表绑定到auto，包括在范围for循环中。

初始化列表可能通过一对指针，或者一个指针加长度的方式实现。复制std::initializer_list被视为浅拷贝，因为它不会复制底层对象。

# 问题114：const_iterators相较于iterators有什么优势？

const_iterators就像是STL世界里指向常量对象的指针。它们指向的值不能被修改。使用const_iterators遵循与在合适场景下使用const变量相同的原则。

自C++11起，所有STL容器都有cbegin和cend成员函数，即便容器本身不是常量的，这些函数也能生成const_iterators。

自C++14起，还有cbegin、cend、crbegin、crend这些非成员函数可用。如果你想要编写通用代码，最好使用非成员函数，因为它们也适用于内置数组，而成员函数则不行。

# 问题115：使用算法二分查找一个元素！

你觉得这段代码会做什么？它能找到7吗？

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

int main() {
    std::vector<int> numbers{1,54,7,5335,8};
    std::cout << std::binary_search(numbers.begin(), numbers.end(), 7) << std::endl;
}
1
2
3
4
5
6
7
8

它很可能找不到7的位置，即便得到了正确结果，也不可靠。实际上，上述代码存在未定义行为。

这都与约定和原则有关。在C++中，一个基本概念是，你不应为未使用的功能付出代价。按照这种理念，std::binary_search以及其他一些算法要求输入范围是有序的。毕竟，搜索算法不应负责排序，而那些已经传入有序范围的用户也不应为不必要的排序尝试付出代价。

所以，要让这段代码正常工作，只需在传入搜索算法前对vector进行排序。

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

int main() {
    std::vector<int> numbers{1,54,7,5335,8};
    std::sort(numbers.begin(), numbers.end());
    std::cout << std::binary_search(numbers.begin(), numbers.end(), 7) << '\n';
}
1
2
3
4
5
6
7
8
9

关键在于，算法都有其约定，你应该先了解并遵守这些约定。

# 问题116：什么是迭代器类（Iterator class）？

你可能还记得，标准模板库（Standard Template Library）由容器、算法、函子（functors）和迭代器组成。迭代器是连接容器和函子的纽带。

在STL中，在范围（ranges）出现之前，算法从不直接操作容器，而是操作迭代器。

迭代器就像指针。它是一个对象，指向某个元素范围（如数组或容器）中的元素，并且能够使用一组运算符（至少有自增（++）和解引用（*）运算符）遍历该范围内的元素。

迭代器有不同的类别，其分类取决于它们实现的功能。从最通用到最特殊的类别依次为：

  • 随机访问（Random Access）
  • 双向（Bidirectional）
  • 正向（Forward）
  • 输入（Input）
  • 输出（Output，输入和输出实际上处于同一层级）

想了解这些类别的更多详细信息，查看这个链接 。

上次更新: 2025/03/27, 20:29:48
第十二章 程序质量
第十四章 杂项

← 第十四章 杂项→

最近更新
01
第一章 auto与类型推导
03-27
02
第二章 关键字static及其不同用法
03-27
03
C++语言面试问题集锦 目录与说明
03-27
更多文章>
Copyright © 2024-2025 沪ICP备2023015129号 张小方 版权所有