C ++ Iterator, Почему нет базового класса Iterator, от которого наследуются все итераторы

11

Я готовлюсь к экзамену, и у меня есть вопрос, на который я стараюсь дать ответ.

Почему не существует базового класса итераторов, от которого наследуются все остальные итераторы?

Полагаю, мой учитель ссылается на иерархическую структуру из ссылки на cpp " http://prntscr.com/mgj542 ", и мы должны предоставить другую причину, чем почему они должны это делать?

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

Вероятно, это специализированные шаблоны в зависимости от контейнера, верно?

объединенный
источник
2
Поделиться своими исследованиями помогает всем . Расскажите нам, что вы пробовали и почему это не соответствует вашим потребностям. Это свидетельствует о том, что вы потратили время, чтобы попытаться помочь себе, избавляет нас от повторения очевидных ответов и, прежде всего, помогает получить более конкретный и актуальный ответ. Также смотрите Как Ask
комар
5
« Почему не существует базового класса итератора, от которого наследуются все другие итераторы? » Гм ... почему он должен быть?
Никол Болас

Ответы:

14

Вы уже получили ответы, указывающие на то, почему не нужно, чтобы все итераторы наследовали от одного базового класса Iterator. Я получил немного дальше, хотя. Одной из целей C ++ является абстракция с нулевыми затратами времени выполнения.

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

Давайте рассмотрим, например, простую иерархию итераторов, которая использует наследование и виртуальные функции:

template <class T>
class iterator_base { 
public:
    virtual T &operator*() = 0;
    virtual iterator_base &operator++() = 0;
    virtual bool operator==(iterator_base const &other) { return pos == other.pos; }
    virtual bool operator!=(iterator_base const &other) { return pos != other.pos; }
    iterator_base(T *pos) : pos(pos) {}
protected:
    T *pos;
};

template <class T>
class array_iterator : public iterator_base<T> {
public: 
    virtual T &operator*() override { return *pos; }
    virtual array_iterator &operator++() override { ++pos; return *this; }
    array_iterator(T *pos) : iterator_base(pos) {}
};

Тогда давайте проведем быстрый тест:

int main() { 
    char input[] = "asdfasdfasdfasdfasdfasdfasdfadsfasdqwerqwerqwerqrwertytyuiyuoiiuoThis is a stringy to search for something";
    using namespace std::chrono;

    auto start1 = high_resolution_clock::now();
    auto pos = std::find(std::begin(input), std::end(input), 'g');
    auto stop1 = high_resolution_clock::now();

    std::cout << *++pos << "\n";

    auto start2 = high_resolution_clock::now();
    auto pos2 = std::find(array_iterator(input), array_iterator(input+sizeof(input)), 'g');
    auto stop2 = high_resolution_clock::now();

    std::cout << *++pos2 << "\n";

    std::cout << "time1: " << duration_cast<nanoseconds>(stop1 - start1).count() << "ns\n";
    std::cout << "time2: " << duration_cast<nanoseconds>(stop2 - start2).count() << "ns\n";
}

[примечание: в зависимости от вашего компилятора вам может потребоваться сделать немного больше, например, определить iterator_category, diff__type, reference и т. д., чтобы компилятор принял итератор.]

И вывод:

y
y
time1: 1833ns
time2: 2933ns

[Конечно, если вы запустите код, ваши результаты не будут точно соответствовать.]

Таким образом, даже для этого простого случая (и выполняющего только около 80 приращений и сравнений) мы добавили около 60% накладных расходов к простому линейному поиску. Особенно, когда итераторы были первоначально добавлены в C ++, довольно много людей просто не приняли бы дизайн с такими большими накладными расходами. Они, вероятно, не были бы стандартизированы, и даже если бы они были, практически никто не использовал бы их.

Джерри Гроб
источник
7

Разница между тем, что что-то есть, и тем, как что-то ведет себя.

Многие языки пытаются объединить эти два понятия, но это совершенно разные вещи.

Если как и что и как ...

Если все наследуется, objectтогда получаются некоторые преимущества, такие как: любая переменная объекта может содержать любое значение. Но это также проблема, все должно вести себя ( как ) как objectи и похоже ( что ) object.

Но:

  • Что если у вашего объекта нет значимого определения равенства?
  • Что делать, если у него нет значимого хэша?
  • Что если ваш объект не может быть клонирован, но объекты могут быть?

Либо objectтип становится по существу бесполезным - из-за объекта, не обеспечивающего общности во всех возможных экземплярах. Или же будут существовать объекты, у которых есть сломанное / подкаблучное / абсурдное определение некоторого предполагаемого универсального свойства, найденного на основе, objectкоторое обеспечивает почти универсальное поведение, за исключением ряда уловок.

