::std::list::push_back()

[mikoil]

Hello,

Maybe someone here knows the answer because I've been looking for it but could not find it:

I know (seen it) that when I use
::std::list::erase()
to remove an item from the list, a "delete" is called.

That means we've got a "new" call somewhere? (probably at push_back())?

Why am I asking?
I don't want to get to memory fragmentation with a program I build, which is going to use this linked lists heavily.

In details, I have this "list" object which stores pointers to a custom class I've made.
So pointers are added, and then removed after a while.
I'm trying to avoid new/delete as much as possible, although this linked list idea seem to be very good.

Can someone shed some light please?

Thank you!

[kempofighter]

Erase only erases the elements. If you are adding pointers to objects to the list then you need to delete the objects yourself to avoid a memory leak. If you are really concerned about the std allocator then you'll have to write your own. When you use push_back to insert elements then the container class has to copy the "whatever it is that you are adding" which results in memory allocation internally. Post a small example of what you are trying to do. If you are putting pointers into the container, the container is only performing allocation/deallocation for the memory required to hold the pointers and not the entire object. The new/delete of the object is still your responsibility if that is the case.

[STLDude]

I think question should be more which container is right one for the job. For example, you can use std::vector of objects which will allocate continues memory block for them, but it depends if you want it sorted, how are you going to add, remove elements, etc. There are allot of consideration to pick the right container. If you are not sure, here some data about Big Oh notation.

P.S. The key in C++ is to minimize manual memory management (you should see very little of new and delete in your program).

[JohnW@Wessex]

In details, I have this "list" object which stores pointers to a custom class I've made.
So pointers are added, and then removed after a while.

If you're only storing pointers then a list is probably not the most efficient way of storing them. As said before, a vector would be more appropriate.
Also consider using some sort of smart pointer if you are dynamically allocating your class instances.

std::tr1::shared_ptr

boost::shared_ptr

[Zaccheus@Work]

I'm trying to avoid new/delete as much as possible, although this linked list idea seem to be very good.

Can someone shed some light please?

As kempofighter indicated, std::list (and std::vector) uses an allocator class to get (and free) the memory it needs:

template < class T, class Allocator = allocator<T> > class list;

std::allocator is what is doing the new and delete that you've noticed.

