Issue with using iterators

Dec 25, 2019 at 3:08pm
aTotalNoob (3)
I have the following code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
struct Floe
{
    int x{}, y{}, penguinsOnFloe{}, maxJumps{}, curJumps{0};
    bool isInputNode{true};
    vector<int> edges;
    shared_ptr<Floe> parent{nullptr};
};

vector<Floe> floes;

int linkNodes(double maxJumpSquared)
{
    int x,y;
    for (auto outputNodePtr = next( floes.begin() ); outputNodePtr != floes.end(); advance(outputNodePtr, 2) )
    {
        x = outputNodePtr -> x; y = outputNodePtr -> y;
        for (auto inputNodePtr = floes.begin(); inputNodePtr != prev( floes.end() ); advance(inputNodePtr, 2) )
        {
            if ( pow(x - (inputNodePtr -> x), 2) + pow(y - (inputNodePtr -> y), 2) <= maxJumpSquared )
            {
                outputNodePtr -> edges.push_back( inputNodePtr - floes.begin() );
            }
        }
    }
    return 0;
}


floes is a vector of Struct Floe and has the following (x,y) values associated with each struct:
[(1,1), (1,1), (2,3), (2,3), (3,5), (3,5), (5,1), (5,1), (5,4), (5,4)]

I want the first loop to iterate over the even indices and the second the odd ones.

Currently the program crashes and after running with a debugger I found that the inner loop (on first iteration) gives me x = 5 (when I expect it to be a 1). After repeated looping, every int in the struct is equal to -17891602 which leads me to think I am messing up the way I am moving my iterator.

Previously I tried:
inputNodePtr + 1 instead of next ( inputNodePtr )
inputNodePtr - 1 instead of prev ( inputNodePtr )
inputNodePtr += 2 instead of advance( inputNodePtr, 2)

I'm very new to c++ so would also like pointers on general style
Last edited on Dec 25, 2019 at 3:09pm
Dec 25, 2019 at 7:18pm
Duthomhas (13278)
You are trying to modify the vector while iterating over it — which introduces undefined behavior.

What kind of modification are you really trying to do to your floes?
Dec 25, 2019 at 7:44pm
aTotalNoob (3)
I didn't realise I couldn't modify the vector from the iterator.

I want to see which flows are closer than maxJump and add those as edges.
Dec 25, 2019 at 8:00pm
Enoizat (1343)
and has the following (x,y) values associated with each struct:
[(1,1), (1,1), (2,3), (2,3), (3,5), (3,5), (5,1), (5,1), (5,4), (5,4)]

Could you please also check the elements in ‘floes’ to ensure they have been correctly initialized?

For example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
struct Floe {
    int x {}
      , y {}
      , penguinsOnFloe {}
      , maxJumps {}
      , curJumps {};
    bool isInputNode { true };
    std::vector<int> edges;
    std::shared_ptr<Floe> parent;

//friend:
    friend std::ostream& operator << ( std::ostream& os, const Floe& rhs);
};


std::ostream& operator << ( std::ostream& os, const Floe& rhs)
{
    os << "{ " << rhs.x << ", " << rhs.y << " }";
    return os;
}


std::vector<Floe> floes;


void printFloes(const std::vecotr<Floe>& v)
{
    for ( const auto& e : v ) {
        std::cout << e << ", ";
    }
    std::cout << '\n';
}


int linkNodes(double maxJumpSquared)
{
    printFloes(floes);
    for ( auto outputNodePtr = next( floes.begin() );
          outputNodePtr != floes.end();
          advance(outputNodePtr, 2) )
    {
        int x = outputNodePtr -> x;
        int y = outputNodePtr -> y;
        for ( auto inputNodePtr = floes.begin();
              inputNodePtr != prev( floes.end() );
              advance(inputNodePtr, 2) )
        {
            if (    std::pow(x - (inputNodePtr -> x), 2)
                 +  std::pow(y - (inputNodePtr -> y), 2)
                 <= maxJumpSquared )
            {
                outputNodePtr -> edges.push_back( inputNodePtr - floes.begin() );
            }
        }
    }
    return 0;
}

