Библиотека STL

Представление массива строк

Списковое представление строк

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

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

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

Наиболее распространенным способом решения представленной задачи является использования функции расстановки или хэширования. Хэш функция - такая функция, которая сложному объекту ставит в соответствие простой объект. В данном случае в соответствие строке ставится число. При добавлении новой строки вычисленное хэш-значение становится индексом строки. Тогда поиск строки происходит за линейное время. Если несколько строк имеют одинаковое значение хэш-функции, они помещаются в список.

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

Например, функцией расстановки может являться коды двух первых букв строк. Более эффективной функцией является (P*X+Q)%n, где n - предполагаемое количество строк в массиве, P и Q - некоторые простые числа, близкие по порядку к n, X - вычисленная сумма кодов букв слова. Очевидно, что размер пустого массива в этом случае составит n строк.

Также эффективным является представление в виде бинарного дерева.

Наиболее эффективным, но и достаточно сложным, является предтавление в виде структуры "бор".

Стандартная библиотека шаблонов (STL) (англ. Standard Template Library) — набор согласованных обобщённых алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций в C++.

Стандартная библиотека шаблонов до включения в стандарт C++ была сторонней разработкой, в начале — фирмы HP, а затем SGI. Стандарт языка не называет её «STL», так как эта библиотека стала неотъемлемой частью языка, однако многие люди до сих пор используют это название, чтобы отличать её от остальной части стандартной библиотеки (потоки ввода/вывода (iostream), подраздел Си и др.).

Контейнер (container) - хранение набора объектов в памяти.

Итератор (iterator) - обеспечение средств доступа к содержимому контейнера.

vector – C-подобный динамический массив произвольного доступа с автоматическим изменением размера при добавлении/удалении элемента. Доступ по индексу за O(1). Добавление-удаление элемента в конец vector занимает амортизированное O(1) время, та же операция в начале или середине vector — O(n). Стандартная быстрая сортировка за O(n * log(n)). Поиск элемента перебором занимает O(n). Существует специализация шаблона vector для типа bool, которая требует меньше памяти за счёт хранения элементов в виде битов, однако она не поддерживает всех возможностей работы с итераторами.

list – Двусвязный список, элементы которого хранятся в произвольных кусках памяти, в отличие от контейнера vector, где элементы хранятся в непрерывной области памяти. Поиск перебором медленнее, чем у вектора из за большего времени доступа к элементу. Доступ по индексу за O(n). В любом месте контейнера вставка и удаление производятся очень быстро - за O(1).

deque – Очередь. Контейнер похож на vector, но с возможностью быстрой вставки и удаления элементов на обоих концах за O(1). Реализован в виде двусвязанного списка линейных массивов.

set – Упорядоченное множество уникальных элементов. При вставке/удалении элементов множества итераторы, указывающие на элементы этого множества, не становятся недействительными. Обеспечивает стандартные операции над множествами типа объединения, пересечения, вычитания. Тип элементов множества должен реализовывать оператор сравнения operator< или требуется предоставить функцию-компаратор. Реализован на основе самобалансирующего дерева двоичного поиска.

multiset – То же что и set, но позволяет хранить повторяющиеся элементы.

map – Упорядоченный ассоциативный массив пар элементов, состоящих из ключей и соответствующих им значений. Ключи должны быть уникальны. Порядок следования элементов определяется ключами. При этом тип ключа должен реализовывать оператор сравнения operator<, либо требуется предоставить функцию-компаратор.

multimap – То же что и map, но позволяет хранить несколько одинаковых ключей.

stack – Стек — контейнер, в котором добавление и удаление элементов осуществляется с одного конца.

queue – Очередь — контейнер, с одного конца которого можно добавлять элементы, а с другого — вынимать.

priority_queue – Очередь с приоритетом, организованная так, что самый большой элемент всегда стоит на первом месте.

bitset – Служит для хранения битовых масок. Похож на vector<bool> фиксированного размера. Размер фиксируется тогда, когда объявляется объект bitset. Итераторов в bitset нет. Оптимизирован по размеру памяти.

basic_string – Контейнер, предназначенный для хранения и обработки строк. Хранит в памяти элементы подряд единым блоком, что позволяет организовать быстрый доступ ко всей последовательности. Элементы должны быть POD'ами. Определена конкатенация с помощью +.

valarray – Шаблон служит для хранения числовых массивов и оптимизирован для достижения повышенной вычислительной производительности. В некоторой степени похож на vector, но в нём отсутствует большинство стандартных для контейнеров операций. Определены операции над двумя valarray и над valarray и скаляром (поэлементные). Эти операции возможно эффективно реализовать как на векторных процессорах, так и на скалярных процессорах с блоками SIMD.

#include <iostream>#include <deque>using namespace std;

deque<char > chardeque;

Другие примеры.

#include <vector>

using namespace std;

void main()

{

vector<int> arr;

for(int i=0;i<1000;i++) arr.push_back(i);

for(int i=0;i<1000;i++) printf("%d,",arr[i]);

_getch();

}

#include <list>

using namespace std;

void main()

{

list<int> lst;

for(int i=0;i<1000;i++) lst.push_back(i);

for(list<int>::iterator i=lst.begin();i!=lst.end();i++) printf("%d,",*i);

_getch();

}

Дата добавления: 2014-01-05