Если что не связано с тем, как

В качестве альтернативы вы можете оставить раздел « Что и как» . Тогда несколько различных типов (с ничего общего у всех , что ) все это может вести себя таким же образом , как видно из соавтора Хау . В этом смысле идея Iteratorне является чем-то конкретным , а как . В частности, как вы взаимодействуете с вещами, когда вы еще не знаете, с чем взаимодействуете.

Java (и аналогичные) позволяют подходить к этому с помощью интерфейсов. Интерфейс в этом отношении описывает средства связи и, неявно, протокол связи и действий, которые соблюдаются. Любое То, что заявляет о себе как о данном Как , заявляет, что оно поддерживает соответствующие коммуникации и действия, изложенные в протоколе. Это позволяет любому Соавтор полагаться на Хау и не увязнуть, указав , какие именно Какие «s могут быть использованы.

C ++ (и аналогичные) позволяют подходить к этому посредством утки. Шаблону не важно, объявляет ли сотрудничающий тип, что он следует поведению, только в пределах данного контекста компиляции, с которым объект может взаимодействовать определенным образом. Это позволяет указателям C ++ и объектам, перекрывающим определенные операторы, использоваться одним и тем же кодом. Потому что они соответствуют контрольному списку, чтобы считаться эквивалентным.

  • поддерживает * a, a->, ++ a и a ++ -> итератор ввода / вывода
  • поддерживает * a, a->, ++ a, a ++, --a и a-- -> двунаправленный итератор

Базовый тип даже не должен выполнять итерации контейнера, это может быть что угодно . Кроме того, это позволяет некоторым соавторам быть еще более универсальными, представьте, что функция нуждается только в ней a++, итератор может удовлетворить это, как и указатель, так и целое число, так же как и любой объект, реализующий operator++.

Под и над спецификацией

Проблема с обоими подходами находится под и над спецификацией.

Использование интерфейса требует, чтобы объект объявил, что поддерживает заданное поведение, что также означает, что создатель должен наполнить его с самого начала. Это приводит к некоторому Что «S , чтобы не делать разрез, так как они не объявляли его. Это также означает , что когда - нибудь , что имеет общий предок, интерфейс , представляющий Хау . Это круг назад к первоначальной проблеме object. Это заставляет соавторов переопределять свои требования, одновременно вызывая невозможность использования некоторых объектов из-за отсутствия объявлений или скрытых ошибок, так как ожидаемое поведение плохо определено.

Использование шаблона требует, чтобы соавтор работал с совершенно неизвестным « Что» , и через свои взаимодействия он определяет « Как» . В некоторой степени это усложняет написание коллабораторов, так как он должен анализировать What для своих примитивов связи (функции / поля / и т. Д.), Избегая при этом ошибок компиляции, или, по крайней мере, указывать, как данное What не соответствует его требованиям для How . Это позволяет коллаборационисту требовать абсолютного минимума от любого заданного « Что» , что позволяет широчайший диапазон того, что должно быть использовано. К сожалению, у этого есть недостаток, позволяющий бессмысленное использование объектов, которые технически предоставляют коммуникационные примитивы для данногоКак , но не следуйте подразумеваемому протоколу, позволяющему совершать всевозможные плохие вещи.

итераторы

В этом случае Iteratorявляется Как это сокращение для описания взаимодействия. Все, что соответствует этому описанию, по определению Iterator. Знание как позволяет нам писать общие алгоритмы и иметь короткий список « как дано конкретное что », которые необходимо предоставить, чтобы заставить алгоритм работать. Этим списком являются функция / свойства / и т. Д., Их реализация учитывает конкретные аспекты алгоритма.

Kain0_0
источник
6

Потому что C ++ не должен иметь (абстрактных) базовых классов для полиморфизма. Он имеет структурный подтип, а также номинативный подтип .

Сбивает с толку в конкретном случае итераторов, предыдущие стандарты определены std::iteratorкак (приблизительно)

template <class Category, class T, class Distance = std::ptrdiff_t, class Pointer = T*, class Reference = T&>
struct iterator {
    using iterator_category = Category;
    using value_type = T;
    using difference_type = Distance;
    using pointer = Pointer;
    using reference = Reference;
}

Т.е. как просто поставщик необходимых типов членов. Это не имело никакого поведения во время выполнения, и было объявлено устаревшим в C ++ 17

Обратите внимание, что даже это не может быть общей основой, так как шаблон класса не является классом, каждое создание является отдельным от других.

Caleth
источник
5

Одна из причин заключается в том, что итераторы не обязательно должны быть экземплярами класса. Например, во многих случаях указатели являются очень хорошими итераторами, и, поскольку они являются примитивами, они не могут наследовать ни от чего.

Дэвид Торнли
источник