Оценка числа элементов и размеров контейнера

↑

▷ Содержание

⇐ ПредыдущаяСтр 7 из 10Следующая ⇒

Сравнение контейнеров

Для однотипных контейнеров сравнение может быть выполнено с помощью стандартных операций отношений ==,!=, <, <=, >, >=.

Отношения <, <=, >, >= проверяются по лексикографическому критерию. В этом случае два контейнера сравниваются с учетом интервалов размещения элементов [beg1, end1) и [beg2, end2). Элементы из интервалов сравниваются попарно до тех пор, пока не будет выполнено одно из условий:

· если очередные два элемента не равны, то результат этих элементов сравнения определяет результат сравнения контейнеров;

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

Присваивание контейнеров и обмен содержимым

Все типы контейнеров имеют общие операции вставки и удаления:

Методы частного применения

push_back() – вставка элемента в конец контейнера; применим к деку, вектору, списку.

push_front() – вставка элемента в начало контейнера; применим к деку, списку.

pop_back() – удаление последнего элемента контейнера; применим к деку, вектору, списку.

pop_front() – удаление элемента из начала контейнера; применим к деку, списку

Методы pop_back() и pop_front() не возвращают удаленное значение.

Для считывания первого элемента используется метод front(), а для считывания последнего элемента – метод back().

Контейнер vector эффективно обрабатывает произвольную выборку элементов с помощью операции индексации [] или метода at, который аналогичен операции индексации, но в отличие от нее проверяет выход за границу вектора (генерирует исключение out_of_range, если такое нарушение обнаруживается).

Действия методов вставки и удаления:

push_back() push_front()

элементы последовательности

pop_back() pop_front()

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

Обозначения в таблице:

O(1) – длительность операции не зависит от числа элементов в контейнере;

O(n) – длительность операции пропорциональна числу элементов в контейнере;

+ – суффикс, обозначающий, что длительность исполнения операции может возрастать;

- – неприменимость операции к контейнеру.

Итераторы

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

Существуют итераторы:

· однонаправленные (прямые); если нужно продвигаться вперед, но при этом совершать как запись, так и чтение, используется «прямой» итератор;

· двунаправленные;

· обеспечивающие произвольное перемещение (произвольный доступ); итератор «произвольного доступа» обеспечивает доступ к элементу контейнера без всяких продвижений.

Имеются два специализированных типа итераторов:

· потоковые итераторы, благодаря которым входные и выходные потоки могут вести себя как итераторы:

§ ostream_iterator – итератор выходного потока; используется, если требуется только лишь продвинуться на один шаг по контейнеру для осуществления последовательной записи, например, при записи в файл или выводе на экран;

§ istream_iterator – итератор входного потока; используется, если требуется только лишь продвинуться на один шаг по контейнеру. для осуществления последовательного чтения, например, при чтении из файлов или с клавиатуры.

· адаптеры итераторов – варианты модификации обычного итератора, которые могут необычным способом изменять поведение обычных итераторов:

o обратный итератор (reverse_iterator) для реверсного прохода контейнера (в обратном направлении);

o итератор вставки:

§ back_inserter вставляет новые элементы в конец контейнера

§ front_inserter вставляет новые элементы в начало контейнера (кроме вектора)

§ inserter вставляет новые элементы в указанное место

o итератор неинициализированного хранения, позволяющий хранить данные в неинициализированном еще участке памяти.

Для просмотра контейнеров с помощью итераторов в каждом контейнере определены методы:

Алгоритмы

Алгоритм – независимая шаблонная функция, производящая действия над элементами контейнера (для ее использования к программе подключается заголовочный файл <algorithm>). Алгоритмы можно использовать и при работе с обычными массивами С++.

Наиболее популярные алгоритмы STL:

В списках параметров всех алгоритмов первые два параметра задают диапазон обрабатываемых элементов в виде полуинтервала [first, last), где first – итератор, указывающий на начало диапазона, а last – итератор, указывающий на выход за границы диапазона, т.е. на элемент, располагающийся за последним.

Например, массив int arr[7] = {15, 2, 19, -3, 28, 6, 8};

можно отсортировать с помощью алгоритма sort: sort (arr, arr +7);

Здесь имя массива arr (имеющее тип указателя int*) используется как итератор.

Примеры

Познавательные статьи:



Алгоритмические операторы Matlab

Конструирование и порядок расчёта дорожной одежды

Исследования учёных: почему помогают молитвы?

Почему терпят неудачу многие предприниматели?