Something like a deque on large numbers of items, but small memory usage on small numbers?

Question

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.

Answer 1

You don't mention if you need other capabilities of vector or deque like random access iterators. If you don't this actually sounds like a good candidate to use list. It has good performance inserting and removing from both ends.

Answer 2

You could use an (intrusive) list if you don't need random access by index. Lists allow quick O(1) push_front/push_back() and pop_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.