1

I know std::vector doesn't reduce its capacity but since std::deque is allocated in chunks, I expect it to free at least some of the chunks that are no longer used.

From what I have searched I am confused as the answer seems to be "no" or "maybe". Does anyone have a concrete answer?

If it does not free its chunks, does anyone know of some other implementation that does this?

I am brainstorming data structures for an application redesign that currently uses linked lists but gives poor performance which is why I am considering a deque. Challenge is my application should run the whole day and it would have tons of deque and each one could grow to be very long, hence I cannot neglect storage use of deque or a vector.

Suhail Khan
  • 190
  • 1
  • 1
  • 7
  • 1
    both `std::vector` and `std::deque` have `shrink_to_fit`, which is just a "request" in both cases. I think its a definite clear "maybe" – 463035818_is_not_an_ai Jul 09 '21 at 12:20
  • 1
    Sounds like you're trying to circumvent memory leaks, which are code bugs. Many apps that use large vectors run 24 hours a day, without any issues. Also, it is your compiler's heap manager that controls whether an actual call to "free" the memory will free the memory. All you're doing when you call `delete` or `free` is to tell the runtime that there are slots open -- whether the memory is actually freed by the OS or not is a different story. – PaulMcKenzie Jul 09 '21 at 12:22
  • Also, the `std::vector` and `std::deque` has an allocator as the second template argument. You can try and create one that matches what you are trying to achieve. – PaulMcKenzie Jul 09 '21 at 12:28
  • @PaulMcKenzie So does a deque call free or delete on an unused chunk? – Suhail Khan Jul 09 '21 at 12:30
  • [See the documentation on shrink_to_fit](https://en.cppreference.com/w/cpp/container/deque/shrink_to_fit) – PaulMcKenzie Jul 09 '21 at 12:34
  • `deque` calls the allocator's `deallocate` function to free an unused chunk – Marshall Clow Jul 09 '21 at 14:47

2 Answers2

2

I know std::vector doesn't reduce its capacity but since std::deque is allocated in chunks, I expect it to free at least some of the chunks that are no longer used.

[ This is specific to libc++ ]

As a deque shrinks, most of the unused chunks will be freed. The deque will keep (at most) two unused chunks. The reason for this is that when the deque is being used "as a queue", (items are being put on one end and taken off the other end, but the size of the deque is relatively stable), the deque will not need to allocate or free additional chunks.

Marshall Clow
  • 15,972
  • 2
  • 29
  • 45
0

Does anyone have a concrete answer?

The concrete answer is "no ... or maybe".

The language standard doesn't impose any requirements on containers cacheing or releasing cached memory during their lifetime. It is unspecified. It is an implementation detail, which is left up to the implementation.

So, your options are to:

  1. test what your standard library's implementation does
  2. find another implementation that does what you want
  3. write your own

If you decide on 2 or 3, you need a benchmark to tell whether you succeeded anyway, so do 1 first.

Useless
  • 64,155
  • 6
  • 88
  • 132