Sign in to follow this  

std::set design issue

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

im having a problem with std::set ive got different sets where all the types inherit a class "Identifiable" with an std::string Id() function... looks somehting like this
struct IDCompare	
{ 
bool operator()(const IdentifiablePtr& lhs, const IdentifiablePtr& rhs) const	
{ 
return strcmp(lhs->Id().c_str(), rhs->Id().c_str())  < 0 ; 
} 
};

std::set<boost::shared_ptr<SomeType>, IDCompare>

however when i want to find an object in the set based on the "Id" i get into problems...
			template<typename T> 
			boost::shared_ptr<T> Find(const std::string& id) const
			{
				boost::shared_ptr<T> dummy(new T(id));
				SetType::const_iterator it = mySet.find(dummy);
				return it != Get<T>().end() ? *it : boost::shared_ptr<T>();
			}

i have to create a "dummy" object of the type in order to find the real object... these objects can be pretty large so i dont want to create a dummy everytime... the reason im using a set instead of a map is that i want to be able to use for_each functions and similar easily... how shoudl i go about this?

Share this post


Link to post
Share on other sites
struct IDCompare
{
bool operator()(const IdentifiablePtr& lhs, const IdentifiablePtr& rhs) const
{
return lhs->Id() < rhs->Id();
}
bool operator()(const IdentifiablePtr& lhs, const std::string& rhs) const
{
return lhs->Id() < rhs;
}
bool operator()(const std::string& lhs, const IdentifiablePtr& rhs) const
{
return lhs < rhs->Id();
}
};
...
std::string str("hi");
mySet.find(str);

Share this post


Link to post
Share on other sites

return strcmp(lhs->Id().c_str(), rhs->Id().c_str()) < 0 ;


This would be somewhat simpler as:


return lhs->Id() < rhs->Id();


As to the dummy, at least it doesn't have to be allocated dynamically. But perhaps a map would be better (do the objects even need to know their ID if the map could know that?)

Share this post


Link to post
Share on other sites
Quote:
Original post by visitor

return strcmp(lhs->Id().c_str(), rhs->Id().c_str()) < 0 ;


This would be somewhat simpler as:


return lhs->Id() < rhs->Id();


As to the dummy, at least it doesn't have to be allocated dynamically. But perhaps a map would be better (do the objects even need to know their ID if the map could know that?)


i think a map would work better... however there are problems when i want to use algorithms on the collection... since the map iterator works on key value pairs... do u know of any adapters for maps?

Share this post


Link to post
Share on other sites
Quote:
Original post by Dragon_Strike
there are problems when i want to use algorithms on the collection... since the map iterator works on key value pairs
What kinds of problems? It's just that it seems relatively easy to extract the value from a key-value pair?

Share this post


Link to post
Share on other sites
Quote:
Original post by incin
struct IDCompare
{
bool operator()(const IdentifiablePtr& lhs, const IdentifiablePtr& rhs) const
{
return lhs->Id() < rhs->Id();
}
bool operator()(const IdentifiablePtr& lhs, const std::string& rhs) const
{
return lhs->Id() < rhs;
}
bool operator()(const std::string& lhs, const IdentifiablePtr& rhs) const
{
return lhs < rhs->Id();
}
};
...
std::string str("hi");
mySet.find(str);


that doesnt work...?

cannot convert parameter 1 from 'const std::string' to 'const boost::shared_ptr<T> &'

Share this post


Link to post
Share on other sites
Quote:
Original post by dmatter
Quote:
Original post by Dragon_Strike
there are problems when i want to use algorithms on the collection... since the map iterator works on key value pairs
What kinds of problems? It's just that it seems relatively easy to extract the value from a key-value pair?


well the problem is that it adds complexity and makes it harder to work with... id rather add some extra code here than having to extract the value with every use case

EDIT:

another reason i want the objects to know their ids is that i can optimize it later by precaluclating a hash function and use that for lookups rather than running a hash function for each lookup...

[Edited by - Dragon_Strike on May 2, 2009 4:11:07 PM]

Share this post


Link to post
Share on other sites
Sorry, thought I did that before. But it obviously won't work, as find() must take a value_type. I'd also vote for using a map. You can always use helper functions to hide the map implementation.

Share this post


Link to post
Share on other sites
You need to use the right container for the job, and when the key is logically separate from the value, you use a map.

In your case, the value "knows" about it's own key, which is OK, but the key is obviouslly still logically separate, since you want to be able to search just on key.

Share this post


Link to post
Share on other sites
Quote:

But it obviously won't work, as find() must take a value_type.


And I thought I had learned something new...

Probably to make it more efficient with a set, you can avoid the dynamic allocation because boost::shared_ptr can also hold pointers to stack objects.

Share this post


Link to post
Share on other sites
changed to map...

ive written some helper functions... i hope someone else might find them useful



#pragma once

#include <string>
#include <algorithm>
#include <boost/iterator/transform_iterator.hpp>

