How exactly iterators are being compared?

Question

#include <iostream>
#include <set>
using namespace std;
int main() {
  set<int> numbers;
  numbers.insert(1);
  auto numbers_find = numbers.find(1);
  auto numbers_end = numbers.end();
  cout<<*numbers_find<<endl;
  cout<<*numbers_end<<endl;
  cout<<(numbers_find==numbers_end?"true":"false")<<endl;
  return 0;
}

In that case output would be

1
1
false

As well as I understand iterators are basically pointers, but only for elements of STL collections. So my question is - what exactly is being compared when we comparing two iterators, I assume this is some kind of equivalent of address that pointer points to. But, according to pointers logic, if two iterators pointing to the same element, then it would make sense if they were equal.

int a = 5;
int *ptr1 = &a;
int *ptr2 = &a;
cout<<((ptr1==ptr2)?"true":"false")<<endl;

Output

true

P.S. Link to code example above https://repl.it/@VanyaRyanichev/FrillyPapayawhipMonitor#main.cpp

Does dereferencing the end iterator have any relevance to your question? You can't do that. — chris, Jul 06 '20 at 11:03
`*numbers_end` is UB. It's like `int *ptr2 = &a + 1; cout << *ptr2; /* how come it prints 1 but ptr1 == ptr2 is false? */` — user253751, Jul 06 '20 at 11:03
As i understand from your question you expect t the output of cout<<(numbers_find==numbers_end?"true":"false")< — Farhad Sarvari, Jul 06 '20 at 11:07
@FarhadSarvari Yeah, but since ```numbers``` contains only one element, ```numbers_end``` and ```numbers_find``` are pointing to the same element, is that correct? — Vanya Ryanichev, Jul 06 '20 at 11:11
@VanyaRyanichev It points to the end of the first element, i.e. it points to the non-existent second element. Since there isn't a second-element, dereferencing it is UB — user253751, Jul 06 '20 at 11:21
Going into implementations details (that may vary), `std::set` is a binary search tree. `std::set::iterator` is a class that internally holds a pointer to a tree node. When you compare iterators, you compare those pointers. `std::set::end()` points to some sentinel node and cannot be dereferenced because that sentinel node is not a "full" node and doesn't hold any user data, but only `left`, `right`, and `parent` pointers. — Evg, Jul 06 '20 at 11:22
@Vanya Ryanichev Please check this https://en.cppreference.com/w/cpp/container/set/end. You can observe the end pointer visually. — Farhad Sarvari, Jul 06 '20 at 11:25
[What's the difference between “STL” and “C++ Standard Library”?](https://stackoverflow.com/questions/5205491/whats-the-difference-between-stl-and-c-standard-library) — Evg, Jul 06 '20 at 11:54

score 4 · Accepted Answer · answered Jul 06 '20 at 11:06

4

The end iterator does not point to the last element, it doesn't point to anything. Your program is ill-formed (has undefined behaviour).

C++ expresses sequences as half-open intervals

answered Jul 06 '20 at 11:06

Caleth

52,200
2
44
75

Apparently this is something very simple, but how then ```*numbers_end``` gives us ```1``` ??? – Vanya Ryanichev Jul 06 '20 at 11:15
5

Undefined behavior means anything can happen. Apparently in your case a value `1` is returned. In my case I get a crash (MSVC 2019). – rustyx Jul 06 '20 at 11:16
@rustyx just compiled the code above with MSVC, and it is really UB, ***gcc*** and ***clang*** are handling it as ```numbers_end``` always points to last element, thank you – Vanya Ryanichev Jul 06 '20 at 11:27
3

@VanyaRyanichev, no, internally it doesn't point to the last element. Replace `1` with `12` and you'll see. – Evg Jul 06 '20 at 11:29
@Evg I just initialized ```numbers``` with ```{1,2,3}``` , and using gcc ```*numbers_end``` gives me 3 – Vanya Ryanichev Jul 06 '20 at 11:40
@VanyaRyanichev `*numbers.end()` gives you undefined behavior. It doesn't matter if it happened to return 3 this time. Look what it points at: https://en.cppreference.com/w/cpp/container/set/end – Ted Lyngmo Jul 06 '20 at 11:43
1

@VanyaRyanichev, but when you insert `12`, the output is `1`. The behaviour is undefined, anything can happen. – Evg Jul 06 '20 at 11:44
@Evg yeah, I see, it's not always returns last element – Vanya Ryanichev Jul 06 '20 at 11:46
3

@VanyaRyanichev Ok, but you seem stuck on that it sometimes returns a value similar to a value you've put into the container. As long as you have undefined behavior comparing it to _anything_ is pointless. – Ted Lyngmo Jul 06 '20 at 11:48

How exactly iterators are being compared?

1 Answers1