• Advertisement
Sign in to follow this  

Pointers and STL find() function.

This topic is 2992 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Let's say I have a class XYZ, and a list of pointers to objects of class XYZ. So, list<XYZ*> myList; I want to look through this list for a specific XYZ object. So: XYZ *test; list<XYZ*>::iterator it; it = find(myList.begin(), myList.end(), test); However, that doesn't search for equivalent objects. It searches fore equivalent pointers. So, if it's even possible, how would I use find on a list of pointers to look for the actual object that's being pointed to? I tried find(*(myList).begin(), *(myList).end(), *test), which didn't give me any compiler errors, but it = couldn't handle it (I'm guessing either because it returned the wrong kind of iterator, or the pointer wizardry there is completely wrong).

Share this post


Link to post
Share on other sites
Advertisement
Use a functor template that does the dereferencing internally:

template<typename T>
class dereference
{
T* pointer;

public:

dereference(T* p) : pointer(p) {}

bool operator()(T* p)
{
return *p == *pointer;
}
};

// ...

it = find_if(test.begin(), test.end(), dereference<XYZ>(test));


If you don't want to supply the template argument yourself, you can build a helper function:

template<typename T>
class dereference_t
{
T* pointer;

public:

dereference_t(T* p) : pointer(p) {}

bool operator()(T* p)
{
return *p == *pointer;
}
};

template<typename T>
dereference_t<T> dereference(T* p)
{
return dereference_t<T>(p);
}

// ...

it = find_if(test.begin(), test.end(), dereference(test));


[Edited by - DevFred on December 4, 2009 5:16:50 AM]

Share this post


Link to post
Share on other sites
The facility DevFred outlined is available in the boost lambda library. Something like this should do the trick:


using boost::lambda::_1;
it = std::find_if(b, e, *_1 == *myXYZ);


EDIT: alternatively, just use std::list<XYZ> rather than hold the objects by pointer. You seem to be early on in the game as far as your C++ career is concerned, so I feel obliged to point out that this would usually be considered as a more normal thing to do.

Share this post


Link to post
Share on other sites
All objects of type XYZ are created at run time. Wouldn't I need it to be a list of pointers so that I could use new..?

Anyway, just for testing purposes, I posted your functor code verbatim and changed the find arguments.

So, declaration for the objects, here:

const list<SpriteSheet*> &artAssets (This is an argument, of course)
list<SpriteSheet*>::const_iterator ait;
SpriteSheet *test;

And calling find:

ait = find(artAssets.begin(), artAssets.end(), dereference<SpriteSheet>(test));

Is still giving me the following errors, which I would get a result of just passing in *test.


|n function `_InputIterator std::find(_InputIterator, _InputIterator, const _Tp&, std::input_iterator_tag) [with _InputIterator = std::_List_const_iterator<SpriteSheet*>, _Tp = dereference<SpriteSheet>]':

instantiated from `_InputIterator std::find(_InputIterator, _InputIterator, const _Tp&) [with _InputIterator = std::_List_const_iterator<SpriteSheet*>, _Tp = dereference<SpriteSheet>]'

error: no match for 'operator==' in '(&__first)->std::_List_const_iterator<_Tp>::operator* [with _Tp = SpriteSheet*]() == __val'




And I do have operator == overloaded on the SpriteSheet class, although maybe I did that wrong:


bool operator==(const SpriteSheet &rhs) const
{ if (this->sheetName == rhs.sheetName) {
return true; }
else { return false; }
}


So, uh, what am I doing wrong..?

--edit--

Getting the same issue with the boost::lambda thing.

[Edited by - MeshGearFox on December 4, 2009 12:01:17 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by MeshGearFox
All objects of type XYZ are created at run time. Wouldn't I need it to be a list of pointers so that I could use new..?

No, observe:

list<pair<int, double> > myList;

// function style constructor, template parameters necessary
myList.push_back(pair<int, double>(42, 42.0));

// helper function, no need for template parameters
myList.push_back(make_pair(42, 42.0));


Quote:
Original post by MeshGearFox
And calling find:

You need to call find_if, not find.

Quote:
Original post by MeshGearFox

bool operator==(const SpriteSheet &rhs) const
{ if (this->sheetName == rhs.sheetName) {
return true; }
else { return false; }
}


No need for the if/else, the result of the comparison is already the result you are interested in:

bool operator==(const SpriteSheet &rhs) const
{
return this->sheetName == rhs.sheetName;
}

Share this post


Link to post
Share on other sites
Ahh, thank you. Didn't see the _if there, for whatever reason.

As for your second example, I guess I just admit the new command. I was... not aware that I could do that! Interesting! I'll go restructure some things real quick here.

Share this post


Link to post
Share on other sites
Quote:
Original post by MeshGearFox
I guess I just admit the new command. I was... not aware that I could do that!

You probably have a programming background in programming languages where new is the only way to create an object (Java for example).

Share this post


Link to post
Share on other sites
Quote:
As for your second example, I guess I just admit the new command.


Brief addendum: I have absolutely no idea what this means, or what it was supposed to mean.

Also, this in general involved way too much fiddling around. See, the objects have a string name member that store's the strings name, and then a public accessor. What I WANTED to do was search through my list of objects based on the string name, which doesn't really work with find, and would work with find_if if I screwed around with the lambda functions a bit.

Or, the other option was to just look up the STL source code for the find functions, copy them into one of my own headers, and change them to do what I wanted. Which took all of five minutes.

And now I feel stupid :)

[Edited by - MeshGearFox on December 4, 2009 10:23:25 PM]

Share this post


Link to post
Share on other sites
On a side note, why are you storing pointers to the objects rather than the objects themselves? There are very few good reasons to do that.

Share this post


Link to post
Share on other sites
Quote:
Original post by MeshGearFox
Quote:
As for your second example, I guess I just admit the new command.


Brief addendum: I have absolutely no idea what this means, or what it was supposed to mean.
I figured it meant he liked doing return this->sheetName == rhs.sheetName; better than the if/else. That is a strange way to say it if that is what he meant though.

edit: I didn't realize you were the one who said both things! Hilarious.

Share this post


Link to post
Share on other sites
Okay, wow.

The program was NOT calling the find template function I wrote. It was calling the STL find function. And working in the same way the one I wrote was supposed to.

Except it was working with one class that didn't have properly overloaded operator== functions to support... what I think I was doing.

Which was using a string as the thing I was searching for in the find function call.

Now, seriously, I can pass off my earlier confusion about what I needed to pass in to find as a result of me misunderstanding the pointers, and why I didn't need to store list of pointers to dynamically allocate objects. Fine.

That still doesn't explain what the deal with the overloaded operators is.

Now I'm very, very deeply confused. I'll post the code sometime later when it's cleaned up a bit.

Share this post


Link to post
Share on other sites
Quote:
Original post by MeshGearFox
See, the objects have a string name member that store's the strings name, and then a public accessor. What I WANTED to do was search through my list of objects based on the string name

If you want to map strings to objects, you can use a map.

#include <map>
#include <string>
#include <utility>

using namespace std;

class Object
{
int i;
double d;

public:

Object(int i, double d): i(i), d(d) {}
};

int main()
{
map<string, Object> myMap;
myMap.insert(make_pair("foo", Object(4711, 3.1416)));
myMap.insert(make_pair("bar", Object(123, 9.81)));

// ...

map<string, Object>::iterator it = myMap.find("bar");
if (it != myMap.end())
{
Object& o = it->second;
// process object
}
else
{
// object not found
}
}

Share this post


Link to post
Share on other sites
That would work, although the GameData and ArtAsset sets should remain small enough that using the O(N) algorithm find() shouldn't really be much slower than the O(logN) map::find(), unless map's find function has some other optimizations I'm not aware of. Additionally I'd kind of like to keep the name identifier string as part of the GameData and ArtAssets class.

However, map would probably be a lot more efficient for another set of objects I'm using (which are identified by integer values that don't really need to be an atomic part of that class). I'll switch over to that eventually.

