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?

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?

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.

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:

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?

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.