CODEWITHSUNDEEP
c++stliteratorset
DEBNATH KUNDU
DEBNATH KUNDU

Reputation: 61

Why does the iterator to set::end in C++ dereferences to the number of elements in the set?

In C++-STL, set::end() returns an iterator pointing to past-the-last element of the set container. Since it does not refer to a valid element, it cannot de-referenced end() function returns a bidirectional iterator.

But when I execute the following code: 

set<int> s;

s.insert(1);
s.insert(4);
s.insert(2);

// iterator pointing to the end
auto pos2 = s.end();
cout<<*pos2;

it prints 3 as output. The output increases as I insert more elements to the set and is always equal to the total number of elements in the set.

Why does this happen?

Upvotes: 4

Views: 405

Answers (3)

juanchopanza
juanchopanza

Reputation: 227518

Although it is undefined behaviour, in this particular case the observed behaviour could be due to implementation details of the standard library in use.

std::set::size() has O(1) complexity, but std::set is a node-based container (internally a binary search tree). So the size needs to be stored somewhere withing the data structure. It could be that the end() iterator points at a location that doubles as storage for the size, and by pure chance, you're able to access it.

Upvotes: 3

Nikos C.
Nikos C.

Reputation: 51910

Since it does not refer to a valid element, it cannot de-referenced

It can, as your test code demonstrated. However, it shouldn't be dereferenced.

Upvotes: 2

AVH
AVH

Reputation: 11516

Dereferencing the end() iterator is undefined behavior, so anything is allowed to happen. Ideally you'd get a crash, but unfortunately that doesn't seem to be the case here and everything "seems" to work.

Upvotes: 8

Related Questions