How do I place objects that seem to be incomparable in a C ++ std :: set?
Let's say I want to put objects that identify the server in stl set
. Then I would have to make sure that I also implement operator<
for those objects, otherwise I would run into a compiler error:
struct ServerID
{
std::string name; // name of the server
int port;
};
std::set<ServerID> servers; // compiler error, no operator< defined
This is just one example of a common problem where I want to make an object comparable.
My current solution is usually done like this:
bool operator< (const ServerID & lhs, const ServerID & rhs)
{
if (lhs.name != rhs.name)
{
return lhs.name < rhs.name;
}
else
{
return lhs.port < rhs.port;
}
}
This is just the solution I found. But I suspect this problem could also be recognized in the field of computer science. So if I'm lucky there is a better solution for this. Can anyone give me a hint of this?
source to share
I would recommend not using it as operator <to avoid possible confusion, but rather passing the order function as a parameter to the std :: set template argument.
struct server
{
std::string name;
int port;
};
struct name_then_port : public std::binary_function<server,server,bool>
{
bool operator()( server const & lhs, server const & rhs ) {
// using litb approach (more efficient as it does not call both < and == on strings:
int cmp = lhs.name.compare(rhs.name);
return ( cmp < 0 ) || ((cmp==0) && ( lhs.port < rhs.port));
}
};
struct port_then_name : public std::binary_function<server,server,bool>
{
bool operator()( server const & lhs, server const & rhs ) {
return (lhs.port < rhs.port) || ((lhs.port==rhs.port) && (lhs.name<rhs.name));
}
};
int main()
{
std::set< server, name_then_port > servers; // or:
std::set< server, port_then_name > servers2;
}
On the question of whether this issue has been identified before, it has. The general solution is exactly what you placed: lexicographic order . Although this term is usually called string ordering, but the order is the same: take the first element, compare if it does not determine the order, taking the next data element and iteration.
source to share
Your canonical solution. I'm not sure how you could do this to make it better.
To expand on this, if you have members n
in your class, you will find that you need to compare a number of these fields to establish a strict ordering. There is no real way to get around this, although you may find that you can make the comparison function more efficient (in terms of moderate complexity) if you order comparisons so that those that are more likely to contribute to the success of the comparison come first. This helps him to quickly abandon the comparison.
A feature that can help in some circumstances (if you find that performance dominates the comparison) is to create a "sort key" - string comparisons can be expensive. The sort key is an integer that can be used to quickly compare objects. If the sort key compares less then the string will work as well.
In your case, a simplified sort key might involve treating the binary representation of strings as integers - by the way, this involves a lot of errors, and then comparing integers instead of strings.
On Windows, the LCMapString function can be used to create a sort key for strings in this way. I think you can use a fast type function memcmp
to compare strings instead of a slower string comparison. This is more useful if you will be doing case insensitive comparisons, or if you are using the entire range of Unicode characters and would like correct comparisons according to their rules.
source to share
I usually write it like:
return x.name < y.name ||
x.name == y.name && x.port < y.port;
... which you can keep expanding for the number of member variables. This solution will short-circuit as soon as possible and eliminate branching.
Note that each of the member variables needs to be defined operator<
, which is very well implemented outside of this procedure.
source to share
I would use string::compare
bool operator< (const ServerID & lhs, const ServerID & rhs) {
int lcr = lhs.name.compare(rhs.name);
return lcr < 0 || (lcr == 0 && lhs.port < rhs.port);
}
If it doesn't make sense for you to match it, and the only thing that could be used in set
, you can use the functor
struct ServerIdCompare {
bool operator()(const ServerID & lhs, const ServerID & rhs) const {
int lcr = lhs.name.compare(rhs.name);
return lcr < 0 || (lcr == 0 && lhs.port < rhs.port);
}
};
std::set<ServerID, ServerIdCompare> servers;
If you do, however, provide the operator with an independent (not using a functor), as described above, are also provided <=
, ==
, >=
and !=
so it was agreed.
source to share
Your solution is pretty much fine for this. Your comparison function should be set up to uniquely identify each server (which really means depends on your use case), so name / port comparison is probably sufficient.
If you know that you will not have two servers with the same name but different ports (or you want to treat them the same way), you can opt out of this part of your comparison function. A more realistic example would be if you had more members of your server object that were not tied to the identity of the server itself (like the "last request" cache); in that case, you probably would not want your set to differ based on that field, so you would not include it in your comparison function. OTOH, this may not be the best design for the server object.
If you find it difficult to answer the question "When is it necessary for two servers (objects) to be considered identical?" then you may not need the kit at all.
source to share