CODEWITHSUNDEEP
c++listmemorymemory-managementstl
Mr.C64
Mr.C64

Reputation: 42984

std::list node's memory recycling after element removal

I'd be interested to know if STL's std::list implements some form of node's "memory saving/recycling" when elements are removed from lists, to reuse the memory occupied by previous nodes for future addition of new elements to the list.

E.g. when std::list::pop_back() is called to remove the last element of a linked list, is the memory occupied by that node kind of saved, such that when a new element is added to end of the linked list using push_back(), there is no dynamic memory allocation for the new node, but simply the memory of the previously removed node is recycled?

This would be kind of similar to std::vector, which has slack capacity.

Upvotes: 3

Views: 433

Answers (1)

Reed Hedges
Reed Hedges

Reputation: 1650

This is a pretty old question but it came up on Google when I was looking for information on this.

When an item is removed from a std::list, then the memory for that item is deallocated and destroyed, unless you provide an alternate Allocator that does something different when asked to deallocate the memory. The standard library containers have pretty well defined memory characteristics, I doubt any modern standard library implementation tries to reuse memory. The OS may be trying to be efficient about allocation and deallocation but the default allocator would still be making system malloc/free calls which I assume are the expensive thing you are trying to avoid.

A universal or generic way to implement this is to write your own allocator.

Just using std::list though, if you want to reuse memory you could try using splice() to relink items to and from another list of reusable items. Or if you are both adding an item and removing another item at the same time (e.g. a buffer or fixed size queue where items are removed from the back whenever an item is added to the front), then splice the old item into the new position and replace its contents, etc.

More on splice: https://en.cppreference.com/w/cpp/container/list/splice

Don't get the splice() arguments mixed up. (That documentation says "another list" but it could be the same list; note that iterators will not be invalidated.)

Note that this is bordering on custom memory management and so make sure you have a clear, well defined algorithm for doing so.

As always with C++, you need to be aware of when objects/values are copied, allocated, and possibly moved. Read documentation of std::list carefully to understand when it is allocating and copying data. https://en.cppreference.com/w/cpp/container/list

An example follows that re-links the last element in the list to the front:

#include <list>
#include <iostream>
#include <algorithm>

int main() {
  std::list<int> l{1, 2, 3, 4};

  std::for_each(l.begin(), l.end(), [](int i){std::cout << i << ", ";});
  std::cout << "\n";

  auto topos = l.begin();
  auto frompos = l.end();
  frompos--;
  l.splice(topos, l, frompos);

  std::for_each(l.begin(), l.end(), [](int i){std::cout << i << ", ";});
  std::cout << "\n";

  return 0;
  }

Modify the above to store structs or objects in the list that print out when they are constructed, destroyed, copied and moved, and then try using insert(), emplace(), remove(), pop_back(), etc. to see what happens.

Upvotes: 5

Related Questions