namespace drone
{
namespace utils
{

template <typename T> struct wrap{};

template<typename C, typename F>
inline F for_all(C& c, F& f)
{
return std::for_each(c.begin(), c.end(), f);
}

template<typename C, typename F>
inline F for_all_values(C& c, F& f)
{
return std::for_each(utils::make_value_iterator(c.begin()), utils::make_value_iterator(c.end()), f);
}


template<typename C, typename F>
inline F find_if_all(C &c, F& f)
{
return std::find_if(c.begin(), c.end(), f);
}

template <typename T>
struct take_value
{
typename typedef T::value_type pair_type;
typename typedef pair_type::second_type result_type;

result_type operator()(const pair_type &pair) const
{
return pair.second;
}
};

template<typename T>
inline boost::transform_iterator<utils::take_value<T>, T> make_value_iterator(T it)
{
return boost::make_transform_iterator(it, utils::take_value<T>());
}

}
}




[Edited by - Dragon_Strike on May 2, 2009 6:10:44 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Dragon_Strike
return strcmp(lhs->Id().c_str(), rhs->Id().c_str())  < 0 ; 


Don't do that. std::string already provides perfectly good comparison operators.

return lhs->ID() rhs->ID();


Quote:

the reason im using a set instead of a map is that i want to be able to use for_each functions and similar easily...


You can do that just fine with a map. You just have to select the .second of whatever is passed to your Predicate and then do whatever with it.

Share this post


Link to post
Share on other sites
Quote:
Original post by visitor
Quote:

But it obviously won't work, as find() must take a value_type.


And I thought I had learned something new...
...



I was probably thinking about std::find() or std::lower_bound(), where this kind of thing would work. But, it's not going to help with a std::set.

Share this post


Link to post
Share on other sites
Quote:
Original post by incin
struct IDCompare
{
bool operator()(const IdentifiablePtr& lhs, const IdentifiablePtr& rhs) const
{
return lhs->Id() < rhs->Id();
}
bool operator()(const IdentifiablePtr& lhs, const std::string& rhs) const
{
return lhs->Id() < rhs;
}
bool operator()(const std::string& lhs, const IdentifiablePtr& rhs) const
{
return lhs < rhs->Id();
}
};
...
std::string str("hi");
mySet.find(str);

That would've been perfect solution if STL designers would have been as clever as that code. I tried that once too, and it didn't work.
It is actually a common problem. Very often, it is most sensible to have key as part of value itself; yet, you have to either put it outside and break encapsulation (which may be a huge problem when element has methods that require knowledge of key), or you have to duplicate it.

If not for this design mistake, std::map would have been just a derived class of std::set< std::pair<...> > There is no luck now pushing STL committee to change set::find to be a template :/ .

Share this post


Link to post
Share on other sites
Hmm, Boost.Intrusive looks good in principle (dunno about implementation). I may even try to actually use it. Though, generally, I'm very suspicious of boost's claims of high performance (never backed by benchmarks; real benchmarks on other hand show that boost's smartpointers for instance are rather slow).

Share this post


Link to post
Share on other sites
Quote:
Original post by Dmytry
(never backed by benchmarks; real benchmarks on other hand show that boost's smartpointers for instance are rather slow).
Which benchmarks show that? And which smart pointer implementations are faster - while still providing the same functionality - as boost's? Remember, the boost smart pointer library is more than just boost::shared_ptr. I having a feeling these "benchmarks" compare the performance of boost::shared_ptr with another implmentation of something like boost::intrusive_ptr...

Anyway, this is rather off-topic now...

Share this post


Link to post
Share on other sites

SetType::const_iterator it = std::find_if(mySet.begin(), mySet.end(),
boost::bind(std::equal_to<std::string>(),
boost::bind(&SetType::value_type::element_type::Id, _1),
id)
);



Not that I recommend using a set rather than a map (or hash map) if you need to look up by name.

Share this post


Link to post
Share on other sites
Codeka: dont forget thread safety. Smart pointers are nontrivial to implement quickly. Especially, weak pointers.
Quote:
Original post by scjohnno
*** Source Snippet Removed ***

Not that I recommend using a set rather than a map (or hash map) if you need to look up by name.

holy cow, you're iterating through set to find something in it? you know that set uses binary tree and why?

Share this post


Link to post
Share on other sites
Quote:
Original post by Dmytry
Codeka: dont forget thread safety. Smart pointers are nontrivial to implement quickly. Especially, weak pointers.
Quote:
Original post by scjohnno
*** Source Snippet Removed ***

Not that I recommend using a set rather than a map (or hash map) if you need to look up by name.

holy cow, you're iterating through set to find something in it? you know that set uses binary tree and why?

Yes, hence the disclaimer.

Share this post


Link to post
Share on other sites
Actually, the new C++ standard already allows for searching a different type that the one used to sort the range, but only for algorithms.
There is a proposal to extend that to associative containers: http://www.open-std.org/JTC1/sc22/wg21/docs/papers/2009/n2820.pdf

Share this post


Link to post
Share on other sites

This topic is 3146 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this