C++智能线性容器

Question

让我解释一下我的问题和背景，这样会更容易理解我为什么要问这种特定类型的事情。我正在开发一个即时通讯工具。我的老师概述了大部分架构，但实现细节可能会有所不同。有一个“引擎”类，EventManager，用于注册客户端。为了识别它们并轻松删除它们，我使用了一个映射(带有客户端 ID)或一个带有指针的集合。到目前为止，一切都很好。但是此 EventManager 使用 poll()(或 select()，但使用起来不如 poll() 舒适，因为您有每次都重建数组，我猜这很慢而且不太好，如果你问的话，我可以将自己限制在 UNIX 环境中)在它的主循环中。这需要一个 struct pollfd 数组。现在每次有新客户到来或离开时，这个数组都需要重建。要么我手动使用动态数组并每次分配内存(baaaaaad)，要么我使用一个 vector ，它可以很好地处理新客户端的 struct pollfd 在容器末尾插入，或者一个双端队列，它可以很好地在任何地方插入和删除。现在我的两个问题是:

1. 如果我选择 vector，它会自动收缩和移动自身中间的元素而不是完全重新分配吗？和
2. 无论如何都会复制很多，如果它在开头，所以我想使用双端队列。它是否具有数组接口(interface)(就像您对 vector 所做的那样 - &myVector[0])或者它是否严格不连续？

Answer 1

1. 如果您从 vector 的中间删除某些内容，它会将所有后续元素移向开头一个位置。它不会重新分配。您根本不必考虑重新分配，因为它们被分摊为每次插入 O(1) 时间。

2. deque 并不比 vector 好多少。从开头或结尾删除是有效的。不是从中间。如果你从任何地方移除，那么它的速度有望是 vector 的两倍，但不会更快。由于它是一个更复杂的结构，它可能会更慢。双端队列不保证连续存储，因此尽管允许建立索引并在 O(1) 时间内完成，但您仍然无法可靠地将其转换为指针。

无论如何，它闻起来像是过早的优化。使用 vector 。由于客户的顺序并不重要，您可以通过将要删除的元素与 vector 中的最后一个元素交换并在之后调用 pop_back() 来加快客户的删除。