С++ std::vector <>:: Итератор не является указателем, почему?

Просто небольшое введение, с простыми словами. В С++ итераторы - это "вещи", на которых вы можете написать, по крайней мере, оператор разыменования *it, оператор инкремента ++it, а для более продвинутых двунаправленных итераторов - декремент --it и, что не менее важно, для случайных Итераторам доступа необходим индекс оператора it[] и, возможно, сложение и вычитание.

Такие "вещи" на С++ являются объектами типов с соответствующими перегрузками оператора, или простые и простые указатели.

std::vector<> - это класс контейнера, который обертывает непрерывный массив, поэтому указатель как итератор имеет смысл. В сетях и в какой-то литературе вы можете найти vector.begin(), используемый в качестве указателя.

Обоснование использования указателя - это меньшие накладные расходы, более высокая производительность, особенно если оптимизирующий компилятор обнаруживает итерацию и делает свою вещь (векторные инструкции и прочее). Использование итераторов может быть сложнее оптимизировать компилятор.

Зная это, мой вопрос в том, почему современные реализации STL, скажем, MSVС++ 2013 или libstdС++ в Mingw 4.7, используют специальный класс для векторных итераторов?

Ответ 1

Вы совершенно правы, что vector::iterator может быть реализован простым указателем (см. здесь) - на самом деле концепция итератор основан на указателе на элемент массива. Однако для других контейнеров, таких как map, list или deque, указатель не будет работать вообще. Так почему же это не сделано? Вот три причины, по которым реализация класса предпочтительна над необработанным указателем.

Реализация итератора как отдельного типа позволяет, например, добавить дополнительную функциональность (помимо того, что требуется стандартом) (добавлено в edit после комментария Quentins) возможность добавления утверждений при разыменовании итератора, например, при отладке режим.
разрешение перегрузки Если итератор был указателем T*, он мог быть передан как действительный аргумент функции, принимающей T*, в то время как это было бы невозможно с типом итератора, Таким образом, при создании std::vector<>::iterator указатель фактически изменяет поведение существующего кода. Рассмотрим, например,
```
template<typename It>
void foo(It begin, It end);
void foo(const double*a, const double*b, size_t n=0);

std::vector<double> vec;
foo(vec.begin(), vec.end());    // which foo is called?
```
зависящий от аргумента поиск (ADL; указатель juanchopanza). Если вы выполняете неквалифицированный вызов, ADL гарантирует, что функции в namespace std будут найдены только в том случае, если аргументы определены типами в namespace std. Таким образом,
```
std::vector<double> vec;
sort(vec.begin(), vec.end());             // calls std::sort
sort(vec.data(), vec.data()+vec.size());  // fails to compile
```
std::sort не найден, если vector<>::iterator был простым указателем.

Ответ 2

Реализация итератора - это реализация, которая соответствует требованиям стандарта. Это может быть указатель на vector, который будет работать. Существует несколько причин не использовать указатель;

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

Если все итераторы были указателями, то ++it на map не увеличивал бы его до следующего элемента, так как память не должна быть непересекающейся. Прошедшая непрерывная память std:::vector для большинства стандартных контейнеров требует "умных" указателей - отсюда итераторы.

Физическое требование итератора-гольца очень хорошо связано с логическим требованием, что движение между элементами - это четко определенная "идиома" итерации по ним, а не просто переход к следующей ячейке памяти.

Это было одним из оригинальных требований и целей проекта STL; ортогональная связь между контейнерами, алгоритмы и подключение двух через итераторы.

Теперь, когда они являются классами, вы можете добавить весь набор проверок ошибок и проверки работоспособности для отладки кода (а затем удалить его для более оптимизированного кода выпуска).

Учитывая положительные аспекты, основанные на итераторах на основе классов, вы должны или не должны использовать указатели для std::vector итераторов - согласованность. Ранние реализации std::vector действительно использовали простые указатели, вы можете использовать их для vector. Как только вам придется использовать классы для других итераторов, учитывая положительные результаты, которые они приносят, применение этой функции к vector становится хорошей идеей.

Ответ 3

Поскольку STL был разработан с идеей, что вы можете написать что-то, что итерации над итератором, независимо от того, эквивалентен ли этот итератор указателю на элемент массивов, связанных с памятью (например, std::array или std::vector) или что-то вроде связанного списка, набора ключей, чего-то, что генерируется "на лету" при доступе и т.д.

Кроме того, не обманывайте себя: в векторном случае разыменование может (без параметров отладки) просто ломаться до развёртывания указательного курсора, поэтому после компиляции даже не будет накладных расходов!

Ответ 4

Обоснование использования указателя меньше накладных расходов, выше производительность, особенно если оптимизирующий компилятор обнаруживает итерацию и делает свою вещь (векторные инструкции и прочее). Использование итераторов может быть сложнее оптимизировать компилятор.

Это недоразумение в основе вопроса. Хорошо сформированная реализация класса не будет иметь накладных расходов и одинаковой производительности, потому что компилятор может оптимизировать абстракцию и рассматривать класс итератора как просто указатель в случае std::vector.

Тем не менее,

MSVС++ 2013 или libstdС++ в Mingw 4.7, используйте специальный класс для вектора итераторы

поскольку они считают, что добавление слоя абстракции class iterator для определения понятия итерации по std::vector более выгодно, чем использование обычного указателя для этой цели.

Абстракции имеют разный набор затрат и выгод, обычно добавляя сложность дизайна (не обязательно связанные с производительностью или накладными расходами) в обмен на гибкость, будущую проверку, скрывая детали реализации. Вышеупомянутые компиляторы решили, что добавленная сложность - это подходящая стоимость для оплаты выгод от абстракции.

Ответ 5

Обоснование использования указателя меньше накладных расходов, выше производительность, особенно если оптимизирующий компилятор обнаруживает итерацию и делает свою вещь (векторные инструкции и прочее). Использование итераторов может быть сложнее оптимизировать компилятор.

Возможно, но это не так. Если ваша реализация не является полным shite, структура, обертывающая указатель, достигнет той же скорости.

С учетом этого легко видеть, что простые преимущества, такие как улучшенные диагностические сообщения (именование итератора вместо T *), лучшее разрешение перегрузки, ADL и отладка, делают структуру явным победителем над указателем. Необработанный указатель не имеет преимуществ.

Ответ 6

Я преодолел это надоедливое препятствие путем разыменования и сразу же обратился к итератору снова. Это выглядит смешно, но оно удовлетворяет MSVC...

class Thing {
  . . .
};

void handleThing(Thing* thing) {
  // do stuff
}

vector<Thing> vec;
// put some elements into vec now

for (auto it = vec.begin(); it != vec.end(); ++it)
  // handleThing(it);   // this doesn't work, would have been elegant ..
  handleThing(&*it);    // this DOES work