空双端队列与向量

Question

我在 STL 测验问题样本中遇到了以下问题

问：当您尝试编译运行以下代码时会发生什么？

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <deque>

using namespace std;

void printer(int i) {
    cout << i << ", ";
}

int add (int a, int b) {
    return a+b;
}

int main() {

    vector<int> v1 = { 3, 9, 0, 2, 1, 4, 5 };
    set<int> s1(v1.begin(), v1.end());
    deque<int> d1;      // LINE I
    transform(s1.begin(), s1.end(), v1.begin(), d1.begin(), add);//LINE II
    for_each(d1.begin(), d1.end(), printer); //LINE III

    return 0;
}


A compilation error in LINE III
B program outputs: 3, 10, 2, 5, 5, 9, 14,
C program outputs: 3, 9, 0, 2, 1, 4, 5, 
D runtime error at LINE III 
E compilation error in LINE II 
F runtime error at LINE II 
G program outputs: 0, 1, 2, 3, 4, 5, 9,

通过阅读代码，我预计答案是 F，因为 1 复制到零大小的容器是未定义的行为或 2 stl 函数可能会在运行时检查是否有足够的容量，如果没有则抛出异常

我在 gcc 4.8.1

上编译并运行代码

没有编译或运行时间错误。 LINE III 什么也不打印，因为我假设 d1.begin() == d1.end()。双端队列中没有有效元素。

但是如果我添加 LINE IV

for_each(d1.begin(), d1.begin()+7, printer); //LINE IV

它打印

3, 10, 2, 5, 5, 9, 14,

所以 t运行sform 函数确实将 7 个元素写入 "unmanaged" 内存。

当我将 LINE I 更改为

vector<int> d1;

然后运行LINE II 出现了时间错误。

问题

1 能不能说上面的问题没有提供正确答案的选项。我不确定其他编译器的行为方式。

2 我假设因为双端队列不一定使用连续存储，所以当 t运行sform 函数向其写入元素时，双端队列迭代器会发生某种形式的分配。然而，双端队列本身的大小仍然为 0。但是向量迭代器在尝试写入内存时会导致崩溃。有没有人详细解释一下。

3 在编写我自己的可以接受迭代器的实用程序函数时，在不了解底层容器的情况下，处理这种情况的最佳方法是什么，迭代器被无意中传递到一个空容器。我认为 begin() == end() 是 gua运行teed 对于所有空容器都是正确的，所以首先执行此检查并抛出异常？

谢谢

Answer 1

问题 3 的答案：

您可以使用类似这样的方法来验证目标容器不仅不为空，而且大小足够：

if(std::distance(d1.begin(), d1.end()) < std::distance(s1.begin(), s1.end()))
{
    throw std::runtime_error("Not enough space");
}

你在问题1中的假设似乎是正确的。 gcc 和 clang 编译都没有错误。

抱歉，我没有关于 2 的详细解释，但正如您所说，这是未定义的行为。上面的示例在使用 libstdc++（clang 和 gcc）编译时使用 deque 运行良好，但使用 libc++ 和 clang 编译时使用 deque 和 vector 出现段错误。因此，在 libstdc++ 中 deque 的实现似乎总是预分配一些 space（即使在运行 d1.shrink_to_fit() 之后）。

空双端队列与向量

empty deque vs vector

c++

stl