Interesting logic of random access iterators in STL containers

In programming courses, I got the task of writing an analogue of std :: vector in C ++ with preserving the functional and interface, in order to make it at least twice as fast, a million times more readable. During execution, I came across the fact that Random access iterators have some very strange interesting features that I wanted to change. Who cares - welcome to cat.

Briefly about iterators

On Habré there is already a good article on iterators here
From myself I want to add only the definition from the article on iterators on Wikipedia.
An iterator is an object that abstracts access to the elements of a collection behind a single interface.
Create an iterator

So, create two integer vectors:
	vector vector1;
	vector vector2;

Fill both numbers from 0 to 14:
	for ( int i = 0; i < 15; i++ ) {

Create iterators for each vector:
	vector::iterator it1 = vector1.begin();
	vector::iterator it2 = vector2.begin();

Actually interesting features

The first thing that caught my eye was the presence of an overloaded operator "-" and the absence of an overloaded operator "+" for two iterators (adding an iterator with an int is provided). Create an additional iterator for the first vector and do both actions:
	vector::iterator temp = vector1.begin() + 3;
	cout << temp - it1 << endl;
	cout << temp + it1 << endl;

In the first case, we get output 3, in the second - a compilation error.

Secondly, I was interested in the issue of equality of iterators. Based on the definition, the iterator should provide access to the elements of the collection. That is, if two iterators belong to different collections, the cap suggests that you cannot compare them at all. However:
	if ( it1 == it2 ) {
		cout << "Equal" << endl;
	} else {
		cout << "Not equal" << endl;

At the output we have “Not equal”, which, with the strangeness of the very possibility of such a comparison, is very logical.
After I realized that it is possible to compare iterators of different objects, I decided to try to subtract one from the other:
	cout << it1 - it2 << endl;

At the exit we get 34. I immediately remembered Pelevin and his "Numbers".
Brief Summary
The hero of Pelevin's new novel, The Numbers, is Stepan’s businessman. As a child, Styopa realized that he was not like everyone else. Styopa felt an inexplicable latent craving for the number 7, but did not understand how to please this great number, which is worshiped by so many talented people. As a result, he realized that 7 is nothing more than 3 + 4 (which we will see later), so he began to worship the number 34, subjecting him to his whole life.
Taken from

The fact that at the output we get an unpredictable int is related to how the vectors are located in memory relative to each other. Having tried to fill both vectors with a different number of numbers, I got a completely different result.

Well and the most interesting:
	it2 += 34;
	if ( it1 == it2 ) {
		cout << "Equal" << endl;
	} else {
		cout << "Not equal" << endl;

At the exit, you guessed it, Equal. This leads to the following conclusion, which is unfavorable from my point of view, that:
	it2 = vector2.begin() + 34;

will allow us to iterate the first vector, not the second.


When creating Random access iterator, the developers did not limit the use of the iterator to the scope of the container for which it was created. I can understand their logic, although I personally do not like it. Close comparison and subtraction of iterators pointing to different vectors would not be very difficult. And although, perhaps, such situations are rare, do not forget about these features.

Also popular now: