C++智能线性容器
让我结合背景来解释我的问题，这样会更容易理解为什么我要求这种特定类型的事情。我正在开发一个即时通讯工具。我的老师概述了大部分架构，但实现细节可能有所不同。有一个“引擎”类，EventManager，用于注册客户端。为了识别它们并轻松删除它们，我使用地图（带有客户端 ID）或带有指针的集合。到目前为止，一切都很好。但是这个 EventManager 使用了 poll() （或 select()），但是使用起来并不像 poll() 那样舒服，就像你有的那样每次都重建数组，我猜这很慢而且不太好，而且我可以将自己限制在 UNIX 环境（如果你问的话）在其主循环中。这需要一个 struct pollfd 数组。现在，每次有新客户到来或离开时，都需要重建该阵列。要么我手动使用动态数组并每次分配内存（baaaaaad），要么我使用向量，它可以很好地处理新客户端在容器末尾的 struct pollfd 插入，或者使用双端队列，它可以很好地插入和删除任何地方。现在我的两个问题是：
- 如果我选择向量，它会自动收缩并在其中间移动元素而不是完全重新分配吗？ 如果是在开始的时候，无论如何
- 都会复制很多，所以我想使用双端队列。它是否有一个数组接口（就像你对向量所做的那样 -
&myVector[0]）或者它是严格不连续的？
Let me explain my problem together with the background, so it would be easier to understand why I'm asking for this specific type of thing. I'm developing an instant messenger. Most of the architecture is outlined by my teacher, however implementation detail may vary. There is an "Engine" class, EventManager, which registers clients. To identify them and to easily remove them, I use a map (with client-id's) or a set with pointers. So far, so good. But then this EventManager uses poll() (or select(), but that's nowhere as comfortable to use as poll(), as you have to rebuild the array each time, which is slow and not-so-nice, I guess, and I can restrict myself to UNIX environment, if you ask) in its main loop. Which needs an array of struct pollfd. Now every time a new client comes or goes, this array needs to be rebuilt. Either I use a dynamic array by hand and allocate memory every time (baaaaaad), or I use a vector, which would handle new client's struct pollfd insertion pretty well at the end of the container, or a deque, which would insert and remove anywhere pretty well. Now my two questions are:
- If I choose
vector, will it automatically shrink and move elements in the middle of itself instead of full reallocation? and - That would anyway copy a lot, if it's in the beginning, so I'd like to use deque. Does that have an array interface (like you would do with vector -
&myVector[0]) or is it strictly non-contiguous?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果从
向量中间删除某些内容，它会将所有后续元素向开头移动一个位置。它将不会重新分配。您根本不必考虑重新分配，因为它们会摊销为每次插入提供 O(1) 时间。双端队列并不比向量好多少。从开头或结尾删除是有效的。不是从中间来的。如果你从任何地方删除，那么它的速度有望是向量的两倍，但不会更快。由于它的结构更复杂，因此速度可能会更慢。 deque 不保证连续存储，因此尽管允许建立索引并在 O(1) 时间内完成，但您仍然无法可靠地将其转换为指针。
不管怎样，这听起来像是过早的优化。使用向量。由于客户端的顺序并不重要，因此您可以通过将要删除的元素与向量中的最后一个元素交换并在之后调用
pop_back()来加快客户端的擦除速度。If you remove something from the middle of a
vectorit will move all the following elements one position towards the beginning. It will not reallocate. You don't have to consider reallocations at all because they are amortized to give O(1) time per insertion.deque is not much better than vector. Removing from the beginning or end is efficient. Not from the middle. If you remove from anywhere, then it will hopefully be twice as fast a vector, but not faster. Since it's a more complicated structure it'll probably be even slower. deque doesn't guarantee continuous storage, so although indexing is allowed and done in O(1) time, you still can't reliably convert it to a pointer.
Anyway it smells like premature optimization. Use vector. Since the order of clients is not significant, you can speed up the erasure of clients by swapping the element that you want to remove with the last element in the vector and calling
pop_back()after that.