Like Tree5Likes

Problem with vector iterator

This is a discussion on Problem with vector iterator within the C++ Programming forums, part of the General Programming Boards category; Hello. I began playing around a little with iterators for an std::vector a while back for my programming project I'm ...

  1. #1
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827

    Problem with vector iterator

    Hello.
    I began playing around a little with iterators for an std::vector a while back for my programming project I'm currently working on, and am basically trying to use them right now to access a vector object (stored inside of a map)'s elements (which are instances of a struct named "S_html_attr_value"), and modify them to add some information not originally given in an earlier class I built (such as setting a 'notes' and 'tips' property for them). Now, my original thought was that I could modify the vector inside of the map without having to copy the vector content into a new vector object (and then copy it back into the map after removing the old vector, once the changes are made...), and simply modify the original vector inside of the map instead. However, attempting to do this has run me into a number of issues (starting with a segfault, continuing with a segfault even after I tried a number of things to fix it, and now when I C/Ped it into codepad.org's, and modified the original concept a little, the error its giving me now (at least on codepad.org) complains about "trying to increment a singular iterator", even though the iterator is supposed to be a random access iterator which shouldn't have any problems. I suspect it has something to do with std::map's behavior with vector mapped values, since using just a vector and no map, the code works just fine. Anyway, I tried many different things, which I wont go to any great length to explain right now, as that would take too long.

    Here is basically where I'm stuck right now (click the link to see the
    code):

    C++ code - 158 lines - codepad

    The line of most interest is 153. Try commenting it out, and you'll see the error disappears.
    Last edited by Programmer_P; 01-03-2013 at 07:47 PM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,526
    My guess is (from your description, such as it is) is that you are retrieving an iterator from the map, doing something which changes the map (and therefore invalidates iterators), and then using the iterator.

    If you are storing pointers to the return value of a map's operator[] multiple times, you can achieve the effect, since operator[] potentially inserts elements into the map (which means you will invalidate the pointers).

    Singular iterators are generally iterators corresponding to the end of a container (eg returned by some_container.end()), in some implementations of the standard library. If you increment such an iterator, you are effectively falling off the end of the container.

    Note that I have not bothered to read your code. That's fair. After all, you can't be bothered to explain your problem clearly, and I would guess your code is a mess, so why should I waste my time reading it?
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy in reply to you, it is likely you deserve it. Suck it up, sunshine, and read this, this, and this before posting again.

  3. #3
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    682
    Quote Originally Posted by Programmer_P View Post
    The line of most interest is 153. Try commenting it out, and you'll see the error disappears.
    Haven't you thought that the bug may be somewhere else? And your code is full of mangled identifiers which make it hard to read and understand.
    I never put signature, but I decided to make an exception.

  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,750
    Yeah I can pretty much guarantee that grumpy has the right end of the stick on this one.

    I do question if you are using the right data structure. If each attribute value has a list of supported browsers in it do you really need to use a map to express this relationship?

  5. #5
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by grumpy View Post
    My guess is (from your description, such as it is) is that you are retrieving an iterator from the map, doing something which changes the map (and therefore invalidates iterators), and then using the iterator.
    No. I do not do that, in either my original code or in the example code which simplifies the problem. I do modify the map, though without using iterators, by inserting some new elements into the map, namely pairs of S_browser objects and empty vector<S_html_attr_value> objects. See, the basic idea of my code, is to construct Html tag objects in a class called C_html4_tags. The tag objects constructed represent, in order, each Html tag listed in the Html 4.01 specification. And each tag object
    contains a 'supported_attrs' member which is a vector<S_html_attr> object that contains, in alphabetical order, Html attribute objects which represent each Html attribute listed in the Html 4.01 specification (each of which contains all of the attribute values
    that can be associated with a given attribute, of course) for that specific Html tag object. Now, one of the members of an S_html_attr object is a 'supported_attr_values' member which is a map< S_browser, vector<S_html_attr_value> > which contains (at
    the C_html4_tags level, at least...though this what I modify at the next level up, the C_html4_elements level) a list of attribute value objects specific to a given Html attribute object, corresponding to the same list found in the Html 4.01 specification. Because
    this list is not browser-oriented at this level (and for a good reason, since I did not want to worry about coding for specific browsers at that level, but merely wanted to provide the model to use for that purpose later on...in C_html4_elements), I used an S_browser object called a "dummy_browser" by convention, since its a fake browser key used only for referencing the list of attribute values inside that map object. And this map object is what I later decided to modify in C_html4_elements, by adding new pairs of S_browser objects and vector<S_html_attr_values>s to the map, coding now for each major browser I decided to support (namely IE, FF, Opera, Google Chrome, and Safari). Thus the reason for the code that is producing the problem now.

    If you are storing pointers to the return value of a map's operator[] multiple times, you can achieve the effect, since operator[] potentially inserts elements into the map (which means you will invalidate the pointers).
    Well, yes, I understand that. That is why before using that, in my code, I first inserted an S_browser and vector<S_html_attr_value> pair into the map, the same S_browser object of which I later use with that operator to retrieve that same vector, or rather
    create a pointer to it, so I could use the pointer to add to the vector inside of the map.

    Singular iterators are generally iterators corresponding to the end of a container (eg returned by some_container.end()), in some implementations of the standard library. If you increment such an iterator, you are effectively falling off the end of the container.
    Ok, but how do you explain the fact that I only iterate through the vector container starting at vector.begin() and ending at vector.end() - 1 (see the example code for proof of this...)?

    Note that I have not bothered to read your code. That's fair. After all, you can't be bothered to explain your problem clearly, and I would guess your code is a mess, so why should I waste my time reading it?
    Lol. Well, I hope I have explained my problem a little better now. Maybe now you will be bothered to read the code...
    Also note that one of the reasons that I did not previously explain the problem very well, is because I figured my code when read, itself, would help one understand what it is I was trying to accomplish.
    Last edited by Programmer_P; 01-04-2013 at 01:13 PM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  6. #6
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by kmdv View Post
    Haven't you thought that the bug may be somewhere else? And your code is full of mangled identifiers which make it hard to read and understand.
    Well, in my example code, I would almost guarantee that that line is the problem. Otherwise, commenting it out would not remove the error, now would it...
    As for mangled identifers, I don't think that's quite true. I actually used descriptive names in my code, and even added some additional information, as for what certain things are for, in comments, when the name itself wasn't clear enough.

    Note that the main thing you should be focusing on, and reading, in my example code, is the int main() function, which is not very long.
    The reason why the two structs shown there contain variables not used in the example code, is because I copied and pasted the original structs into the thing, so I wouldn't have to rewrite them.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  7. #7
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by whiteflags View Post
    Yeah I can pretty much guarantee that grumpy has the right end of the stick on this one.

    I do question if you are using the right data structure. If each attribute value has a list of supported browsers in it do you really need to use a map to express this relationship?
    Well, I believe that I do, since the map is in the S_html_attr construct, as a member called 'supported_attr_values', and the list you're talking about is in the construct called 'S_html_attr_value'.
    I have both because for some reason, I may need both. But the map is more convenient because it means you can easily get a list of supported attribute values for a specific browser from an S_html_attr object,
    as well as a list of standard (i.e. listed in the specification) attribute values with a couple lines of code.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  8. #8
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    682
    Ok, so I bothered to read your code.

    First, you declare your own copy-assignment operator without any good reason, instead of using the default one. Obviously you implemented it wrong:

    Code:
    S_html_attr_value& operator= (const S_html_attr_value& otherAttrValue) // Return by reference, not by value.
    {
        ...
        return *this; // And return *this, not otherAttrValue.
    }
    However, this isn't the problem, since it is theoretically allowed and valid.
    The problem is your operator< which does not do a proper total ordering of S_browser:

    Code:
    struct S_browser {
    
    std::string name;
    double version;
    
    bool operator< (const S_browser& browser) const {
    
        if ((name == browser.name) && (version < browser.version)) {
            return true;
         }
    
         return false;
    }
    
    };
    The total ordering should take into account any visible state.
    Later in your code there is a map:

    Code:
    map<S_browser, TYPE_attr_values> a_map;
    
    a_map.insert(make_pair(dummy_browser, supported_attr_values_for_Dummy_Browser));
    a_map.insert(make_pair(ie_browser, supported_attr_values_for_IE));
    
    supported_attr_values_for_Dummy_Browser_P = &a_map[dummy_browser];
    supported_attr_values_for_IE_P = &a_map[ie_browser];
    And because of the incorrectly implemented total ordering, your map has exactly one key-value pair. As a result, these two pointers point to the same instance giving you INPUT == OUTPUT. As grumpy has said:

    you are retrieving an iterator from the map, doing something which changes the map (and therefore invalidates iterators), and then using the iterator.
    Assuming that an untested code is valid is a bad practice.
    Programmer_P likes this.
    I never put signature, but I decided to make an exception.

  9. #9
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by kmdv View Post
    Ok, so I bothered to read your code.

    First, you declare your own copy-assignment operator without any good reason, instead of using the default one. Obviously you implemented it wrong:

    Code:
    S_html_attr_value& operator= (const S_html_attr_value& otherAttrValue) // Return by reference, not by value.
    {
        ...
        return *this; // And return *this, not otherAttrValue.
    }
    However, this isn't the problem, since it is theoretically allowed and valid.
    The problem is your operator< which does not do a proper total ordering of S_browser:

    Code:
    struct S_browser {
    
    std::string name;
    double version;
    
    bool operator< (const S_browser& browser) const {
    
        if ((name == browser.name) && (version < browser.version)) {
            return true;
         }
    
         return false;
    }
    
    };
    You are right. Those operators I was just trying out for now. I was unsure about them, and whether or not they work, and had not tested them extensively.
    How would you suggest that I implement the < operator of S_browser then? I remember in another thread I posted here, someone said I needed one of those,
    if I was going to have an S_browser object as a key of a map. And they said I needed it even if I didn't have a use for it. So I basically just wrote something that I thought might work to compare two S_browser objects
    with the same name but different versions. Of course, I obviously didn't know how std::map uses this operator to begin with...and still don't know. I also don't understand why its necessary to have one at all.
    As for the copy-assignment operator of S_html_attr_value, I wrote that only after the segfault problem, and I thought that maybe that was the problem, since I didn't know how the default one worked, and I knew
    I was using it in a couple of setter functions of the C_html4_tags class to copy the modified attribute value object's contents into the attribute value object passed (which originally was an iterator of the
    vector<S_html_attr_value> inside the map - dereferenced). But after looking at other people's implementations of that operator online, I didn't really understand why it was returning a reference to *this, so
    I decided to return by value instead. Anyway, obviously I understood all that was questionable, and might have to be modified later on.

    The total ordering should take into account any visible state.
    I'm not sure what you mean by that...? Could you please elaborate on that?

    Later in your code there is a map:

    Code:
    map<S_browser, TYPE_attr_values> a_map;
    
    a_map.insert(make_pair(dummy_browser, supported_attr_values_for_Dummy_Browser));
    a_map.insert(make_pair(ie_browser, supported_attr_values_for_IE));
    
    supported_attr_values_for_Dummy_Browser_P = &a_map[dummy_browser];
    supported_attr_values_for_IE_P = &a_map[ie_browser];
    And because of the incorrectly implemented total ordering, your map has exactly one key-value pair. As a result, these two pointers point to the same instance giving you INPUT == OUTPUT. As grumpy has said:
    I'm assuming you mean by all that, the < operator of the S_browser object somehow effects how the insert operation of the std::map works, right?
    If so, could you please explain how exactly it works? Thanks.

    Assuming that an untested code is valid is a bad practice.
    You're right. I guess that was partly due to pure laziness.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  10. #10
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    682
    Quote Originally Posted by Programmer_P View Post
    How would you suggest that I implement the < operator of S_browser then?
    By comparing fields like this:

    Code:
    bool operator<(const Foo& lhs, const Foo& rhs)
    {
        if (lhs.A != rhs.A)
        {
           return lhs.A < rhs.A;
        }
        if (lhs.B != rhs.B)
        {
           return lhs.B < rhs.B;
        }
        if (lhs.C != rhs.C)
        {
           return lhs.C < rhs.C;
        }
        return false; // lhs and rhs are equivalent.
    }
    Quote Originally Posted by Programmer_P View Post
    Of course, I obviously didn't know how std::map uses this operator to begin with...and still don't know. I also don't understand why its necessary to have one at all.
    It is needed for O(log N) operations. Map stores its elements in a tree.

    Quote Originally Posted by Programmer_P View Post
    I'm not sure what you mean by that...? Could you please elaborate on that?
    You should take into account every field (every state visible to the user of your class) to avoid a situation where two values which look and feel like two different things are recognised as equivalent values.
    This applies to every comparison operator.

    Quote Originally Posted by Programmer_P View Post
    I'm assuming you mean by all that, the < operator of the S_browser object somehow effects how the insert operation of the std::map works, right?
    If so, could you please explain how exactly it works? Thanks.
    You feed your map with two different values: A and B. If !(A < B) && !(B < A) then A == B. This makes the map think that it recieves two pairs with the same key.
    iMalc likes this.
    I never put signature, but I decided to make an exception.

  11. #11
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by kmdv View Post
    By comparing fields like this:

    Code:
    bool operator<(const Foo& lhs, const Foo& rhs)
    {
        if (lhs.A != rhs.A)
        {
           return lhs.A < rhs.A;
        }
        if (lhs.B != rhs.B)
        {
           return lhs.B < rhs.B;
        }
        if (lhs.C != rhs.C)
        {
           return lhs.C < rhs.C;
        }
        return false; // lhs and rhs are equivalent.
    }


    It is needed for O(log N) operations. Map stores its elements in a tree.



    You should take into account every field (every state visible to the user of your class) to avoid a situation where two values which look and feel like two different things are recognised as equivalent values.
    This applies to every comparison operator.



    You feed your map with two different values: A and B. If !(A < B) && !(B < A) then A == B. This makes the map think that it recieves two pairs with the same key.
    Ahh...I see. So something like this then, right:

    C++ code - 161 lines - codepad

    (Yay, it works!)
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  12. #12
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Weird. When I tried that in my real code, it now complains about multiple definitions of that operator. Even though there is only one.

    S_browser.h:

    Code:
    #ifndef S_BROWSER_H
    #define S_BROWSER_H
    
    //STL module:
    #include <string>
    
    struct S_browser {
    
         std::string name;
         double version;
    
    };
    
    bool operator< (const S_browser& lhs, const S_browser& rhs) {
    
             if (lhs.name != rhs.name) {
                return lhs.name < rhs.name;
             }
    
             if (lhs.version != rhs.version) {
                return lhs.version < rhs.version;
             }
    
             return false; //since lhs and rhs are the same
    
    }
    
    #endif //S_BROWSER_H
    EDIT: Oops. Nevermind. Forgot to make it an inline function, since the definition is in a header file.
    Last edited by Programmer_P; 01-04-2013 at 03:14 PM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  13. #13
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Hmm...on second thought, I'm thinking this implementation might be better:

    C++ code - 166 lines - codepad

    EDIT: Or modify the version in my last post to use an else if instead of an if for the last checking statement:

    Code:
    bool operator< (const S_browser& lhs, const S_browser& rhs) {
     
             if (lhs.name != rhs.name) {
                return lhs.name < rhs.name;
             }
     
             else if (lhs.version != rhs.version) {
                return lhs.version < rhs.version;
             }
     
             return false; //since lhs and rhs are the same
     
    }
    I think they would both do basically the same thing.
    Last edited by Programmer_P; 01-04-2013 at 04:05 PM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  14. #14
    Registered User
    Join Date
    Jun 2005
    Posts
    6,526
    Quote Originally Posted by Programmer_P View Post
    Well, in my example code, I would almost guarantee that that line is the problem. Otherwise, commenting it out would not remove the error, now would it...
    Not true.

    A segmentation violation is a common symptom of undefined behaviour (typically due to your program modifying memory it shouldn't).

    More often than not, code which causes undefined behaviour is distinct from code where the symptoms are detected. Adding or removing a line, and having symptoms disappear, therefore often indicates that some code BEFORE the offending line is the cause of the problem.

    All you are doing by commenting out that particular line is removing the code where the symptoms become visible. You are not affecting the cause of the problem.

    Quote Originally Posted by Programmer_P View Post
    You're right. I guess that was partly due to pure laziness.
    Indeed. You have demonstrated laziness in this thread in more ways that assuming untested code is valid.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy in reply to you, it is likely you deserve it. Suck it up, sunshine, and read this, this, and this before posting again.

  15. #15
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by grumpy View Post
    Not true.

    A segmentation violation is a common symptom of undefined behaviour (typically due to your program modifying memory it shouldn't).

    More often than not, code which causes undefined behaviour is distinct from code where the symptoms are detected. Adding or removing a line, and having symptoms disappear, therefore often indicates that some code BEFORE the offending line is the cause of the problem.

    All you are doing by commenting out that particular line is removing the code where the symptoms become visible. You are not affecting the cause of the problem.
    You are right. However, I really meant that that line is the entry point for understanding the problem, i.e. you read that line, and that gives you the information on where to proceed from there.
    I was trying to get everyone to focus on that line to start with, thus the reason for those earlier words.

    I've learned that sometimes making untrue statements helps all those involved reach the real truth of a matter. Has something to do with the way our brains think...

    Btw, I read up on segfaults before even starting this thread, but still did not spot the problem. I didn't realize it was the fault of the < operator of the S_browser struct.
    Indeed. You have demonstrated laziness in this thread in more ways that assuming untested code is valid.
    I wont dispute that point. lol
    Last edited by Programmer_P; 01-04-2013 at 06:26 PM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem using a vector iterator in a loop.
    By M.Richard Tober in forum C++ Programming
    Replies: 6
    Last Post: 10-29-2011, 02:53 PM
  2. vector and iterator problem
    By BeBu in forum C++ Programming
    Replies: 10
    Last Post: 03-11-2009, 08:38 AM
  3. Vector Iterator Help
    By (TNT) in forum C++ Programming
    Replies: 5
    Last Post: 11-04-2007, 02:53 PM
  4. vector<object>::iterator Help
    By The Brain in forum C++ Programming
    Replies: 16
    Last Post: 03-26-2006, 07:22 PM
  5. Iterator _ erasing from a vector help
    By Hexxx in forum C++ Programming
    Replies: 1
    Last Post: 03-22-2006, 07:43 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21