0

Based on the implementation of Iter, I have difficulties to understand operator!= and don't understand why it doesn't check _p_vec?

This is the suggested implementation of operator!= that ONLY compares the _pos.

class Iter
{
    public:
    Iter (const IntVector* p_vec, int pos)
        : _pos( pos )
        , _p_vec( p_vec )
    { }

    // these three methods form the basis of an iterator for use with
    // a range-based for loop
    bool operator!= (const Iter& other) const
    {
        return _pos != other._pos;
    }
    ...
    ...
    private:
        int _pos;
        const IntVector *_p_vec;
};

However, I think the correct way to do this as follows. In other words, we have to compare both _pos and _p_vec.

bool Iter::operator!= (const Iter& other) const
{
    return _p_vec != other._p_vec || _pos != other._pos;
}

Question> Whose code is correct?

===Update on how std::vector works on comparison of iterator====

std::vector<int> vecOne { 1, 2, 3};
std::vector<int> vecTwo { 4, 5, 6};

auto iterOne = vecOne.begin();
std::advance(iterOne, 1);

auto iterTwo = vecTwo.begin();
std::advance(iterTwo, 1);

if ( iterOne == iterTwo)
    std::cout << "iterOne == iterTwo" << std::endl;
else
    std::cout << "iterOne != iterTwo" << std::endl;

Output is : iterOne != iterTwo

However,

std::vector<int> foo;
std::vector<int> bar;

if ( foo.begin() == bar.begin() )
    std::cout << "foo.begin() == bar.begin()" << std::endl;
else
    std::cout << "foo.begin() != bar.begin()" << std::endl;

Output is : foo.begin() == bar.begin()

GCC (version 4.7.1)

q0987
  • 34,938
  • 69
  • 242
  • 387
  • 5
    your check is not necessary, as it's UB to compare iterators from two *different* containers... (AFAIK) – Nim Feb 01 '13 at 16:04
  • Are you sure? Comparing two iterators from different container *types* is UB for sure, but also for different containers of the same type? – leemes Feb 01 '13 at 16:06
  • 1
    @leemes, the first would generate a compiler error, the second not, and hence the UB... – Nim Feb 01 '13 at 16:07
  • @leemes "The result of the application of functions in the library to invalid ranges is undefined" and a valid range is a two iterators `[a, b)` such that `b` is reachable from `a`. So yeah, for the same type as well. – Seth Carnegie Feb 01 '13 at 16:08
  • @Nim Well, only STL iterators. Not your custom ones. Nobody tells you that *you shouldn't* define behavior. – leemes Feb 01 '13 at 16:12
  • 1
    Besides the comparison problem, it's a bit odd to store a pointer and an offset when you could just as well have a pointer directly to the current element. – Bo Persson Feb 01 '13 at 16:14
  • @leemes Yes, but in the same way nobody tells the writer of this linked example code to define the behaviour. – Christian Rau Feb 01 '13 at 16:16
  • Oh wow, I thought we were talking about standard iterators. Neeeeevermind. – Seth Carnegie Feb 01 '13 at 16:16
  • @leemes: imagine this stupid example: `my_container a, b;..add some values;// now: for(auto i = a.begin(); i != b.end(); ++i){}`, whether you check the instance or makes no difference in this case, unless you start throwing exceptions etc... – Nim Feb 01 '13 at 16:18
  • @Nim, I have updated my OP and you can see the results of comparing two iterators from two different containers are NOT UB. – q0987 Feb 01 '13 at 16:19
  • @Nim It would be bad design to accept such a code. I personally would put a debug-build-only assertion in the comparison operator. – leemes Feb 01 '13 at 16:19
  • @q0987 UB doesn't mean it has to fail. Anything can happen. Most libraries would go for best performance and hence not check anything they don't have to. – leemes Feb 01 '13 at 16:20
  • 1
    @q0987 *"you can see [...] are NOT UB"* - No, you can't see that. You can only see that in this example it works. But you know what, one of the most evil things about UB is, that it can also *just work*, since *working* is at least *some* behaviour. But then again in the next line/program/library/compiler it can break. UB is one of the reasons why proof by example usually doesn't work that well for C++ language features. – Christian Rau Feb 01 '13 at 16:21
  • @Bo Persson, since you don't like the linked example. Can you refer me to a decent one? – q0987 Feb 01 '13 at 16:27

2 Answers2

2

Also comparing the underlying container reference is an improvement to make sure that, for example, the begin() iterators of two different containers compare equal.

