::std::list::push_back()

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!

:wave:

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.

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).

Quote:

---

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

Quote:

---

Originally Posted by mikoil

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:

Code:

---

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 :

Code:

---

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

---

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

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! :)

Quote:

---

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.

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".

Quote:

---

Originally Posted by mikoil

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.

---

Quote:

---

Originally Posted by 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!).

---

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.

Quote:

---

Originally Posted by mikoil

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.

Quote:

---

Originally Posted by mikoil

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.

Quote:

---

Originally Posted by mikoil

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.

Quote:

---

Originally Posted by kempofighter

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.

Quote:

---

Originally Posted by kempofighter

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

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.

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? :)

Quote:

---

Originally Posted by mikoil

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? :)

---

Consider the std::deque as well.
http://www.cplusplus.com/reference/stl/deque/

You never did describe, in detail, what your custom class is. Therefore it is hard to imagine which container will work best for you. Also, you indicated that you are storing pointers to objects so I am unclear on what the fuss is all about with regards to copying and memory fragmentation. The list could work for you but again I am unclear on what your custom class is for. Lists have a more significant difference from vectors than do deques but that may not matter. I have no idea what your program does. Unless you tell us you'll have to analyze the three types of containers and figure it out.

Hello KempoFighter and thanks (to everyone as well!!).

Well, in general yet very specific:
In the start of a program I allocate a bunch of objects.
I use them over and over until the program ends.

Guessing what type of program would do that be? :)


.... I'd love to tell but I'll let you think of it by yourself, or maybe another person here will find it. Not too hard :)
Of course since you're trying to be so helpful, I'll let you know!

Anyway I think I understood the issue here - none really knows how STL list/vector works from the inside... or maybe they didn't see the last post I had (above yours, fighter)... Because my question has nothing to do with what I intend to do with the collection - it's a simple case where I want to re-use objects. That's it.

Quote:

---

...none really knows how STL list/vector works from the inside.

---

Wrong, most experience people do know that, or more to the point that you do not need to know internal workings of stl vector but performance characteristics which is the most important thing when you decide which container to use. All this information is available if you search. Even in one of my post I provided link to big Oh notation for stl containers, which you should know it before deciding which one to use.

Quote:

---

In the start of a program I allocate a bunch of objects.
I use them over and over until the program ends.

---

You are not explaining very well, do you just allocate at start up all the objects or do you add/remove them during runtime, do they need to be sorted, do you just add to the end or in the middle, etc. Do you see how many questions there is just to figure out what exactly your needs are?

It appears that you do not understand stl container, so you should hit the books and read on some more rather then just shoot the wall and see what sticks.

Quote:

---

Originally Posted by mikoil

.... I'd love to tell but I'll let you think of it by yourself, or maybe another person here will find it. Not too hard :)
Of course since you're trying to be so helpful, I'll let you know!

Anyway I think I understood the issue here - none really knows how STL list/vector works from the inside... or maybe they didn't see the last post I had (above yours, fighter)... Because my question has nothing to do with what I intend to do with the collection - it's a simple case where I want to re-use objects. That's it.

---

Then, I guess you are on your own from here. Nobody here, so far as I know, is clairvoyant. I don't understand the second sentence. You still haven't given us any relevant details that would help us understand what you need!

Actually, many of us have told you exactly how STL vectors work on the inside. The problem is that you are too vague in describing your requirements. The questions on memory management has everything to do with how you intend to use the collection, since the three containers in question manage themselves in totally different ways!

STL vectors work in the obvious way, really. They double their capacity and copy each time they run out of space. That's pretty much the entire algorithm.

Quote:

---

Originally Posted by Lindley

STL vectors work in the obvious way, really. They double their capacity and copy each time they run out of space. That's pretty much the entire algorithm.

---

Good.
But how does the algorithm work when I remove an object which is in the middle of the collection?


Anyway, to be EXACT as some folks asks:
It's a TCP server program.
On each new connection, an object (let's call it class "Client") is being pulled out of the pre-allocated pool, and assigned to the new connection.

Therefore, when a client disconnects, I do not "delete" the object but I memset() it to 0x00, and I put it back in the pool.

This is just about it when I say I want to avoid memory fragmentation.

Now, besides that I have a worker thread that checks for scheduled tasks concerning the server's operation (it's a game server).

What kind of operations?
For example a time-out operation. A client has X seconds to act (in a certain state of the game), otherwise, if he didn't react, he's out of the game.

So when the game advances, a new checking task is being submitted to the time-out-thread-checker.
This thread iterates between the tasks.
When X seconds has passed and the thread iterated to this task, it checks for this and that.
If the conditions are met, the task should be removed from the collection.