You can however write your own allocator class (I'll just call it class FasterAllocator here) and typedef your own specific use of std::list :

typedef std::list<SomeType,  FasterAllocator<SomeType> > SomeList;

You might want to read this:
http://www.ddj.com/cpp/184406243;jse...questid=105284

[mikoil]

Hi all and thanks for the attention!

I think my point has been slightly missed;

The program allocates, say, 100 instances of class myClass (which will not be freed until the program ends!).
Then it runs normally, while from time to time, it posts a "job" to the worker thread, which runs in the background and iterates a collection of items for jobs.
Now, the jobs are timed so the main thread might post 10 jobs within a second.
Then the worker thread will start an iteration (it sleeps between iterations) and examine all the new objects in the shared collection.

Now said that, what I know, and correct me if I'm wrong please:

Vector
- A vector will resize, on an erase/push.
- If I removed an object from the middle of the collection, say position 5, the vector library will have to copy all the objects after position 5 to the position 5 (object 6 becomes 5, object 7 becomes 6, etc'), and that might take a long time when I have hundreds if not thousands of objects inside the collection (and don't forget that in one iteration I might just erase all the objects, if conditions allow it).

On the other hand, list
- Doesn't need to resize anything. The last object simply assigns it's own "next" pointer to the newly added object. On an erase, only two pointers change info.
- A list does (fix me if I'm wrong) allocate X bytes (in my case it's 4bytes, because I store pointers) on a push() and frees those bytes on an erase().

So the question is, and I think the answer is a negative - can this lead to memory fragmentation somehow?
You know, 4 bytes allocated here, 4 bytes allocated there, the older ones are freed, then re-allocated...

I think it's not simply because the size if fixed, and besides, it's "only" a 4 bytes allocation each.


P.S
Only way to avoid it as I can think of is simply derive my class from a "class Node" which has preceding/next pointers and that's it..


Thank you again!

[STLDude]

f I removed an object from the middle of the collection, say position 5, the vector library will have to copy all the objects after position 5 to the position 5 (object 6 becomes 5, object 7 becomes 6, etc'),

No, you can use swap and pop.

[mikoil]

Can you be a bit more specific?
You're saying that there's a way to avoid the vector "reCopy" behaviour by swapping the object I want to remove with the first or last object?
But then again, when the vector gets to be 5 objects for example after being 100 objects, it will reLocate at a smaller memory, no?
If I could avoid the shrinking step maybe that would give better results than "list".

[kempofighter]

In details, I have this "list" object which stores pointers to a custom class I've made.
So pointers are added, and then removed after a while.

Hi all and thanks for the attention!

I think my point has been slightly missed;

The program allocates, say, 100 instances of class myClass (which will not be freed until the program ends!).

I'm confused. First you say that you are deleting the pointers from the list but the objects aren't deleted until the program ends. How are you preventing memory leaks? This is why you should post some code when asking a question this complex so that we can see a small example of what you are trying to do.

Memory fragmentation is a complex issue. Do you think that you can do better than the std library implementors? If so try to write your own memory allocator that will prevent fragmentation. You've stated that you are only dealing with pointers. Pointers require very little memory. If you were storing actual objects in the container, that is a different story. So which is it? By the way, the purpose of a linked list is fundamentally different from the purpose of a vector. They are not substitutes for each other in my mind. You either need a linked list or you don't. A deque does not store elements contiguously as a vector does. If you are only worried about too much copying after removing an element either use a deque or try the swap/pop method with the vector.

Also, with vector or deque you can certainly use the reserve function to cause it to preallocate enough memory that will prevent reallocations from occuring. if you have some idea of how many elements the container will ever need, you can reserve memory upfront. This way you won't have to worry so much about fragmentation because the container will allocate a big chunk up front and simply work within the bounds of that until it needs more. I recommend picking up a copy of Effective STL by Meyers.

[laserlight]

You're saying that there's a way to avoid the vector "reCopy" behaviour by swapping the object I want to remove with the first or last object?

You would swap with the last, not the first, so you can pop_back() the last.

But then again, when the vector gets to be 5 objects for example after being 100 objects, it will reLocate at a smaller memory, no?

No, it is not guaranteed to reduce the amount of memory used, but you can copy the vector to a temporary and then swap it with the temporary if this is a problem.

[kempofighter]

But then again, when the vector gets to be 5 objects for example after being 100 objects, it will reLocate at a smaller memory, no?
If I could avoid the shrinking step maybe that would give better results than "list".

A follow-up question for one of the stds gurus here is this. If the number of elements in the vector shrinks does the std require that the vector keeps the memory? Or is this implementation dependent?

You want the vector to have more memory then it really needs (via the reserve function) so that it doesn't have to allocate / deallocate the memory it needs. Reserve slightly more memory then you think you will need. I would hope that if the vector gets smaller and bigger that the capacity won't change until more memory is needed. If less memory is needed the vector shouldn't be deallocating. That defeats the purpose of the reserve call in my mind.

[laserlight]

If the number of elements in the vector shrinks does the std require that the vector keeps the memory?

It does not appear to be explicitly stated, but consider: both versions of erase() only invalidate iterators and references to elements after the point of the erase. This means that reallocation cannot happen, otherwise iterators and references to elements before the point of the erase will also be invalidated. Likewise, v.pop_back() should not cause reallocation, since it has the same operational semantics as v.erase(--v.end()) for some vector v.

[Paul McKenzie]

A follow-up question for one of the stds gurus here is this. If the number of elements in the vector shrinks does the std require that the vector keeps the memory? Or is this implementation dependent?

From what I understand, vector's internal memory buffer can only grow, and never shrink, unless the vector is destroyed (where the internal memory is also destroyed).

Regards,

Paul McKenzie

[laserlight]

Oh, and that reminds me: resize() to less than the current size has the same effect as using erase() appropriately, which in turn means that reallocation cannot happen. I think that just about covers all the cases, so reallocation does not occur for a reduction in size for std::vector, hence the copy (or default construct) and swap idiom that I mentioned in post #10 really would be needed if shrinking the capacity was desired.

[mikoil]

Ok, so let's conclude:

If I go on a vector then it will only grow, never shrink, correct?

Now, let's say the vector now has those integer values (each takes 4 bytes):
11, 22, 33, 44, 55.
Now during an iteration, I found '33' and just "erase()" it.
What would happen internally?

Option 1:
The values "44, 55, would be copied each to a preceding position, e.g "44" to where "33" was and so on.

Option 2:
Is there any? How does it work then?


Now assuming Option 1 is the correct one and this is really what happens internally, how would I avoid all this copying?
On suggestion, from what I understand, is to swap between "33" and "55", and then remove, then all the vector will do is cutting the array at the end, with no need to copy all.

Anyone follows?