Thread: Sets of Vectors in STL

  1. #1
    Registered User
    Join Date
    Jun 2009
    Posts
    3

    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?

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You need to think of what it would mean for this_vector to be less than that_vector, and implement operator < accordingly.

  3. #3
    Registered User
    Join Date
    Jun 2009
    Posts
    3
    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?

  4. #4
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    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

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Steff View Post
    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.

  6. #6
    Registered User
    Join Date
    Jun 2009
    Posts
    3
    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.

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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?

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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: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?
    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"

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by iMalc View Post
    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: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?
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem aligning floating point numbers
    By esbo in forum C Programming
    Replies: 4
    Last Post: 01-05-2009, 08:09 PM
  2. STL Vectors of Vectors
    By Beamu in forum C++ Programming
    Replies: 2
    Last Post: 12-31-2008, 05:23 AM
  3. Array of Vectors amd other STL questions
    By kolistivra in forum C++ Programming
    Replies: 16
    Last Post: 04-12-2007, 09:11 AM
  4. Stl sets and custom classes.
    By cunnus88 in forum C++ Programming
    Replies: 3
    Last Post: 05-12-2006, 11:58 PM
  5. STL Vectors
    By Da-Nuka in forum C++ Programming
    Replies: 2
    Last Post: 02-25-2005, 08:35 PM