Archived

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

STL Woes

This topic is 5975 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

I'm working on an C++ OpenGL hirearchy that I plan to use to create some Borland C++ Builder components for developing tools. It's for work right now, but I'll eventually use it in some of my real game tools. Well, being that it's for work, others will be looking at it, so to reduce the learning curve of how things work internally, I'm using the STL. Basically, my question comes down to: How do I search a std::list of pointers to structures using a member of the structure as a key? I can do it the hard way, i.e. creating my own iterator and traversing the entire list, but isn't there some function in that I can use for this, similiar to find()? The list is similar to what follows follows:
       
struct TStruct 
{
    TMember1* Member1;
    TMember2* Member2;
};
std::list<TStruct*> StructList;  
  
How do I search through it to find the list node that contains a given key of type TMember1*? I have Stroustrup's book, and I'm sure I'll be able to find it in there, but while I'm looking I figured I might as well just post here, as someone probably knows off the top of his or her head. Thank you for your bandwidth. -- Succinct ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Edited by - Succinct on August 1, 2001 2:59:06 PM

Share this post


Link to post
Share on other sites
use find_if and supply your own predicate that compares the dereferenced pointer:
  
struct FunctorFindTMember1
{
bool operator (const TStruct *pLhs, const TMember1 *pRhs) const
{
return pLhs->Member1 == pRhs;
}
};

//... in code, where TMember1 *val = key you''re looking for

it = find_if (StructList.begin (), StructList.end (),
bind2nd (FunctorFindTMember1, val));

Might be a little rough around the edges since I didn''t compile this, but that''s the idea.

PS: I''m sure you have already, but check that a map wouldn''t be more appropriate (your use of the word "key" and searching linearly through the list forces me to ask. =) )

Share this post


Link to post
Share on other sites
Well, actually I'm implementing a tree, e.g. lists of lists.

I tried using a map, like you'd figured, but I was running into problems using maps in Borland Builder when using typed pointers as the key because you can't overload the < operator for them (which is necessary for maps, why the compiler wasn't using just the <(void*,void*) operator is beyond me).

Instead of going too far into the diagnosing the symptoms and prescribing a solution, I decided that using lists would work fine and they don't need the < operator defined. My reasoning was that, though there are a lot of lists, each list will only be holding a few items, on average between 1 and 8 or so, and searching through a list of this size won't cause much of a performance hit (vs. maps) for the work being done here.

Besides, I figure that this is just a rough, quick and dirty implementation that I'll optimize later when I have more time for it, and, being that this is the STL and most of the operations I'm performing on them can be performed on any STL container, switching to maps should be pretty easy when I figure out what the heck is wrong.

Thank you for your time. I'll be trying this tomorrow at work.
-- Succinct

Edited by - Succinct on August 1, 2001 8:01:10 PM

Share this post


Link to post
Share on other sites
Hashmap is maybe something you need. Stl does not have them but they are very common and come as extentions on some Stl implementations. A hashmap is an array of pointers to a short linked lists. Basicaly an unique id is calculated for each item and its position can be found with a hash function. This gives for fast searching.

Share this post


Link to post
Share on other sites
If map won't work for borland, hashed map won't work.

When I've made maps of pointers as the keys, I just used my own predicate in the map that compared the pointers. I think your problem is that the syntax is fairly tricky. I wrote this template (cleverly called PLess) to solve it:
      
// PLess defines predicate template that sorts pointers by their

// objects less-than operator rather than the values of the pointers

template<class T>
struct PLess : public std::binary_function<T, T, bool>
{
bool operator () (const T& x, const T& y) const
{ return *x < *y; }
};

// example usage:

map<MyClass*, Whatever, PLess<MyClass*> > myMap;

All you need is an operator < for MyClass and you're set (no pun intended).

Edited by - Stoffel on August 1, 2001 8:42:41 PM

Share this post


Link to post
Share on other sites
felix9x:
Well, still, though, I''m building a tree, lists of lists, and not just a list (singular) of lists. A hash of lists would still be only 2 dimensional. My tree is set up similar to (if I can remember, as my code isn''t on this box)
  
struct TTreeNode; // forward dec for use in circular reference

typedef std::list<TTreeNode*> TTreeListBranch;

struct TTreeNode
{
TMember* MemberPointer;

TTreeListBranch ChildBranch;
};

TTreeNode m_TreeRoot;


A hash wouldn''t provide this functionality directly w/o suffering from the same pointer indexing problem as regular maps.

Stoffel:
Ohhh, yeah, you''re right... the 3rd parameter allows you to specify a function object used in the comparisons...

Thank both of you!

-- Succinct

Share this post


Link to post
Share on other sites
Maybe a multimap might be what you''re looking for.

Its like a map except that instead of one value per key, you basically have a list of values.

I think the Borland Documentation there''s mention of how to implement a Tree using STL components.

Also, if you''re looking for a more generic graph structure, check out www.boost.org

There''s a bunch of cool stuff there - written by some of the major contributers to the C++ language.

Share this post


Link to post
Share on other sites