类似对大量项目使用双端队列，但对少量项目使用少量内存？
我有一大堆特定类型的对象，每个对象都可以分配一个双端队列来保存同一类型的其他对象。我使用双端队列是因为我需要在两端进行快速访问，并且因为任何特定对象都可能引用许多其他对象。
然而，很可能的情况是，许多甚至大多数对象引用了很少的其他对象。这种情况下，deque的内存占用是相当大的。我使用的实现是在执行第一个 Push_back() 后一次性分配 4096 个字节。双端队列中的每个元素只有 8 个字节。这是浪费了很多空间，特别是因为我正在制作许多这样的对象，因此也制作了许多这样的双端队列。
同时，我非常需要一个双端队列（或类似的东西），因为正如我所说，任何特定对象实际上都可以引用许多其他对象，尽管大多数对象引用很少的其他对象。
我的第一个想法是使用capacity()和reserve()来自己增加双端队列，但是我的编译器告诉我双端队列上没有这样的函数。
所以，我在想也许编写一个具有类似双端队列的接口的类，其底层是一个向量和一个双端队列，使用向量直到（比如说）存在十六个元素，之后向量被丢弃并使用双端队列从那里开始。
由于向量仅在只有少量元素时才使用，因此 push_front() 和 pop_front() 在速度方面效率低下应该不会太重要，而且因为我可以使用以下命令控制向量capacity() 和 Reserve()，当存在更多元素时，双端队列使用大量内存并不重要。
但是，在像这样推出我自己的课程之前，我想检查一下类似的东西是否已经存在。另外，如果有人知道我没有想到为什么这样的事情是一个坏主意，或者如果有人有任何相关的建议，我很乐意听到。
提前致谢。
I have a whole bunch of objects of a certain type, each of which may allocate a deque to hold other objects of that same type. I am using a deque because I need fast access at both ends, and because any particular object could possibly refer to many other objects.
However, it's likely the case that many or even most of the objects refer to very few other objects. In this case, the memory usage of deque is pretty big. The implementation I'm using is allocating 4096 bytes at a shot, as soon as I do the very first push_back(). Each element in the deque is only 8 bytes. That's a whole lot of wasted space, especially because I'm making many of these objects, and hence many of these deques.
At the same time, I pretty much need a deque (or something like it), because like I said, any particular object can actually refer to many other objects, despite the fact that most objects refer to very few other objects.
My first thought was using capacity() and reserve() to grow the deque myself, but my compiler informed me that there are no such functions on deque.
So, I was thinking perhaps to write a class with a deque-like interface, underlying which is a vector and a deque, with the vector used until (say) sixteen elements exist, after which the vector is thrown away and the deque is used from there on out.
Since the vector is only used when there are only a small number of elements, it shouldn't really matter too much that push_front() and pop_front() are going to be inefficient in terms of speed, and since I can control the vector with capacity() and reserve(), it shouldn't really matter too much that deque uses a lot of memory when more elements exist.
But, before rolling my own class like this, I wanted to check to see if something like this already exists. Also, if anybody knows of any reason I haven't thought of why something like this is a bad idea, or if anybody has any related suggestions, I'd love to hear it.
Thanks in advance.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您没有提及是否需要
vector或deque的其他功能，例如随机访问迭代器。如果您不这样做，这实际上听起来像是使用list的一个不错的选择。两端插拔性能良好。You don't mention if you need other capabilities of
vectorordequelike random access iterators. If you don't this actually sounds like a good candidate to uselist. It has good performance inserting and removing from both ends.如果您不需要按索引随机访问，则可以使用（侵入式）列表。列表允许快速 O(1)
push_front/push_back()和pop_front/pop_back()。如果对象不是共享的，也就是说，一个对象最多只被另一个对象拥有，那么侵入式列表将是最好的。由于您的对象属于同一类型，因此可以从一个内存池（大数组）分配它们，以避免任何内存开销。
You could use an (intrusive) list if you don't need random access by index. Lists allow quick O(1)
push_front/push_back()andpop_front/pop_back().If objects are not shared, that is, an object is only ever owned by at most one other object, than an intrusive list would be the best. And since your objects are of the same type, they can be allocated from one memory pool (big array) to avoid any memory overhead.