Интересная логика Random access итераторов в STL контейнерах

в 18:08, , рубрики: c++, container, iterator, stl, Песочница, метки: , , ,

На курсах программирования я получил задание — написать на C++ аналог std::vector с сохранением функицонала и интерфейса, с целью сделать его хотя бы в два раза быстрее в миллион раз читабельнее. В ходе выполнения я столкнулся с тем, что Random access итераторы имеют некоторые очень странные интересные особенности, которые мне захотелось изменить. Кому интересно — добро пожаловать под кат.

Коротко об итераторах

На Хабре уже есть хорошая статья об итераторах здесь
От себя хочу добавить только определение из статьи об итераторах на Википедии.
Итератор — объект, абстрагирующий за единым интерфейсом доступ к элементам коллекции.

Создаём итератор

Итак, создадим два вектора целых чисел:

	vector<int> vector1;
	vector<int> vector2;

Заполним оба числами от 0 до 14:

	for ( int i = 0; i < 15; i++ ) {
		vector1.push_back(i);
		vector2.push_back(i);
	}

Создадим итераторы для каждого вектора:

	vector<int>::iterator it1 = vector1.begin();
	vector<int>::iterator it2 = vector2.begin();

Собственно интересные особенности

Первое что бросилось мне в глаза — этот наличие перегруженного оператора "-" и отсутствие перегруженного оператора "+" для двух итераторов (сложение итератора с интом предусмотрено). Создадим дополнительный итератор для первого вектора и проделаем оба действия:

	vector<int>::iterator temp = vector1.begin() + 3;
	cout << temp - it1 << endl;
<s>	cout << temp + it1 << endl;</s>

В первом случае получаем на выходе 3, во втором — ошибку компиляции.

Во-вторых, меня заинтересовал вопрос равенства итераторов. Исходя из определения, итератор должен обеспечивать доступ к элементам коллекции. Т. е. если два итератора принадлежат разным коллекциям, кэп подсказывает, что сравнивать их вообще нельзя. Однако:

	if ( it1 == it2 ) {
		cout << "Equal" << endl;
	} else {
		cout << "Not equal" << endl;
	}

На выходе имеем «Not equal», что при странности самой возможности такого сравнения, весьма логично.
После того, как я понял, что сравнивать итераторы разных объектов можно, решил попробовать вычесть один из другого:

	cout << it1 - it2 << endl;

На выходе получаем 34. Сразу вспомнился Пелевин и его «Числа».

Краткая аннотация

Герой нового романа Пелевина «Числа» — бизнесмен Степа. Еще в детстве Степа понял, что он не такой как все. Степа ощущал необъяснимую латентную тягу к числу 7, но не понимал как угодить этому великому числу, которому поклоняется столько талантливых людей. В итоге он понял, что 7 это не что иное, как 3 + 4 (в чем мы с вами убедимся чуть позже), поэтому начал поклоняться числу 34, подчинив ему всю жизнь.
Взято с pelevin.nov.ru/stati/o-lleo2/1.html

То, что на выходе мы получаем непредсказуемый инт связано с тем, как располагаются векторы в памяти относительно друг друга. Попробовав позаполнять оба вектора разным количеством чисел, получал совершенно разный результат.

Ну и самое интересное:

	it2 += 34;
	if ( it1 == it2 ) {
		cout << "Equal" << endl;
	} else {
		cout << "Not equal" << endl;
	}

На выходе, как Вы уже догадались «Equal». Это ведёт к следующему, неутешительному с моей точки зрения выводу, что:

	it2 = vector2.begin() + 34;

позволит нам итерировать первый вектор, а не второй.

Выводы

При создании Random access iterator разработчики не ограничили использование итератора только рамками того контейнера, для которого он был создан. Я могу понять их логику, хотя лично мне она не по душе. Закрыть сравнение и вычитание итераторов, указывающих на разные вектора было бы не очень сложно. И хотя, возможно, такие ситуации встречаются редко, не стоит забывать об этих особенностях.

Автор: HuanTarget

Поделиться

* - обязательные к заполнению поля