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?

Printable View

- 06-17-2009SteffSets of Vectors in STL
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? - 06-17-2009tabstop
You need to think of what it would mean for this_vector to be less than that_vector, and implement operator < accordingly.

- 06-17-2009Steff
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?

- 06-17-2009cpjust
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? - 06-17-2009tabstop
- 06-17-2009Steff
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. - 06-17-2009tabstop
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?

- 06-17-2009iMalc
I've used the following structure in code before, and for good reason:

Code:`map< list< pair<long, long> >, set<long> >`

- 06-18-2009tabstop