相关疑难解决方法(0)

可能重复:
为什么我更喜欢使用vector来deque

我很好奇为什么它std::vector比这更受欢迎std::deque.Deque几乎和查找一样有效,插入更有效(没有vector :: reserve),允许在前面插入/删除.

Herb Sutter曾经建议如果你想使用矢量,那就更喜欢deque(我在解读).然而,在最近关于编写Modern C++的演讲中,他再次强烈建议将其std::vector视为默认容器.根据我之前链接的GOTW,即使标准也有类似的措辞.

有这种差异的原因吗？它vector是否更简单,更为人所知,还是有技术原因？或者它vector只是一个更酷的名字..？

是否有一个特定的数据结构,C++ STL中的deque应该实现,或者是一个deque只是这个模糊的概念,一个数组可以从前面和后面增长,然而实现选择实现？

我以前总是假设deque是一个循环缓冲区,但我最近在这里读了一个C++引用,听起来像deque是某种数组的数组.它似乎不是一个普通的旧循环缓冲区.那么它是一个间隙缓冲区,还是可扩展数组的其他变体,还是仅仅依赖于实现？

答案的更新和摘要:

似乎普遍的共识是,双端队列是一种数据结构,这样:

• 插入或删除元素的时间应该在列表的开头或结尾处是恒定的,并且在其他地方最多是线性的.如果我们将此解释为真正的恒定时间而非摊销的恒定时间,正如有人评论,这似乎具有挑战性.有些人认为我们不应将此解释为非摊销的常数时间.
• "deque要求任何插入都应保持对成员元素的任何引用有效.迭代器可以无效,但成员本身必须保留在内存中的相同位置." 正如有人评论的那样:只需将成员复制到堆上的某个位置并将T*存储在引擎盖下的数据结构中即可.
• "在双端队列的开头或末尾插入单个元素总是需要一个恒定的时间,并导致对T的构造函数的单个调用." 如果数据结构在引擎盖下存储T*,也将实现T的单个构造函数.
• 数据结构必须具有随机访问权限.

如果我们将第一个条件设为"非摊销的恒定时间",似乎没有人知道如何得到第一和第四条件的组合.链表实现1)但不是4),而典型的循环缓冲实现4)但不实现1).我想我的实现可以满足以下两个要求.评论？

我们从其他人建议的实现开始:我们分配一个数组并从中间开始放置元素,在前面和后面留下空间.在这个实现中,我们跟踪中心在前后方向上有多少元素,调用那些值F和B.然后,让我们用一个两倍于原始大小的辅助数组来扩充这个数据结构.数组(所以现在我们浪费了大量的空间,但渐近的复杂性没有变化).我们还将从中间填充这个辅助数组,并给它类似的值F'和B'.策略是这样的:每次我们在给定方向上向主数组添加一个元素时,如果F> F'或B> B'(取决于方向),最多两个值从主数组复制到辅助数据数组直到F'赶上F(或B'跟B).因此,插入操作涉及将1个元素放入主数组并从主数据库复制到辅助数据2,但它仍然是O(1).当主阵列变满时,我们释放主阵列,使辅助阵列成为主阵列,并制作另一个大2倍的辅助阵列.这个新的辅助数组以F'= B'= 0开始,并且没有复制到它(因此如果堆分配是O(1)复杂度,则调整大小op为O(1)).由于添加到主要和主要的每个元素的辅助副本2个元素最多开始半满,因此当主要用完空间时,辅助节点不可能赶上主要元素.删除同样只需要从主要删除1个元素,从辅助删除0或1.因此,假设堆分配为O(1),则此实现满足条件1).我们使数组为T*,并new在插入时使用以满足条件2)和3).最后,4)被实现,因为我们使用数组结构并且可以轻松实现O(1)访问.

我已经读过按位置索引访问元素可以在STL双端队列中以恒定时间完成.据我所知,双端队列中的元素可能存储在几个非连续的位置,从而消除了通过指针算法的安全访问.例如:

ABC-> defghi-> jkl-> MNOP

上面的双端队列元素由一个字符组成.一组中的字符集表示它被分配在连续的存储器中(例如,abc在单个存储器块中,defhi位于另一个存储器块中,等等).任何人都可以解释如何通过位置索引进行访问可以在恒定时间内完成,特别是如果要访问的元素在第二个块中？或者双端队列是否有指向这组块的指针？

更新:或者deque还有其他常见的实现吗？

std::deque将元素存储在固定大小的“存储桶”（数组）中。不同的编译器使用不同的存储桶大小：

• MSVC：16个字节或元素大小（如果更大）
• GCC：512字节或元素大小（如果更大）
• 铛： element_size < 256 ? 4096 : element_size * 16

对于MSVC（尤其是MSVC）和GCC，如果双端队列元素的大小大于硬编码的大小，std::deque则std::list在大多数情况下会导致性能下降。

我认为Clang的效果更好，无论双端队列元素的大小如何，存储桶至少应包含16个元素。尽管在某些情况下，对于小元素，最小的bucket大小4096字节可能不是最佳的。

为什么没有std::deque用于存储桶大小的附加模板参数，其默认值是供应商认为合理的值？这不会破坏向后兼容性，但可以优化性能。

关于deque中的迭代器失效,我有点困惑.(在这个问题的背景下)

以下是摘自 - The C++标准库:教程和参考,作者:Nicolai M. Josuttis

除开头或结尾之外的任何元素的插入或删除都会 使引用双端队列元素的所有指针,引用和迭代器无效.

以下是SGI网站的摘录:

