Hi,
Sets in STL require a comparison operation. However, I have a situation where I'd like to create a set of vectors of numbers. So, I have a partial order, but no strict ordering. What's the easiest way to accomplish this?
Hi,
Sets in STL require a comparison operation. However, I have a situation where I'd like to create a set of vectors of numbers. So, I have a partial order, but no strict ordering. What's the easiest way to accomplish this?
You need to think of what it would mean for this_vector to be less than that_vector, and implement operator < accordingly.
That's the point. There is no total ordering on vectors in R^n. In other words, while [2,2]>[1,1], we do not have that [1,2] > [2,1] nor [2,1]>[1,2]. We do have a partial ordering, but sets in STL do not allow for this. As such, is there another way?
Why do you need a std::set of vectors? A set, by definition, can only have one copy of each element you add to it; and therefore you need a < operator for comparison.
Maybe you don't really need a set, but some other container?
"I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008
"the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010
That looks correct. Indeed, the lexiographic ordering establishes a total order on R^n which would allow the use of set. Thanks.
As a related question, sets in STL are implemented as trees. Thus, if we have a set of vectors that are very long, the comparison operations become increasingly expensive. If we use the lexiographic ordering, in the worst case we have to do n operations each time we do one comparison. Since we have to do a comparison each time we move through the tree, this becomes expensive. Thus, would it be more efficient to implement a set using a hash table if the elements of the set are long vectors?
Essentially, I want to store sets of vectors and then compute operations such as union, intersection, or set difference and I'm looking for the best way to accomplish this.
I'm thinking the best way to do that would probably be to use sets. Not sets of vectors, but sets of ints. Do you need the ordering that vector provides for some not-yet-specified reason?
I've used the following structure in code before, and for good reason:
So std::list and std:air already have appropriate less-than operators. I can't see why a vector wouldn't also have it. Have you tried simply declaring a set< vector<int> > to see if it compiles?Code:map< list< pair<long, long> >, set<long> >
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"