# Sets of Vectors in STL

• 06-17-2009
Steff
Sets 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-2009
tabstop
You need to think of what it would mean for this_vector to be less than that_vector, and implement operator < accordingly.
• 06-17-2009
Steff
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-2009
cpjust
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-2009
tabstop
Quote:

Originally Posted by Steff
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?

Of course there is a total ordering on vectors in R^n, it just may not be "natural". (The lexicographic order is one example.) Presumably, if you actually need a set of vectors, you have some comparison between them in mind.
• 06-17-2009
Steff
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-2009
tabstop
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-2009
iMalc
I've used the following structure in code before, and for good reason:
Code:

`map< list< pair<long, long> >, set<long> >`
So std::list and std::pair 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?
• 06-18-2009
tabstop
Quote:

Originally Posted by iMalc
I've used the following structure in code before, and for good reason:
Code:

`map< list< pair<long, long> >, set<long> >`
So std::list and std::pair 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?

Hey, what do you know:
Quote:

Originally Posted by ISO C++
Code:

```template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x,     const vector<T,Allocator>& y);```

Even better, < is to be defined in terms of the function "lexicographical_compare". Wonder what that does.