Thread: About STL, iterators, and oerator overloading

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    22

    About STL, iterators, and oerator overloading

    I am introducing STL to myself. I want to make a set (STL container) of a weighted graph's edges. If I understand correctly, the associative containers like set, use the operator < on the keys(members) to sort them, and operator ==(OR != ?) to make sure no duplicates are inserted.

    For my set of edges, I want the check to be evaluated upon iterators that point the two nodes (classes) that are connected via the edge, as its the criterion of uniquity. However, I want them sorted depending on their weight.

    Code:
     
    typedef unsignedlong UL;
    struct node{
        UL v,l;//(V)alue, (L)eader (of branch in Kruskal's algorithm)
    node(UL x):v(x),l(x){}//Constructor
    booloperator<(node x) {return v<x.v;}
    booloperator==(node x) {return v==x.v;}
    };
    typedef iterator<random_access_iterator_tag,node> it;
    struct edge{
    it n1,n2;//Pointer to the two nodes it connects
    double w;//weight
    bool MSTE;
    edge(it x, it y, double z): n1(x), n2(y), w(z),MSTE(false){}//Constructor
    booloperator<(edge x) {return w<x.w;}//n1 will be the same in a set of edges under a specific node.
    booloperator==(edge x) {return n1==x.n1 && n2==x.n2;}
    };
    
    I get the error concerning the last line, no operator == matches these operands. Why? In C++ reference, in the section about iterators, it clearly states that operators ==,!=,*, and -> can be used! It won't work if I try to use * or -> to compare the node classes with the operator i've defined for them either. What's wrong?

    The identation is scr**ed again, can't even fix it, sorry!

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    iterator is just a base class that defines some type traits needed for iterators. If you want an iterator, then you are going to have to create a class that implements your iterator (which inherits from an appropriate iterator type class).
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    Registered User
    Join Date
    Oct 2006
    Posts
    3,445
    you also seem to be missing a LOT of very important whitespace.

    for example 'unsignedlong' is not declared in your example, and should probably be 'unsigned long', just as 'booloperator' should probably be 'bool operator' etc.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    A std::set never uses operator == or operator != for anything. The datatype you are using need not even supply such operators.
    It knows that two items A and B are equal when A < B and B < A are both false.

    What you probably want is:
    Code:
    typedef std::set<node>::iterator it;
    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"

  5. #5
    Registered User
    Join Date
    Nov 2011
    Posts
    22
    Quote Originally Posted by iMalc View Post
    A std::set never uses operator == or operator != for anything. The datatype you are using need not even supply such operators.
    It knows that two items A and B are equal when A < B and B < A are both false.

    What you probably want is:
    Code:
    typedef std::set<node>::iterator it;
    This seems to work, but spawns more questions:

    1) Now, what category is this iterator? Is it a random-access one, as I want it?

    2) Reminding this:
    Code:
    struct node{
    UL v,l;//(V)alue, (L)eader (of branch in Kruskal's algorithm)
    node(UL x):v(x),l(x){}//Constructor
    booloperator<(node x) {return v<x.v;}
    };
    typedef set<node>::iterator it;
    struct edge{
    it n1,n2;//Iterator(pointer) to element of node set (that is, a node)
    double w;//weight
    bool MSTE;
    edge(it x, it y, double z): n1(x), n2(y), w(z),MSTE(false){}//Constructor
    booloperator<(edge);//n1 will be the same in a set of edges under a specific node.
    };
    
    I wanted the edges to be sorted according to the nodes their iterators were pointing to. I tried:
    Code:
    bool edge::operator<(edge x)
    {
    if(n1==x.n1) return *n1<*x.n1;
    elsereturn *n2<*x.n2;
    
    but failed. Then I used this:
    Code:
    
    bool edge::operator<(edge x)
    {
    if(n1==x.n1)
    returnconst_cast<node&>(*n1)<const_cast<node&>(*x.n1);
    else
    
    returnconst_cast<node&>(*n1)<const_cast<node&>(*x.n1);
    }
    
    Why did I need this cast?

    3)
    Code:
    typedefmap<node,set<edge>> graph;
    
    graph G;
    
    node n1=...;
    it it1;
    it1=G.find(n1);
    

    ...won't compile with error:
    "
    1>d:\ha\structures and algorithms\project2_stl\main.cpp(31): error C2679: binary '=' : no operator found which takes a right-hand operand of type 'std::_Tree_iterator<_Mytree>' (or there is no acceptable conversion)
    "

    why?

    4) I don't lack whitespace, but when I paste text here, or even when I try to make it better, things get really messy. I'm using IE, is that the problem?

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    1) It will be a std::set::iterator which is bidirectional. There is no random-access iterator for a set. If you need random access then you'll have to forget about using a set.

    2) The correct code should be:
    Code:
    bool edge::operator<(const edge &x) const
    {
        
        if (n1 != x.n1)
            return *n1 < *x.n1;
        else
            return *n2 < *x.n2;
    }
    The code you had would not compile without the const casts because you were trying to give it a less-than-operator that did not promise to not modify the items. An item in a set must not be modified because otherwise you could change the key and screw up the ordering of the set. Using const correctly as I've shown lets the compiler know that you're not trying to modify anything.
    You also had == where you should have had !=.

    3) Doing a find on G doesn't give you back an iterator of type it, it gives you back an iterator of type graph::iterator.
    Note that sometimes using a map to a set means that what you really should have is just a multimap and not a set at all. I'm not sure if that applies in this case, would need more info.

    4) No, IE is not the problem as I use IE9. Try pasting the code into notepad first and then copying it out of there to paste into the forums. This makes it throw away any rich text crap that you don't need. What IDE are you copying from?
    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"

  7. #7
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    1) Now, what category is this iterator? Is it a random-access one, as I want it?
    This is the sort of question you look up in a book or something.... Nope. It's bidirectional. You can go backwards or forwards through a set. If you want random access, use vector and the unique() algorithm.

    2) Why did I need this cast?
    What was the problem you covered up with it? Only said you failed.

    About question 3, edge cannot be constructed like:

    edge e = somenode, othernode, 3.4;

    That form is restricted to constructors with one argument. Otherwise you are supposed to use this form.

    edge e(somenode, othernode, 3.4);

    This is basic, by the way. Again, the kind of thing you find in a book or something.

    I don't lack whitespace, but when I paste text here, or even when I try to make it better, things get really messy. I'm using IE, is that the problem?
    The problem is you messing with it. Just paste in between code tags and don't touch it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Iterators
    By GReaper in forum C++ Programming
    Replies: 5
    Last Post: 02-26-2010, 02:42 PM
  2. iterators?
    By Warrax in forum C++ Programming
    Replies: 6
    Last Post: 06-11-2007, 03:13 PM
  3. Iterators
    By manutd in forum C++ Programming
    Replies: 5
    Last Post: 12-17-2006, 11:13 AM
  4. iterators
    By linucksrox in forum C++ Programming
    Replies: 5
    Last Post: 03-12-2006, 06:46 PM
  5. iterators
    By strickey in forum C++ Programming
    Replies: 10
    Last Post: 02-15-2005, 12:45 PM