当前位置：文江博客话题详情

为什么push_back或push_front会使双端队列的迭代器失效？

发布于 2024-07-22 06:03:11 字数 103 浏览 5 评论 0原文

正如标题所问。

我对双端队列的理解是它分配“块”。我不明白分配更多空间如何使迭代器失效，如果有的话，人们会认为双端队列的迭代器比向量的迭代器有更多的保证，而不是更少。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

对不⑦ 2024-07-29 06:03:11

C++ 标准没有指定双端队列是如何实现的。不需要通过分配新块并将其链接到先前的块来分配新空间，所需要的只是在每一端的插入以恒定时间分摊。

因此，虽然很容易了解如何实现双端队列以提供您想要的保证[*]，但这并不是唯一的方法。

[*] 迭代器具有对元素的引用，以及对其所在块的引用，以便它们在到达块的末端时可以继续前进/后退。另外，我认为对双端队列本身的引用，使得operator+可以像随机访问迭代器所期望的那样是恒定时间的——遵循从块到块的链接链还不够好。

回复收藏 0 原文

不甘平庸 2024-07-29 06:03:11

更有趣的是，push_back 和 push_front 不会使任何对双端队列元素的引用无效。只有迭代器才被假定为无效。

据我所知，该标准没有说明原因。但是，如果实现的迭代器知道其直接邻居（如列表），则如果迭代器指向既位于双端队列边缘又位于块边缘的元素，则该迭代器将变得无效。

回复收藏 0 原文

允世 2024-07-29 06:03:11

我猜。 push_back/push_front可以分配新的内存块。双端队列迭代器必须知道递增/递减运算符何时应跳转到下一个块。该实现可以将该信息存储在迭代器本身中。在 push_back/push_front 之后递增/递减旧迭代器可能无法按预期工作。

此代码可能会也可能不会因运行时错误而失败。在我的 Visual Studio 上，它在调试模式下失败，但在发布模式下运行到结论。在 Linux 上它会导致分段错误。

#include <iostream>
#include <deque>

int main() {
    std::deque<int> x(1), y(1);
    std::deque<int>::iterator iterx = x.begin();
    std::deque<int>::iterator itery = y.begin();

    for (int i=1; i<1000000; ++i) {
        x.push_back(i);
        y.push_back(i);
        ++iterx;
        ++itery;
        if(*iterx != *itery) {
            std::cout << "increment failed at " << i << '\n';
            break;
        }
    }
}

My guess. push_back/push_front can allocate a new memory block. A deque iterator must know when increment/decrement operator should jump into the next block. The implementation may store that information in iterator itself. Incrementing/decrementing an old iterator after push_back/push_front may not work as intended.

This code may or may not fail with run time error. On my Visual Studio it failed in debug mode but run to the conclusion in release mode. On Linux it caused segmentation fault.

#include <iostream>
#include <deque>

int main() {
    std::deque<int> x(1), y(1);
    std::deque<int>::iterator iterx = x.begin();
    std::deque<int>::iterator itery = y.begin();

    for (int i=1; i<1000000; ++i) {
        x.push_back(i);
        y.push_back(i);
        ++iterx;
        ++itery;
        if(*iterx != *itery) {
            std::cout << "increment failed at " << i << '\n';
            break;
        }
    }
}

回复收藏 0 原文