На курсах программирования я получил задание — написать на C++ аналог std::vector с сохранением функицонала и интерфейса, с целью сделать его хотя бы в два раза быстрее в миллион раз читабельнее. В ходе выполнения я столкнулся с тем, что Random access итераторы имеют некоторые очень странные интересные особенности, которые мне захотелось изменить. Кому интересно — добро пожаловать под кат.
На Хабре уже есть хорошая статья об итераторах здесь
От себя хочу добавить только определение из статьи об итераторах на Википедии.
Итератор — объект, абстрагирующий за единым интерфейсом доступ к элементам коллекции.
Итак, создадим два вектора целых чисел:
Заполним оба числами от 0 до 14:
Создадим итераторы для каждого вектора:
Первое что бросилось мне в глаза — этот наличие перегруженного оператора "-" и отсутствие перегруженного оператора "+" для двух итераторов (сложение итератора с интом предусмотрено). Создадим дополнительный итератор для первого вектора и проделаем оба действия:
В первом случае получаем на выходе 3, во втором — ошибку компиляции.
Во-вторых, меня заинтересовал вопрос равенства итераторов. Исходя из определения, итератор должен обеспечивать доступ к элементам коллекции. Т. е. если два итератора принадлежат разным коллекциям, кэп подсказывает, что сравнивать их вообще нельзя. Однако:
На выходе имеем «Not equal», что при странности самой возможности такого сравнения, весьма логично.
После того, как я понял, что сравнивать итераторы разных объектов можно, решил попробовать вычесть один из другого:
На выходе получаем 34. Сразу вспомнился Пелевин и его «Числа».
То, что на выходе мы получаем непредсказуемый инт связано с тем, как располагаются векторы в памяти относительно друг друга. Попробовав позаполнять оба вектора разным количеством чисел, получал совершенно разный результат.
Ну и самое интересное:
На выходе, как Вы уже догадались «Equal». Это ведёт к следующему, неутешительному с моей точки зрения выводу, что:
позволит нам итерировать первый вектор, а не второй.
При создании Random access iterator разработчики не ограничили использование итератора только рамками того контейнера, для которого он был создан. Я могу понять их логику, хотя лично мне она не по душе. Закрыть сравнение и вычитание итераторов, указывающих на разные вектора было бы не очень сложно. И хотя, возможно, такие ситуации встречаются редко, не стоит забывать об этих особенностях.
Коротко об итераторах
На Хабре уже есть хорошая статья об итераторах здесь
От себя хочу добавить только определение из статьи об итераторах на Википедии.
Итератор — объект, абстрагирующий за единым интерфейсом доступ к элементам коллекции.
Создаём итератор
Итак, создадим два вектора целых чисел:
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
Взято с 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 разработчики не ограничили использование итератора только рамками того контейнера, для которого он был создан. Я могу понять их логику, хотя лично мне она не по душе. Закрыть сравнение и вычитание итераторов, указывающих на разные вектора было бы не очень сложно. И хотя, возможно, такие ситуации встречаются редко, не стоит забывать об этих особенностях.