Skip to main content
gamedev.net
🔒 Locked

more efficient delete?

Started by barazor 6 replies 400+ views
Original Post
barazor
barazor
i''m using a stl list, and the way im deleting objects is: 
  

    for (iter = packet.begin(); iter != packet.end(); ++iter)
    {
        if (iter->data == "world") break;
    } 
    packet.erase(iter);
packet is a std::list and iter is std::list::iterator as you can see, this doesnt exactly look like the most efficient way to delete items from my list, using find() wont work because it uses structs, anybody have any ideas?
Sneftel
Sneftel
There''s no way to search through a linked list in faster than linear time, so this is pretty much your best bet.

Note: if this is a std:list, this code snippet WILL NOT WORK. You need to use strcmp() to check for string equality.
Gorg
Gorg
quote:
Original post by Sneftel
There''s no way to search through a linked list in faster than linear time, so this is pretty much your best bet.

Note: if this is a std:list, this code snippet WILL NOT WORK. You need to use strcmp() to check for string equality.


Since barazor is using an std::list, I believe we can safely assume is data is an std::string object.
Sneftel
Sneftel
quote:
Original post by Gorg
Since barazor is using an std::list, I believe we can safely assume is data is an std::string object.


Agreed... gamedev stripped out the templated char * from my comment. Ooops.
barazor
barazor
actually, the struct in my list object is:

  
struct SomeType // forgot the name, lol

{
    int id;
    char* data;
}


my little delete function works fine, i was just looking for a better way
Oluseyi
Oluseyi
operator== on two char * is an interesting operation. See what happens if one of your data values is "water" (or even "w").

Then switch to STL string.
Grib
Grib
quote:
Original post by Oluseyi
operator== on two char * is an interesting operation. See what happens if one of your data values is "water" (or even "w").

Then switch to STL string.


actually what I bet he is doing is at some point creating a SomeType and saying a->data = "world"; This works in that it compiles, and in his tests it answers the question correctly, he is just asking a completely different question than what he thinks he is.

Switch to STL string, all the cool kids are doing it.
Stoffel
Stoffel
There are efficiency gains to be made here. First, end () might be recomputed inside the loop, so assign an iterator to end before you enter the loop and check aginst that.

There''s also an error, in that you don''t check to see that the search was unsuccessful (e.g. iter = end) before deleting.

But more properly, there is an algorithm that will accomplish this in STL, taking all the guesswork away from you:
  
#include <string>
#include <list>
#include <algorithm>

using namespace std;

// modifying type to use a string and to copy itself properly

struct Type
{
    Type () { }
    Type (const Type &org) : id (org.id), data (org.data) { }
    int id;
    string data;
};

// your old function, except using strings--not error is still there

void func1 (list<Type> &packet, const string &stg)
{
    list<Type>::iterator iter;
    for (iter = packet.begin(); iter != packet.end(); ++iter)
    {
        if (iter->data == stg)
            break;
    }
    packet.erase(iter);
}

// new way to do it: functors & algorithms

// This is the functor

struct FunctorIsStringInType
    : public binary_function<const Type, const string, bool>
{
    bool operator () (const Type &packet, const string &stg) const
    {
        return packet.data == stg;
    }
};

// This is the algorithm

void func2 (list<Type> &packet, const string &stg)
{
    list<Type>::iterator iter =
        find_if (packet.begin (), packet.end (),
        bind2nd (FunctorIsStringInType (), stg));
    if (iter != packet.end ())
        packet.erase (iter);
}

// test code

int main ()
{
    list<Type> packet;
    Type temp;
    temp.id = 0;
    temp.data = "hello";
    packet.push_back (temp);
    temp.id = 1;
    temp.data = "world";
    packet.push_back (temp);
    func2 (packet, string ("world"));

    return 0;
}

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.