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 main()

{    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.begin(); i != v.end(); ++i) cout « *i « " " ;

cout << endl;

return 0; }

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

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

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


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

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

Т a [N] ;

для массива с элементами типа Т. Далее продемонстрируем, что средства STL предоставляют возможность успешно отсортировать массив


<< назад вперед >>