Archived

This topic is now archived and is closed to further replies.

barazor

more efficient delete?

Recommended Posts

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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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;
}

Share this post


Link to post
Share on other sites