1996 года). Если у вас возникнут проблемы с переносимостью примеров для компиляторов Microsoft или Borland, попробуйте использовать электронную версию этих программ, доступную в виде файла stdcpp.zip. Некоторые из них сделаны более переносимыми с помощью условной компиляции.

Кроме того, существуют также коммерческие версии STL, которые мы не будем здесь обсуждать. Поскольку STL состоит только из файлов заголовка, замена одной версии на другую является легко решаемой задачей.

1.3. Векторы, списки и двусторонние очереди

в программе readwr.cpp три раза встречается слово vector.

#include <vector>

vector<int> v;

vector<int>::iterator i;

Применение концепции вектора обеспечивает выделение непрерывной памяти, для чего программисты на С обычно пользуются функциями malloc, realloc и free. В качестве альтернативы можно употребить связный список, как рекомендуется в книгах по структурам данных. С помощью STL мы можем использовать (двойные) связные списки, не программируя их самостоятельно. Все, что нам требуется для программы readwr.cpp- заменить всюду слово vector на list, как показано в следующей программе:

readwrl.cpp:Чтение и вывод переменного количества

ненулевых целых (ввод завершается нулем).

Использует список.

#include <iostream>

#include <list>

using namespace std;

int mainO { list<int> v; int x;

cout << Enter positive integers, followed by 0:\n ; while (cin x, x != 0)

v.push back(x); list<int>::iterator i; for (i=v.begin0; i != v.endO; + + i)

cout *i ; cout endl; return 0;

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

Vector<T>

Deque<T>

Вставка и удаление здесь. Произвольный доступ.

Вставка и удаление здесь. Произвольный доступ.

Ust<T>

Вставка и удаление

- в любом месте. Нет

произвольного доступа.

Рисунок 1.1. Свойства трех последовательных контейнеров

Как показано на рисунке 1.1, мы можем эффективно вставлять и удалять элементы только в конце вектора, в начале и конце двусторонней очереди и в любом месте списка. Хотя вектор накладывает сильные ограничения на вставку и удаление, он имеет преимущество в том, что предоставляет произвольный доступ к своим элементам. Некоторые дальнейшие примеры прояснят эти различия. Для полноты изложения необходимо отметить, что существует четвертая разновидность последовательного контейнера, обычный массив, который описывается как

Т а [N] ;

ДЛЯ массива с элементами типа Т. Далее продемонстрируем, что средства STL предоставляют возможность успешно отсортировать массив. Другими словами, STL может быть полезна даже в программах, которые используют обычные массивы, а не типичные контейнеры STL, о чем рассказано в следующем разделе.

Как показано в приведенной ниже таблице, векторы, двусторонние очереди и списки поддерживают различные наборы операций.

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

Для данного типа Т типы vector<T>, deque<T> и list<T> называются последовательными контейнерами.

Операция

Функция

vector deque list

Вставить в конце Удалить в конце Вставить в начале Удалить в начале Вставить в любом месте Удалить в любом месте

push back / У У

popback У У У

push front -

popjront -

insert {/) {/)

erase (*) (*) *

Отсортировать (см. раздел 1.4) sort (алгоритм)

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

До сих пор мы видели только, как используется функция push back. Следующая программа показывает, как использовать все функции для вставки и удаления, перечисленные в вышеприведенной таблице (pushback, popjback, push front, pop front, insert и erase).

II insdel.cpp: Вставка и удаление элементов из списка, iinclude <iostream> iinclude <list> using namespace std;

void showlist(const char *str, const list<int> &L) { list<int>::const iterator i;

cout str endl

for (i=L.begin() ; i != L.endO; ++i) cout *i ;

cout endl;

int main() { list<int> L; int x;

cout Enter positive integers, followed by 0:\n ; while (cin x, x != 0)

L.push back(x); showlist( Initial list: , L); L.push front(123);