deque的迭代器失效的语义如下.Insert(包括push_front和push_back)使引用deque的所有迭代器无效.在双端队列中间擦除使所有引用双端队列的迭代器无效.只有当它指向已擦除的元素时,在双端队列的开头或结尾处擦除(包括 pop_front和pop_back)才会使迭代器无效.

恕我直言,deque是块的集合,第一个块在一个方向上生长,最后一个块在相反方向上生长.

  -   -  -  
  -   -  -
  |   -  -  ^
  |   -  -  |
  V   -  -  |
      -  -  -
      -  -  -

push_back, push_front 不应该对deque迭代器产生任何影响(我同意Josuttis).

什么是正确的解释？标准对此有何看法？

这个问题是关于拥有指针，使用指针，智能指针，向量和分配器的。

我对代码体系结构的想法有些迷茫。此外，如果这个问题在某个地方已经有答案，1.抱歉，但是到目前为止我还没有找到满意的答案，并且2.请指出。

我的问题如下：

我有一个存储在向量中的“事物”，以及这些“事物”的几个“消费者”。因此，我的第一次尝试如下所示：

std::vector<thing> i_am_the_owner_of_things;
thing* get_thing_for_consumer() {
    // some thing-selection logic
    return &i_am_the_owner_of_things[5]; // 5 is just an example
}

...

// somewhere else in the code:
class consumer {
    consumer() {
       m_thing = get_thing_for_consumer();
    }

    thing* m_thing;
};

在我的应用程序中，这是安全的，因为在任何情况下，“事物”的寿命都超过了“消费者”。但是，可以在运行时添加更多的“事物”，这可能会成为问题，因为如果std::vector<thing> i_am_the_owner_of_things;重新分配了这些事物，则所有thing* m_thing指针都将变为无效。

一种解决方案是将唯一的指针存储到“事物”，而不是直接存储“事物”，即如下所示：

std::vector<std::unique_ptr<thing>> i_am_the_owner_of_things;
thing* get_thing_for_consumer() {
    // some thing-selection logic
    return i_am_the_owner_of_things[5].get(); // 5 is just an example
}

...

// somewhere else in the code:
class consumer {
    consumer() {
       m_thing …

由于几天前的这个问题,有一些事情一直困扰着我对于野外std::deque::push_back/push_front实际std::deque实施的复杂性要求.

上一个问题的结果是这些操作需要具有O(1)最差的案例复杂性.我确认这确实是这样的c++11:

从23.3.3.4 deque修饰符,参考insert,push/emplace前/后

复杂性:复杂性是插入元素数量的线性加上到双端队列开始和结束距离的较小者.在双端队列的开头或末尾插入单个元素总是需要恒定的时间并导致对T的构造函数的单个调用.

这与O(1)索引,通过operator[]等的复杂性要求相结合.

问题是实现并不严格满足这些要求.

在这两个方面msvc与gcc所述std::deque的实施是一个阻塞数据结构,由指针的动态阵列的至(固定大小)的块,其中每个块中存储有数量的数据元素.

在最坏的情况下,push_back/front etc可能需要一个额外的块将被分配(这是精-固定大小的分配是O(1)),但它也可以要求块指针的动态阵列被调整大小-这不是很好的,因为这是O(m)其中m是块数,在一天结束时O(n).

显然,这仍然是分摊的O(1)复杂性,因为通常m << n它在实践中会非常快.但似乎存在一致性问题？

作为进一步的点,我看不出你如何能设计一个数据结构,严格同时满足O(1)两个复杂性push_back/front etc和operator[].您可以拥有块指针的链接列表,但这并不能提供所需的operator[]行为.真的可以吗？

如果我们不断在容器的前面和后面添加,则应选择矢量Deques.但是,这是什么？不要vector的和deque的operator[]工作一样,还是没有？如果没有,哪一个更快？

我的问题很简单:有可能获得指向std::queue容器适配器底层存储的指针吗？

我正在使用SFML进行渲染的一些模拟,我使用draw()SFML渲染目标(sf::RenderTarget)的方法来绘制整个数据.该方法具有类似C的接口,期望指向数据的指针,以及std::size_t具有要绘制的元素数量的指针.

由于数据存储在队列中用于某些目的,如果有某种方法可以将指针指向存储库底层而不是将数据复制到向量,我将很高兴.
我知道默认情况下std::queue调整容器std::deque,但我不知道如何实现循环缓冲区以及它的数据是否连续(所以我可以直接提取指向数据的指针).

编辑:表现

看看下面的答案,让我注意到我没有使用std::deque它,因为它看起来很像队列,但是因为我真的需要快速排队.我当然可以用std::vector.如果性能不是这里的重点,那么我会使用push_back()和erase( begin() )矢量.但我需要的是快速排队以及有效地将该队列的数据移动到渲染目标的方法.当然,如果平衡排队与绘制它的努力进入平局,我将使用std::vector.

我对deque的实现进行了一些搜索.根据这篇文章,deque使用向量的向量.我知道在开始和结束时推送应该是恒定的时间,并且还需要随机访问.我认为循环缓冲区满足所有这些要求,并且更加简单.那么为什么不使用循环缓冲区？

我还发现了增强循环缓冲区.它与deque相比如何？

编辑:好的,所以它与迭代器失效规则有关.它指出:

所有迭代器和引用都是无效的,除非插入的成员位于双端队列的末尾(前面或后面)(在这种情况下,所有迭代器都无效,但对元素的引用不受影响)

我的理解是重载像iter ++这样的运算符,迭代器必须拥有一个指向节点映射的指针和一个指向块的指针,所以如果重新分配节点映射,迭代器就会失效.但由于数据从未移动,因此引用仍然有效.