Thread: 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.

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?

Originally Posted by Programmer_P

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.

Originally Posted by grumpy

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.

Originally Posted by kmdv

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.

Originally Posted by whiteflags

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.

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.

Originally Posted by kmdv

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.

Originally Posted by Programmer_P

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.
}

Originally Posted by Programmer_P

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.

Originally Posted by Programmer_P

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.

Originally Posted by Programmer_P

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.

Originally Posted by kmdv

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!)

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.

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.

Originally Posted by Programmer_P

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.

Originally Posted by Programmer_P

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.

Originally Posted by grumpy

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