Jump to content
  • Advertisement
Sign in to follow this  
Andrew Russell

STL Set Question

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

OK folks, STL hats on! Question time: Say I have a class like this:
class X
{
    Identifier name;
    
    class Traits
    {
    public:
        static const size_t bucket_size = 4;
        static const size_t min_buckets = 8;
        size_t operator()(const X& k) const
            { return k.name.Hash(); }
        bool operator()(const X& k1, const X& k2) const
            { return (k1.name.Compare(k2.name) > 0); }
    };
};

// And then when I want to make a set of these:
std::hash_set<X, X::Traits> somestuff;

Now, the thing is, I'd like to access memebers of this set using just Identifier objects. Creating an empty X object each time isn't suitable. It'd be good if I could overload the trait functions to also accept Identifier objects, but then, I don't think is this even possible? Perhaps it can be done in another way? A map would work, however that is not a great solution, particularly because it would store the identifier twice. Then again, is a map the "correct" solution? Or is there another way of doing this I have not thought of? Cheers, AR

Share this post


Link to post
Share on other sites
Advertisement
Looks like keying on the Identifier is probably the best solution. I'm not sure I'd be worried about having to store the Identifier twice, but then again I don't know the context. As for your other suggestion (the second paragraph) it wasn't really clear what you meant.

Share this post


Link to post
Share on other sites
Well, there's no reason that the comparison functions in the Traits class couldn't accept Identifier as an argument as well. But the container itself can't... Can it?

Share this post


Link to post
Share on other sites
I think hash_map is the best solution here.
Definately the only sane one.

Unless you want to rewrite a hash_set class for one overload.

edit: on further thought you might be able to write an adapter class for hash_set quite easily for this problem but since i dont use hash_xxx so i cant be certain.
But you would probably need to go change hash_sets access rules which is just bad.
edit#2: Ignore everything but the first line.

[Edited by - Amnesty on November 26, 2004 4:10:14 AM]

Share this post


Link to post
Share on other sites
Why don't just have one default overloaded equality operator for your X class and a functor for finding Xs that match a certain identifier type, with STL algorithms (& some ops for containers) you have choice to provide alternative free/member functionr or functors:


#include <cmath>
#include <algorithm>
#include <hash_set>

template < typename T >
struct hash {
size_t operator()(const T& x) const { return 0; }
};

struct Identifier {
size_t Hash() const { return rand(); }
bool Compare(const Identifier&) const { return true; }
};

struct X;

template <>
struct hash<X> {
size_t operator()(const X& s) const {
return s.name.Hash();
}
};

struct X {
Identifier name;

bool operator==(const X& x) const {
return name.Compare(x.name);
}
};

struct identifier_equal {
const Identifier& id;

identifier_equal(const Identifier& _id): id(_id) {}

bool operator()(const X& x) const {
return x.name.Compare(id);
}
};


int main() {

std::hash_set< X, hash<X> > foo;

//...

if(std::find_if(foo.begin(), foo.end(), identifier_equal(Identifier()) != foo.end())
//...
else
//...
}


[Edited by - snk_kid on November 26, 2004 5:23:02 AM]

Share this post


Link to post
Share on other sites
Seeing as hash_set is one of the non-standard container classes, then you'll have to specify which hash_set implementation you are using. It could be that the one you have templated the member find operation to accept non-key types in searching.

Alternately you can hack your STL header to template the member find operation.

Or you can keep a dummy X object around and just overwrite the identifier every time you need it. That should be less expensive than creating a new X everytime you need to do a lookup.

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!