::std::list::push_back()

[kempofighter]

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:eque 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.

[mikoil]

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.

[STLDude]

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

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.

[kempofighter]

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

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

[mikoil]

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.

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

[Lindley]

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.

Would shrink, ever?

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

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

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.

[JohnW@Wessex]

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.

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.

[mikoil]

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?

[laserlight]

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.

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.

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.

[mikoil]

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

#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();
}

[mikoil]

And.. thanks a lot all !!