Very simple to understand I think, and hope.
I'm really trying to cooperate. :p

So, I understand that vector will resize itself when I add new tasks.
But what happens when I erase a task? Would shrink, ever? Would it copy all the following tasks in the array to a new position?

I'm looking for as less as possible operations of relocation to be made because as I said, it might be few hundreds of tasks each iterations.

By the way:
Each task is actually a class which describes that task.
This is why inside the collection I'll only store pointers, because as in the Client objects, I allocate many task object at the start of the program and re-use each one.


I really hope I'm clear on that now.
I not then god mercy :D

Quote:

---

Originally Posted by mikoil

Good.
But how does the algorithm work when I remove an object which is in the middle of the collection? .... Would it copy all the following tasks in the array to a new position?

---

Of course, just like you'd need to do with an array.

Quote:

---

Would shrink, ever?

---

No. You need to use the "swap trick" to get a smaller-capacity vector if you want one.

Quote:

---

Therefore, when a client disconnects, I do not "delete" the object but I memset() it to 0x00, and I put it back in the pool.

---

It's dangerous to use memset, or memcpy for that matter, with C++ objects. It will only work with plain-old-data ones. Avoid those functions. (std::copy and std::fill are the replacements.)

Quote:

---

I'm looking for as less as possible operations of relocation to be made because as I said, it might be few hundreds of tasks each iterations.

---

If you're going to have lots of inserts and deletes, you may wish to consider a map or set. Lists provide constant-time insertion, of course, but in order to delete a specific element (that you don't already have an iterator to) you need to do a traverse of the entire thing. Using a tree-based data structure would alleviate this.

Quote:

---

Originally Posted by mikoil

Therefore, when a client disconnects, I do not "delete" the object but I memset() it to 0x00, and I put it back in the pool.

---

:eek: Alarm bells start ringing in my head when I see memset mentioned in connection with C++ code. We once had an insidious little bug caused by one developer who had a habit of using memset to initialise his structures.

Hehe, now the two of you made me nervous about something I didn't even come for (memset!) :)

What's the "swap trick", in few words please? Note that I'm not looking for a small vector but for a collection that will not need to copy the rest of the elements, starting from the erased one, to a preceding position.
What I do think is that with a vector collection, as you guys say, I might "swap" the to-be-erased element with the last element and then erase.
That way, the elements between won't have to move. Correct or wrong? I'm gonna look at it very soon myself anyway.

By the way:
I understand that "swap" means swapping the elements with/to another vector object, but when I say "swap" I simply mean replace the two values :)

For the last comment of Lindley - so it seems that a linked list would also work fine for me because as I said, a deletion would occur only in the process of an iteration.

So now to decide I think that the only thing I want to know is regarding what I wrote a bit above, in this post - will "swapping" between the in-the-middle to-be-erased element with the last element of the vector avoid reCopy of the rest of the elements?

Quote:

---

Originally Posted by mikoil

What's the "swap trick", in few words please?

---

As I mentioned earlier: create a temporary vector that is a copy of your current vector, then swap it with your current vector.

Quote:

---

Originally Posted by mikoil

What I do think is that with a vector collection, as you guys say, I might "swap" the to-be-erased element with the last element and then erase.
That way, the elements between won't have to move. Correct or wrong?

---

Correct.

Quote:

---

Originally Posted by mikoil

So now to decide I think that the only thing I want to know is regarding what I wrote a bit above, in this post - will "swapping" between the in-the-middle to-be-erased element with the last element of the vector avoid reCopy of the rest of the elements?

---

Yes, it will avoid the copying of the other elements.

Ok, I got my answer for this case.
I'm gonna use a vector because it can get only bigger, and allocation of new memory would stop at some point, after running the program.

To prove this I made the following code, just for anyone who's gonna read this thread some day, if at all :p

Code:

---

#include <vector>
#include <stdio.h>
#include <conio.h>

class someClass
{
public:
    int nVal;
};

void main()
{
    ::std::vector<someClass*> vec;

    someClass *scObj;

    for(int i = 0; i < 1000; i++)
    {
        scObj = new someClass();
        scObj->nVal = i + 1;
        vec.push_back(scObj);
    }

    printf("%d\n", vec.capacity());

    for(::std::vector<someClass*>::iterator itPos = vec.begin(); itPos != vec.end(); NULL)
    {
        scObj = *itPos;

        //printf("%d\n", scObj->nVal);

        if(scObj->nVal != -1)
        {
            itPos = vec.erase(itPos);
        }
        else
        {
            itPos++;
        }
    }

    printf("%d\n", vec.capacity());

    _getch();
}

---

And.. thanks a lot all !!