0

I am very confused by what the following two iterators point to in the code below.

list<fieldT>::iterator steeperField = currentField;
list<fieldT>::iterator shallowerField = 
   activeFields.insert(currentField, *currentField);

If we assume that activeFields (the list these iterators pertain to) has indexes 0,1,2 (count=3), and also that currentField is presently pointing at 1. Then I imagine:

  1. steeperField is set to index 1.
  2. a fieldT is inserted into the list at index 1, and returns an iterator that starts at index 1.

Therefor, steeperField should be pointing to the same location as shallowField. This does not seem to be what's happening: shallowerField appears to point to index 2. Why?

activeFields is a parameter passed as list<fieldT> & activeFields. currentField is a parameter passed as list<fieldT>::iterator & currentField. currentField is initially started via a call to currentField = activeFields.begin();.
Mr. Smith
  • 4,288
  • 7
  • 40
  • 82
  • 3
    Please provide some more context. What are `steeperField`, `currentField` and `shallowerField`? – Stefano Sanfilippo Jan 12 '14 at 16:27
  • 1
    Yeah I can't quite figure this out: http://coliru.stacked-crooked.com/a/bdd8f1df62880bef – Lightness Races in Orbit Jan 12 '14 at 16:37
  • 1
    Do you have a trace of the code you did to get it points to index 2 ? – Gabriel L. Jan 12 '14 at 16:47
  • "shallowerField appears to point to index 2" - show how you came to that deduction, because the premise immediately prior is wrong. `steeperField` is unchanged and not invalidated during this insertion. It still references the same element it did before, but now you shoved an element in front of it. If it initially referenced the 1-slot, it (`steeperField`) will now reference the 2-slot. It sounds like you're measuring with `steeperField` rather than `shallowerField`, and without code that shows what you're *really* doing, its pure speculation, so vtc unless you provide details. – WhozCraig Jan 12 '14 at 16:52
  • I think I figured out what the OP did: assumed that list iterators point to positions in the sequence of elements, rather than the elements themselves. – Lightness Races in Orbit Jan 12 '14 at 16:58

2 Answers2

4

When I simplify the program, I get the results I expect (no assertion failures):

#include <list>
#include <iostream>
#include <cassert>

using std::list;

std::ostream& operator<<(std::ostream& os, const list<char>& l)
{
    os << '{';
    for (auto el : l)
        os << el << ',';
    os << '}';

    return os;
}

int main()
{
    list<char> l{'a', 'b', 'c'};
    list<char>::iterator insertAt { std::next(std::begin(l)) }; // 'b'

    std::cout << l << '\n';

    list<char>::iterator newEl { l.insert(insertAt, 'd') };

    std::cout << l << '\n';

    assert(std::distance(std::begin(l), insertAt) == 2);
    assert(std::distance(std::begin(l), newEl)    == 1);
}

This led me to believe that I'd missed something in your question, so I formulated it as in this post and deduced the issues in your question:

Therefor, steeperField should be pointing to the same location as shallowField.

No, it shouldn't. steeperField is the old element which has been shuffled rightwards by one; shallowField is your new element. Iterators are not fixed indexes into a container; they link to the elements. In a linked list, that means they follow the element when you insert new ones before it.

This does not seem to be what's happening: shallowerField appears to point to index 2. Why?

It does not. shallowerField points to index 1, as it should. steeperField points to index 2, also as it should.

In conclusion, something went wrong when you made your measurements.

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • I tend to conclude said-same. It deserves noting that iterators are fixed to their elements, but also the container semantics (ex. insert invalidates iterators on a vector if a resize happens, otherwise iterators before the inserted element are retained and post-element are invalidated.). Your assessment seems well-founded. – WhozCraig Jan 12 '14 at 17:01
  • @WhozCraig: Thanks. I made a bit of a mess of it, but I'm glad we got to the bottom of it! – Lightness Races in Orbit Jan 12 '14 at 17:04
  • @LightnessRacesinOrbit This solves http://stackoverflow.com/questions/21069712/what-mistake-did-i-make-porting-the-precise-permissive-field-of-view-algorithm-f for me, aswell. :) – Mr. Smith Jan 12 '14 at 17:05
1

First of all let discuss the funcion declaration

iterator insert(const_iterator position, const T& x);

It inserts element x before iterator position and returns iterator that refers to the inserted element.

In your example currentField; is an iterator that refers to some element in the list. *currentField is the value of the element. Now

activeFields.insert(currentField, *currentField)

inserts the same value as the value of the element refered to by currentField; before this element. In fact it propagates the value to the left relative to the currentField;.

If we assume that currentField corresponds to index 1 in the list { 0,1,2 } then after the operation the list will look as { 0,1,1, 2 } and iterator shallowerField will refer the first 1 that is it will correspond to index 1.

As for your statement

This does not seem to be what's happening: shallowerField appears to point to index 2. Why?

then the correct answer is "It seems" that is it seems to you only. You should show a simple compiled example that demonstrates the situation.

Here is an example

std::list<int> l = { 0, 1, 2 };

std::list<int>::const_iterator position = std::next( l.cbegin() );

std::cout << std::distance( l.cbegin(), position ) << std::endl;

std::list<int>::iterator result = l.insert( position, *position );

std::cout << std::distance( l.begin(), result ) << std::endl;

The ouput is

1
1
Vlad from Moscow
  • 301,070
  • 26
  • 186
  • 335