Anyway.

Back to my other questions about find. I went back and looked at the source code again and it's behaving predictably. I'm going to assume I was just tired last night and misreading what I'd written.

Share this post


Link to post
Share on other sites
Quote:
Original post by frob
On a side note, why are you storing pointers to the objects rather than the objects themselves? There are very few good reasons to do that.


Eh, I wouldn't go that far. Pointers are often smaller than value types, leading to less copying (more important in the case of a vector, for example, but still a consideration). Furthermore, I think it's actually quite common to have data stored in multiple places.

For example, suppose you have a global list of objects, and then for ease of access a list of all "interesting" objects. You'd want to store pointers in both cases so that if it changes in one list it changes in the other list.

Obviously this is a trivial example, but personally I find myself using collections of pointers more often than collections of values. The biggest drawback to collections of pointers (especially with vectors) is that you get far better cache performance on collections of value types. But there's always tradeoffs and I use both methods all the time.

Share this post


Link to post
Share on other sites
Actually, you gave me an idea.

Each instance has an ID and draw order. Could I potentially have a list of Instance objects in some arbitrary, unordered arrangement, and then two maps of integers to Instance *pointers*, which would be pointing at the Instance objects in the original list, so that I could have a way of iterating through my Instances both in order of ID and draw order? Sort of using map like a hash table, maybe?

(I thought about having a vector if Instance objects indexed by their IDs, but that doesn't really work out since it'd be quite possible to end up with a large and largely empty vector of a few objects with low IDs and a few objects with high IDs, and nothing in between because they all got removed for various reasons).

Share this post


Link to post
Share on other sites
So, I switched the lists over to lists of objects instead of lists of pointers. So, now I have a list of GameData instead of GameData*.

However, I want to add an object of a child class of GameData to the list. It lets me, but when I try to call some of the functions of the derived class it calls the virtual functions from the base class instead.

Can I get it to call the child class's overriding functions instead, or do I need to go back to a list of GameData pointers?

---edit---

Actually I could probably just use function pointers or functors here instead of fiddling with polymorphism. That would be a lot easier, especially since the only class being derived from GameData is player, and the only reason I'm doing that is because the movement code is part of the player instance/data group, and there's not easy way to offload that to lua.

And if I needed to "derive" other classes later (In reality, create different update() function functionality), while I'd still need some form of RTTI, it'd be a lot easier to handle as I could just store my behavior function pointers in an array and then use RTTI to access the array. So, I'd still have RTTI, but the functions wouldn't be endless, ugly chains of if/else statements.

Hm...

[Edited by - MeshGearFox on December 9, 2009 2:43:50 AM]

Share this post


Link to post
Share on other sites
Quote:
It lets me, but when I try to call some of the functions of the derived class it calls the virtual functions from the base class instead.
It sounds like your objects are getting sliced.
Quote:
Can I get it to call the child class's overriding functions instead, or do I need to go back to a list of GameData pointers?
Since your objects are polymorphic, you'll probably need to go back to storing pointers.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement