Finding/Searching in std:list

[irfan2266]

Write your question here.

Hello All,

Problem description:
1) I have a list of ClientInfo objects getting updated using std::list. You can see the registerToMaster() below
2) Similarly i want to unregister and the input i get is clientID as argument. Now i want to search the ClientInfo object whose data member (clientID) matches the client ID provided as argument.

I am stuck in second point. Please let me know if there is any find API or algorithm to do so.

class ClientInfo
{
    public:
        ClientInfo();
        ~ClientInfo();

        U32 msgId;
        U32 cleintID;    /* This is treated as client ID */ 
        U32 timeout;
        U32 gracePeriod;
};


void Master::registerToMaster(ClientInfo& clientInfo)
{
    std::list<ClientInfo*>::iterator itr;

    // Keep inserting the registered clients at end of list 
    itr = ClientList.begin();
    while (itr != ClientList.end())
    {
        itr++;
    }
    ClientList.insert(itr,&clientInfo);
}

void Master::unregisterFromMaster(U32 clientID)
{
     /*search the cleint ID - ???????? */
     /*remove the client from registered list - I am clear about this part*/
}

[LB]

Why are you using a std::list to hold pointers? You should use std::vector for this, it will make your life easier.

[irfan2266]

Yeah i can use vectors instead of list, but still query would be same :) Hw i am going to search on basis of clientID ? If u could provide me pointer on query and enlighten my limited knowledge on list and pointer it would be gr8 :)

[LB]

If you had a filing cabinet with folders in it and papers in those folders that had IDs on them, how would you find the folder with the paper with the ID on it?

Go through each one, open the folder, grab the paper, and look at the ID. Does it match? No? Keep going. Yes? Erase it, and maybe stop looking if you know that the ID exists only once in there.

[Catfish4]

Why are you using a std::list to hold pointers? You should use std::vector for this, it will make your life easier.

How so?
My personal rule of thumb is: if you don't need elements to be allocated contiguously in memory then use std::list instead of std::vector.

As for the OP's code:

First you don't need to iterate at the end just to insert something at the end.
Use list::push_back() instead.
http://www.cplusplus.com/reference/list/list/push_back/

void Master::registerToMaster(ClientInfo& clientInfo)
{
    ClientList.push_back(&clientInfo);
}

void Master::unregisterFromMaster(U32 clientID)
{
    // at this point I have to ask if std::list is the best choice of a container
    // what if more clients have the same ID?
    // otherwise, if it's guaranteed that a client ID will appear only once in the list...

    for (std::list<ClientInfo *>::iterator i = ClientList.begin(); i != ClientList.end(); ++i)
        if ((*i)->cleintID == clientID) // cleint/client typo???
        {
            ClientList.erase(i);
            break;
        }
}

http://www.cplusplus.com/reference/list/list/erase/

Edit: minor mistake.

[irfan2266]

// what if more clients have the same ID?

Thank you !!
Clients will not have same ID, Actually those are pid's..

[JLBorges]

void Master::registerToMaster(ClientInfo& clientInfo)
{
    // Keep inserting the registered clients at end of list
    ClientList.push_back( &clientInfo ) ;
}

void Master::unregisterFromMaster(U32 clientID)
{
    /*search the cleint ID - ???????? */
    /*remove the client from registered list - I am clear about this part*/

    const auto id_equal = [clientID] ( const ClientInfo* p )
    { return p->clientID == clientID ; } ;

    auto iter = std::find_if( ClientList.begin(), ClientList.end(), id_equal ) ;

    if( iter !=  ClientList.end() ) ClientList.erase(iter) ; // erase it
    else { /* not found */ }
}

If clientID is a key (unique, no duplicates), consider using a set with value semantics to hold the ClientInfo objects - std::set<ClientInfo> or std::unordered_set<ClientInfo>

[LB]

Catfish4 wrote:

How so?
My personal rule of thumb is: if you don't need elements to be allocated contiguously in memory then use std::list instead of std::vector.

That's a bad rule of thumb, there's a difference between "don't need" and "need not". With primitive types especially you should not be using std::list.

Many sources recommend defaulting to std::vector and only using std::list when you need it. For example, Effective C++ says that std::vector should be your default type of container.

I haven't been able to research much on this particular issue though, so if you have some evidence it's better to use std::list over std::vector more often than not (or that using std::vector for holding pointers is not much more efficient than using std::list to hold pointers), please let me know so I can change my ways :)

[3qX21hU5]

It really all depends on your current situation to determine which container you should use.

Personally I think through the problem and try and determine what I need and what I am going to be doing before hand. If I need it to be really efficient with insertions and deletions I will use std::list.

If I need dynamic length and won't really be doing much insertions in the middle of the container I will use std::vector (Though if you know your "high water level" which is basically the maximum number of elements you could possibly have you should use std::array instead because it has less overhead).

If I need a event queue the obvious choice would be using std::queue (IE First in first out).

The point is there isn't really one default container for most situations (Though I will admit most of the time std::vector is used much more often then the others by most people) it should come down to whatever container works best for your situations and your needs (Performance wise and ease of use wise).

Hell sometimes you will need to create your own container for the job since none of the STL containers will work for your particular needs or they won't work well enough.

[LB]

Zereo wrote:

If I need it to be really efficient with insertions and deletions I will use std::list.

You forgot a step. You have to first think why you will be needing insertions and deletions. In many problems they can be avoided entirely even if they at first seem necessary.

I'm interested to know though which containers you had to create yourself because the STL was unsuitable? Exclude any related to hashes or efficiency.

[JLBorges]

Hmm... Echoes from this thread? http://www.cplusplus.com/forum/general/104953/

[3qX21hU5]

LB wrote:

I'm interested to know though which containers you had to create yourself because the STL was unsuitable? Exclude any related to hashes or efficiency.

In C++ I haven't really had a lot of need to create a custom container mainly because the work wasn't really worth the reward. So really I have only done it once or twice in C++ and I believe both of those times had to do with efficiency and specialization needs.

Though I have created quite a few in C# but I wouldn't really say most of them were "needed" just that they were more specialized for my task at hand and C# provides the features to make creating containers quite simple to do.

Can't really remember specific examples at the moment but will try and dig them up when I get off work.