Dec 25, 2019 at 8:10pm
deleted account xyzzy (5768)
I didn't realise I couldn't modify the vector from the iterator.

You can, you have to update the iterator when you do it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#include <vector>
#include <iostream>

int main()
{
   std::vector<int> c { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

   for (const auto& i : c) { std::cout << i << ' '; }
   std::cout << '\n';

   // erase all even numbers
   for (auto it = c.begin(); it != c.end(); )
   {
      if (*it % 2 == 0)
      {
         // update the iterator after erasing an element
         it = c.erase(it);
      }
      else
      {
         ++it;
      }
   }

   for (const auto& i : c) { std::cout << i << ' '; }
   std::cout << '\n';
}
Edit & run on cpp.sh

0 1 2 3 4 5 6 7 8 9
1 3 5 7 9


http://www.cplusplus.com/reference/vector/vector/erase/

Inserting values to any location other than the end of a vector also requires updating the iterator:
http://www.cplusplus.com/reference/vector/vector/insert/
Last edited on Dec 25, 2019 at 8:23pm
Dec 26, 2019 at 12:18am
aTotalNoob (3)
@enoizat
I know the floes are as I expect them to be because the following code gives me the expected values

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
void debugGraph()
{
    for (auto f = floes.begin(); f != floes.end(); ++f)
    {
        printf("pos      : (%d, %d);\n"
               "penguins : %d;\n"
               "max jumps: %d;\n"
               "curJumps : %d\n"
               "inputNode: %d\n"
               "parent   : %p\n"
               "contains : ",
               f -> x, f -> y, f -> penguinsOnFloe, f -> maxJumps, f -> curJumps, f-> isInputNode, f -> parent.get());
        for(auto i = f -> edges.begin(); i != f -> edges.end(); i++)
            cout << *i << ", ";
        cout << "\n\n";
    }
}


@furry guy
Would I still need to update the iterator if I change the members of the struct as opposed to deleted or adding an object?

I know structs hold all their members in a contiguous block of memory in C. Does this mean that when I add to my vector I actually end up overwriting a bit of the next struct in the vector? I imagine this would only happen when the vector resizes as at compile time I haven't passed a default length so it's set to 1 (at least from my debugging it seemed like it was set to 1)?

If the above logic is correct, would that mean changing values of types that take a constant amount of memory is ok (e.g. double, int) but adding a longer string than the default value or causing a vector to increase it's length breaks the iterator?

If that is the case, what is the best way to 'fix' the iterator when that happens?


Edit: I've realised the above is dumb. As then my debug code would also read wrong. Will read up on iterators and try give a better diagnosis. Not only that, but the value is wrong before any pushing to vectors has occurred.
Last edited on Dec 26, 2019 at 12:29am
Dec 26, 2019 at 12:57am
Duthomhas (13278)
Inserting/adding anywhere in a vector potentially invalidates iterators.
Dec 26, 2019 at 12:01pm
Enoizat (1343)
It seems you were simply going beyond boundaries.
This code seems to work:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
#include <cmath>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <memory>
#include <vector>


#ifndef CLASS_FLOE_HPP
#define CLASS_FLOE_HPP


struct Floe {
    int x {}
      , y {}
      , penguins_on_floe {}
      , max_jumps {}
      , cur_jumps {};
    bool is_input_node { true };
    std::vector<int> edges;
    std::shared_ptr<Floe> parent;

//friend:
    friend std::ostream& operator << ( std::ostream& os, const Floe& rhs);
};


#endif // CLASS_FLOE_HPP


std::ostream& operator << ( std::ostream& os, const Floe& rhs)
{
    os << "pos: (" << rhs.x << ", " << rhs.y << ")"
       << "; penguins: " << rhs.penguins_on_floe
       << "; max j: "      << rhs.max_jumps
       << "; curr j: "  << rhs.cur_jumps
       << "; input? "          << std::boolalpha << rhs.is_input_node
       << "; parent: "         << rhs.parent.get()
       << "; --> ";
    for ( int i : rhs.edges ) {
        os << i << ", ";
    }
    return os;
}


int linkNodes(double max_jump);
std::vector<Floe> fillVectorWithMagicValues();
void printFloes(const std::vector<Floe>& v);


int main()
{
    linkNodes( 66.6 );  // arbitrary magic number
}


int linkNodes(double max_jump)
{
    auto floes { fillVectorWithMagicValues() } ;
    printFloes(floes);

    for ( auto odds { std::next( floes.begin() ) };
          odds <= floes.end();
          std::advance(odds, 2) )
    {
        std::cout << "odds now: " << *odds << '\n';
        int x = odds->x;
        int y = odds->y;
        for ( auto evens { floes.begin() };
              evens <= std::prev( floes.end() );
              std::advance(evens, 2) )
        {
            std::cout << "evens now: " << *evens << '\n';
            if (    std::pow(x - (evens->x), 2)
                 +  std::pow(y - (evens->y), 2)
                 <= max_jump )
            {
                odds->edges.push_back( evens - floes.begin() );
            }
        }
    }

    printFloes(floes);
    return 0;
}


std::vector<Floe> fillVectorWithMagicValues()
{
    // x, y, penguins_on_floe, max_jumps, cur_jumps, is_input_node, edges, parent
    // Note: let's use cur_jumps to teel them apart:
    std::vector<Floe> v {
        { 1, 1, 13, 666, 0, false, {}, nullptr },
        { 1, 1, 13, 666, 1, false, {}, nullptr },
        { 2, 3, 13, 666, 2, false, {}, nullptr },
        { 2, 3, 13, 666, 3, false, {}, nullptr },
        { 3, 5, 13, 666, 4, false, {}, nullptr },
        { 3, 5, 13, 666, 5, false, {}, nullptr },
        { 5, 1, 13, 666, 6, false, {}, nullptr },
        { 5, 1, 13, 666, 7, false, {}, nullptr },
        { 5, 4, 13, 666, 8, false, {}, nullptr },
        { 5, 4, 13, 666, 9, false, {}, nullptr }
    };
    return v;
}


void printFloes(const std::vector<Floe>& v)
{
    for ( const auto& e : v ) {
        std::cout << e << '\n';
    }
    std::cout << '\n';
}
Edit & run on cpp.sh


Output:
pos: (1, 1); penguins: 13; max j: 666; curr j: 0; input? false; parent: 0; -->
pos: (1, 1); penguins: 13; max j: 666; curr j: 1; input? false; parent: 0; -->
pos: (2, 3); penguins: 13; max j: 666; curr j: 2; input? false; parent: 0; -->
pos: (2, 3); penguins: 13; max j: 666; curr j: 3; input? false; parent: 0; -->
pos: (3, 5); penguins: 13; max j: 666; curr j: 4; input? false; parent: 0; -->
pos: (3, 5); penguins: 13; max j: 666; curr j: 5; input? false; parent: 0; -->
pos: (5, 1); penguins: 13; max j: 666; curr j: 6; input? false; parent: 0; -->
pos: (5, 1); penguins: 13; max j: 666; curr j: 7; input? false; parent: 0; -->
pos: (5, 4); penguins: 13; max j: 666; curr j: 8; input? false; parent: 0; -->
pos: (5, 4); penguins: 13; max j: 666; curr j: 9; input? false; parent: 0; -->

odds now: pos: (1, 1); penguins: 13; max j: 666; curr j: 1; input? false; parent: 0; -->
evens now: pos: (1, 1); penguins: 13; max j: 666; curr j: 0; input? false; parent: 0; -->
evens now: pos: (2, 3); penguins: 13; max j: 666; curr j: 2; input? false; parent: 0; -->
evens now: pos: (3, 5); penguins: 13; max j: 666; curr j: 4; input? false; parent: 0; -->
evens now: pos: (5, 1); penguins: 13; max j: 666; curr j: 6; input? false; parent: 0; -->
evens now: pos: (5, 4); penguins: 13; max j: 666; curr j: 8; input? false; parent: 0; -->
odds now: pos: (2, 3); penguins: 13; max j: 666; curr j: 3; input? false; parent: 0; -->
evens now: pos: (1, 1); penguins: 13; max j: 666; curr j: 0; input? false; parent: 0; -->
evens now: pos: (2, 3); penguins: 13; max j: 666; curr j: 2; input? false; parent: 0; -->
evens now: pos: (3, 5); penguins: 13; max j: 666; curr j: 4; input? false; parent: 0; -->
evens now: pos: (5, 1); penguins: 13; max j: 666; curr j: 6; input? false; parent: 0; -->
evens now: pos: (5, 4); penguins: 13; max j: 666; curr j: 8; input? false; parent: 0; -->
odds now: pos: (3, 5); penguins: 13; max j: 666; curr j: 5; input? false; parent: 0; -->
evens now: pos: (1, 1); penguins: 13; max j: 666; curr j: 0; input? false; parent: 0; -->
evens now: pos: (2, 3); penguins: 13; max j: 666; curr j: 2; input? false; parent: 0; -->
evens now: pos: (3, 5); penguins: 13; max j: 666; curr j: 4; input? false; parent: 0; -->
evens now: pos: (5, 1); penguins: 13; max j: 666; curr j: 6; input? false; parent: 0; -->
evens now: pos: (5, 4); penguins: 13; max j: 666; curr j: 8; input? false; parent: 0; -->
odds now: pos: (5, 1); penguins: 13; max j: 666; curr j: 7; input? false; parent: 0; -->
evens now: pos: (1, 1); penguins: 13; max j: 666; curr j: 0; input? false; parent: 0; -->
evens now: pos: (2, 3); penguins: 13; max j: 666; curr j: 2; input? false; parent: 0; -->
evens now: pos: (3, 5); penguins: 13; max j: 666; curr j: 4; input? false; parent: 0; -->
evens now: pos: (5, 1); penguins: 13; max j: 666; curr j: 6; input? false; parent: 0; -->
evens now: pos: (5, 4); penguins: 13; max j: 666; curr j: 8; input? false; parent: 0; -->
odds now: pos: (5, 4); penguins: 13; max j: 666; curr j: 9; input? false; parent: 0; -->
evens now: pos: (1, 1); penguins: 13; max j: 666; curr j: 0; input? false; parent: 0; -->
evens now: pos: (2, 3); penguins: 13; max j: 666; curr j: 2; input? false; parent: 0; -->
evens now: pos: (3, 5); penguins: 13; max j: 666; curr j: 4; input? false; parent: 0; -->
evens now: pos: (5, 1); penguins: 13; max j: 666; curr j: 6; input? false; parent: 0; -->
evens now: pos: (5, 4); penguins: 13; max j: 666; curr j: 8; input? false; parent: 0; -->
pos: (1, 1); penguins: 13; max j: 666; curr j: 0; input? false; parent: 0; -->
pos: (1, 1); penguins: 13; max j: 666; curr j: 1; input? false; parent: 0; --> 0, 2, 4, 6, 8,
pos: (2, 3); penguins: 13; max j: 666; curr j: 2; input? false; parent: 0; -->
pos: (2, 3); penguins: 13; max j: 666; curr j: 3; input? false; parent: 0; --> 0, 2, 4, 6, 8,
pos: (3, 5); penguins: 13; max j: 666; curr j: 4; input? false; parent: 0; -->
pos: (3, 5); penguins: 13; max j: 666; curr j: 5; input? false; parent: 0; --> 0, 2, 4, 6, 8,
pos: (5, 1); penguins: 13; max j: 666; curr j: 6; input? false; parent: 0; -->
pos: (5, 1); penguins: 13; max j: 666; curr j: 7; input? false; parent: 0; --> 0, 2, 4, 6, 8,
pos: (5, 4); penguins: 13; max j: 666; curr j: 8; input? false; parent: 0; -->
pos: (5, 4); penguins: 13; max j: 666; curr j: 9; input? false; parent: 0; --> 0, 2, 4, 6, 8,

Dec 26, 2019 at 1:41pm
dhayden (5799)
tldr: the problem is the end conditions on both loops.

You are trying to modify the vector while iterating over it
Where?

Okay, it's early and I haven't finished my coffee, but where is he modifying the vector he's iterating over (floes)? He's modifying the items in floes, but he isn't changing floes itself, so I don't see anything illegal.

aTotalNoob, what you can't do is insert or delete items from the vector while iterating over it, at least not without some care. In general, if you call a method that adds or deletes items from a container while there are iterators pointing to it, be sure you understand which iterators become invalid and do something to fix them. The standard is explicit about which iterators become invalid but this info can be hard to find.

I never use vector::iterator. It's much clearer to use an index, at least it is to me. It's less error prone too as we're about to find out :)

Okay, back to the original problem. Here's your sample input: [(1,1), (1,1), (2,3), (2,3), (3,5), (3,5), (5,1), (5,1), (5,4), (5,4)]

There are 10 items, indexed 0 through 9. Here's your outer loop:
for (auto outputNodePtr = next( floes.begin() ); outputNodePtr != floes.end(); advance(outputNodePtr, 2) )
So outputNodePtr points to item 1, then item 3, then 5, 7, 9, 11, 13, .... No where does it point just beyond item 9, which is where floes.end() points. So this loop won't end until the program crashes because it's trying to access items that don't exist.

Now let's look at the inner loop:
for (auto inputNodePtr = floes.begin(); inputNodePtr != prev( floes.end() ); advance(inputNodePtr, 2) )
The end condition is when inputNodePtr points to the last item (item 9), but this iterator goes through the even nodes (0, 2, 4, 6, 8, ...) so it will never end either.

Let's rewrite this code using good old indexes instead. I'm also going to avoid the expensive call to pow() to square the numbers:
1
2
3
4
5
6
7
8
9
10
11
12
13
 
int linkNodes(double maxJumpSquared)
{
    for (unsigned out=1; out < floes.size(); out += 2) {
        for (unsigned in = 0; in < floes.size(); in += 2) {
            int xdiff = floes[out].x - floes[in].x;
            int ydiff = floes[out].y - floes[in].y;
            if (xdiff*xdiff + ydiff*ydiff < maxJumpSquared) {
                floes[out].edges.push_back(in);
            }
        }
    }
    return 0;
}

See how easy that is? See how clean those loops are?

Does this mean that when I add to my vector I actually end up overwriting a bit of the next struct in the vector?
No. All struct's and classes have a fixed size. vector's have a pointer to the items, which are allocated on the heap. When you add or delete from the vector, it may decide to reallocate space on the heap and move the items. That's why iterators can become invalid.

But again, you aren't adding or deleting anything from the floes vector, which is the one you're iterating over. So no special care is required.

Some other comments:
- why does linkNodes() return a value? You could make it void and avoid the return 0; at the end.
- why does it take maxJumpSquared as the argument? The caller shouldn't care that it needs to use the square of the max jump value. So I'd pass in maxJump and square the value inside the function.
- Your input contains identical pairs of numbers? Is this a coincidence or is it required? If it's required then you should probably change your data structure to contain just one copy.
Topic archived. No new replies allowed.