На курсах программирования я получил задание — написать на 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. Сразу вспомнился Пелевин и его «Числа».
Взято с 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