However, iterators of different containers are rarely compared (when using STL algorithms, they never will). So this might be considered an optimization. Think of a loop in which you step from begin() to end(), so the only iterators you are comparing are the "current" one and end(), which are of the same container.

Comparing iterators of standard containers (vector, etc.) is considered undefined behavior. Indeed, since they never are compared in (good) code (for example the standard algorithms), it doesn't have to define a behavior for such cases.

So the author of this Iter class might also want to come back to this point and say: "Comparing iterators of different vectors is undefined behavior."

This being said, if you want to ensure that you never compare iterators of different containers, leave out this check and maybe assert it for debug builds (but don't check it in release builds).

A good example where you might want to compare iterators of different containers is for linked lists, where you define the end of the list being a null pointer (or a pointer to a static null item instance). Consider the iterator being a pointer to a linked list item; in this case, the end() iterator is just a null pointer (or points to this null item). It is the same one for all containers, so you can't implement the check in your comparison method in such cases. Maybe this is one of the reasons why such a comparison isn't defined -- it should return "unequal" when comparing end iterators of different lists, but it can't.

leemes
  • 44,967
  • 21
  • 135
  • 183
  • 1
    Actually I think they're relying on this being defined as UB. – Seth Carnegie Feb 01 '13 at 16:04
  • 1
    Undefined behavior. It means that the compiler allows you to do something, but the result isn't defined by the standard. There are a lot of examples for undefined behavior. Since the standard doesn't define a behavior, it's up to the implementation what to do (it can do *anything*). – leemes Feb 01 '13 at 16:06
  • 1
    @q0987, Undefined Behaviour (i.e. anything could be possible..) – Nim Feb 01 '13 at 16:06
  • @q0987 *"Undefined Behaviour"* - This means the standard doesn't specify what should happen and allows *anything* to happen (including the compiler overheating your CPU and making your computer explode). In practice (for you implementating the standard, or something standard compliant) this especially means you are allowed to completely ignore this situation and can optimize as if it didn't occur, since *if* it really ocures you don't have to care what happens, anyway. So while being one of the most evil sources of errors and confusion, UB is first of all an optimization possibility. – Christian Rau Feb 01 '13 at 16:11
  • Well, comparing *standard iterators* is UB, but if you're writing your own, nobody says you have to implement it conformant to the standard library rules. Hence you can say I want to implement *defined behavior* for comparing iterators of different containers. – leemes Feb 01 '13 at 16:11
  • Yeah sorry, I didn't look at the name of the class under inspection and thought we were talking about a standard library implementation. Carry on. – Seth Carnegie Feb 01 '13 at 16:18
  • 1
    It's not, strictly speaking an **optimization**; it's a design decision. There's no good reason to compare iterators that don't point into the same sequence, so there is no design requirement to support this misuse. – Pete Becker Feb 01 '13 at 16:22
  • @PeteBecker Assertions are intended to detect misuses. See the last paragraph in my answer. Also, it's up to the author of the class how he/she wants to implement comparison of iterators of different containers. – leemes Feb 01 '13 at 16:23
  • @PeteBecker I meant the paragraph before the last. – leemes Feb 01 '13 at 16:32
  • 1
    @leemes - regardless, the **design decision** for iterators is that comparing iterators that do not point into the same sequence doesn't make sense. So not checking is not an optimization; it's coding to specification. Yes, it's legitimate to bulk up an iterator for debugging purposes, but it's checking for incorrect usage, not improving usability. – Pete Becker Feb 01 '13 at 17:02
2

As a general rule, users of iterators are not supposed to compare iterators from different containers. In the standard library, doing so is undefined behavior.

So assuming you are only trying to create iterators that are as robust as standard library ones, comparing the container is not required. However, if you have the pointer to container around, then it would be polite to check that the containers match at least in debug, then assert that you shouldn't be making this comparison.

You are free to check it in release as well, but if your iterator using code is also supposed to work with standard containers, then relying on iterators from different containers comparing not equal is not advised.

See comparing iterators from different containers for someone talking about how it is undefined behavior.

Community
  • 1
  • 1
Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
  • 3
    @q0987 Trying something doesn't tell you it isn't UB. Undefined behavior doesn't mean "segfault", it means *anything can happen*. Including "return false". And every time you check it it could "return false", and it can still be undefined what happens by the C++ standard, and the next iteration of the compiler could segfault, delete your hard drive, or change the screen color to pink when you compare two iterators. Which is why good debugging iterators assert in debug mode when compared between different containers. – Yakk - Adam Nevraumont Feb 01 '13 at 16:23