Последовательности типа list


Контейнеры типа list представляют собой двусвязные списки, то есть упорядоченные последовательности, допускающие проходы как вперед, так и назад. Операции вставки и удаления одинаково эффективны в любое место списка. Однако операции поиска и выбора элементов линейны относительно размера контейнера. Выбор по индексу вовсе невозможен. Важным свойством списка является то, что операции вставки не портят итераторы, связанные с ним, а удаление делает недействительным только тот итератор, который указывал на удаленный элемент.
В шаблоне класса list определены методы merge, reverse, unique, remove и remove_if, которые оптимизированы для списков. Не путайте их с одноименными шаблонами функций, которые определены в алгоритмах. В примере, который приведен ниже, обратите внимание на операции слияния как списков, так и контейнеров различной природы. При исследовании списков не забудьте вставить директиву #include <list>, а также приведенный выше набор объектов класса Man:
void main 0
{
list<Man> men;
men.push_front(zorah);
men.push_back(mela);
men.push_back(joy);
pr(men,"Man List");
//======== Поиск объекта
list<Man>::iterator p = find (men.begin(),men.end(),mela);
//======== Вставка перед элементом
p = men.insert (p,joe);
// одного объекта men.insert(p,2,joe);
// двух объектов pr(men,"After inserting 3 joes");
//======== Удаление всех вхождений joe
men.remove(j oe);
men.sort(less<Man>() ) ;
pr(men,"After removing all joes and sort");
//======== Создаем второй список
list<Man> li(3,simon);
//======== Сливаем его с первым
. men.merge (li, less<Man>'() );
pr(men,"After merging with simons list");
//==== После слияния второй список полностью исчез
cout « "\n\tAfter merging simons li.size: "
« li.size() « endl;
men.remove(s imon);
//======== Создаем очередь
deque<Man> d(men.size());
//======== Копируем в нее список
copy(men.begin(), men.end(), d.begin());
pr(d,"Deque copied from list");
//======== Создаем вектор
vector<Man> v (men. size () + d.sizeO);
//==== Соединяем список и очередь и помещаем в вектор merge(men.begin(),men.end(),d.begin(),d.end(), v.begin() ) ;
pr(v,"Vector after merging list and deque");
pr(d,"Deque after merging with list");
cout«"\n\n";
}
После слияния (merge) двух списков (men и li) размер второго списка стал нулевым, так как он полностью влился в первый. При слиянии методом list: emerge элементы не копируются, а вливаются в список-мишень операции. При слиянии с помощью алгоритма merge контейнеры операнды остаются невредимыми, так как они копируются в контейнер-мишень. Если операнды операции слияния упорядочены, то при слиянии методом list::merge упорядоченность не нарушается, чего не наблюдается при слиянии шаблоном функции merge. Приведем для ясности результат работы рассматриваемой программы:
Man List # Sequence:
1. Zoran Todorovitch, Age: 27
2. Melissa Robinson, Age: 9
3. Joy Amore, Age: 18
After inserting 3 joes # Sequence:
1. Zoran Todorovitch, Age: 27
2. Joe Doe, Age: 30
3. Joe Doe, Age: 30
4. Joe Doe, Age: 30
5. Melissa Robinson, Age: 9 6. Joy Amore, Age: 18
After removing all joes and sort # Sequence:
1. Melissa Robinson, Age: 9
2. Joy Amore, Age: 18
3. Zoran Todorovitch, Age: 27
After merging with simons list # Sequence: 1. Melissa Robinson, Age: 9
2. Simon Paul, Age: 15
3. Simon Paul, Age: 15
4. Simon Paul, Age: 15
5. Joy Amore, Age: 18
6. Zoran Todorovitch, Age: 27
After merging Simons li.size: 0 Removing simons
Deque copied from list # Sequence:
1. Melissa Robinson, Age: 9
2. Joy Amore, Age: 18
3. Zoran Todorovitch, Age: 27
Vector after merging list and deque f Sequence:
1. Melissa Robinson, Age: 9
2. Joy Amore, Age: 18
3. Melissa Robinson, Age: 9
4. Joy Amore, Age: 18
5. Zoran Todorovitch, Age: 27
6. Zoran Todorovitch, Age: 27
Deque after merging with list # Sequence:
1. Melissa Robinson, Age: 9
2. Joy Amore, Age: 18
3. Zoran Todorovitch, Age: 27
Генерирование последовательности
С помощью алгоритма generate удобно создавать последовательности, имеющие строго определенную структуру. Например, если объявлен список целых из шести элементов, то его можно заполнить значениями, сгенерированными с помощью функции generate:
//========= Создаем список целых
list<uint> 1st (6);
//========= Генерируем степенную последовательность
generate (1st.begin (), Ist.end(), pows);
pr(1st,"List of generated powers");
Здесь pows — это внешняя функция, которая при каждом обращении возвращает возрастающую степень двойки. Эффект достигается за счет того, что static-переменная г инициализируется единицей во время компиляции, а затем помнит свое предыдущее значение:
uint pows()
{
static uint r = 1;
return r <= 1;
}
Если надо добиться обратного эффекта, то есть убрать закономерность в последовательности чисел, то можно воспользоваться шаблоном функции random_shuffle, которая переставляет элементы последовательности в одно из п! состояний. Например:
vector <int> v;
for (int i = 0; i <= 6; i++ ) v.push_back(i+1);
random_shuffle(v.begin() , v.end()) ;
pr(v,"Vector of shuffled numbers");
  
Ассоциативные контейнеры
К ассоциативным контейнерам принадлежат: set, multiset, hash set, hash multiset, map, multimap, hash_map, hash_multimap. Они поддерживают эффективный поиск значений (values), связанных с ключом (key). Они позволяют вставить и удалить элемент, но в отличие от последовательностей не позволяют вставить элемент в заранее определенную и указанную позицию. Различают сортированные ассоциативные контейнеры (set, multiset, map, multimap) и хешированные (hashed) ассоциативные контейнеры (hash_set, hash_multiset, hash_map, hash_ / multimap).
Сортированные контейнеры соблюдают отношение порядка (ordering relation) для своих ключей, причем два ключа считаются эквивалентными, если ни один из них не меньше другого. Например, если отношение порядка не учитывает регистр, то ключ "strict rules" эквивалентен ключу "Strict Rules". Сортированные контейнеры хороши тем, что они гарантируют логарифмическую эффективность (complexity) большинства своих операций. Это гораздо более сильная гарантия, чем та, которую предоставляют хешированные ассоциативные контейнеры. Последние гарантируют постоянную эффективность только в среднем, а в худшем случае — линейную.
Хешированные ассоциативные контейнеры основаны на той или иной реализации хэш-таблиц (см. монографию Кнут Д. Искусство программирования, т. 3, Сортировка и поиск, 1999). Элементы в таком контейнере не упорядочены, хотя их можно добывать последовательно. Если вы вставите или удалите элемент, то последовательность оставшихся элементов может измениться, то есть она не гарантируется. Преимуществом рассматриваемого типа контейнеров является то, что в среднем они значительно быстрее сортированных ассоциативных контейнеров. Удачно подобранная функция хеширования позволяет выполнять вставки, удаления и поиск за постоянное, не зависящее от п, время. Кроме того, она обеспечивает равномерное распределение хешированных значений и минимизирует количество коллизий.
Примечание
Поясним кратко суть хеширования. Она состоит в том, что каждому ключу (key) ставится в соответствие значение (value). Например, ключом могло бы быть имя абонента — строка символов, а значением — номер его телефона. Поиск значения по ключу осуществляется с помощью хеш-таблицы (hash table), которая ассоциирует ключевой объект с объектом типа значение. Эффективность работы зависит от алгоритма хеширования, который преобразует ключ в число из какого-то диапазона. Это число еще не value, а скорее индекс для выбора значения (value). При этом возможна ситуация коллизии (collision), когда два разных ключа будут преобразованы в одно и то же число. В таких случаях производится обработка коллизии по специальному алгоритму. Обычно используются списки для хранения ключей, случайно попавших в коллизию, или, как говорят, в одно ведро (bucket). Списки — это потеря эффективности поиска, но хорошие алгоритмы хеширования гарантируют очень низкую вероятность коллизий.
Если ключи не уникальны, то можно выбрать не hаsh_mар-контейнер, а контейнер типа hash_multimap. Если нужно просто хранить множество каких-то объектов, например строк текста, не ассоциируя их с другими объектами, то стоит подумать о контейнере типа hash_set. Ну а в случае, если среди этих объектов могут попасться одинаковые, то выбором может стать контейнер типа hash_multiset.
Хешируемые типы контейнеров все-таки упорядочивают контролируемую ими последовательность, вызывая встроенный в него объект hash Traits класса value_compare. Вы имеете доступ к этому объекту с помощью метода key_comp. В общем случае два элемента признаются либо одинаковыми, либо какой-либо из них признается меньшим. Но реальная упорядоченность элементов зависит от функции хеширования, функции, задающей отношение порядка и текущего размера хэш-таблицы, поэтому в общем случае невозможно предсказать порядок следования элементов. Важной характеристикой ассоциативных контейнеров является то, что вставка элементов не портит итераторы, а удаление делает недействительными только те итераторы, которые указывают на удаляемый элемент.
  
Контейнер типа set
Множество (set) является ассоциативным контейнером, который хранит объекты типа key. В этом случае говорят о типе Simple Associative Container, имея в виду, что как value, так и key имеют один тип key. Говорят также о Unique Associative Container, имея в виду, что в контейнере типа set не может быть одинаковых элементов. Рассмотрим работу контейнера на примерах. Не забудьте вставить директиву #include <set>:
void main ()
{
//======== Создаем множество целых
set<int> s;
s.insert(1);
s.insert(2);
s.insert (3);
//======= Повторно вставляем единицу (она не пройдет)
s.insert (1);
//==== Два раза вставляем "в конец последовательности"
s. insert (--s.end() , 4); s.insert(—s.endO, -1);
pr(s,"Set of ints");
//======== Второе множество
set<int> ss;
for (int i=l; i<5; i++) ss.insert (i*10);
//======== Вставляем диапазон
s. insert (++ss. begin () , —s s.end() );
pr(s, "After insertion"); cout«"\n\n";
}
Эта программа выведет в окно Output следующие строки:
Set of ints # Sequence:
1. -1
2. 1
3. 2
4. 3
5. 4
After insertion # Sequence:
1. -1
2. 1
3. 2
4. 3
5. 4
6. 20
7. 30
Как видно из распечатки, несмотря на то что и 4 и -1 были вставлены в конец последовательности, контейнер сам распорядился порядком следования и разместил элементы в порядке возрастания ключей. Вставка диапазона из другого множества также происходит по этим законам. Следующий содержательный пример я обнаружил на сайте компании Silicon Graphics. Он приведен в слегка измененном виде:
//========= Предикат
inline bool NoCase(char a, char b)
{
// Определяет отношение less для обычных символов
// без учета регистра (Подключите stdlib.h)
return tolower(a) < tolower (b) ; !;
}
//========= Функциональный объект
struct LessStr
{
//==== Определяет отношение less для C-style строк
bool operator()(const char* a, const char* b) const
{
return strcmp(a, b) < 0;
}
};
Два отношения порядка для типов данных, хорошо вам знакомых (char и char*), для разнообразия заданы: одно в виде предиката, другое в виде функционального объекта. Ниже они будут использованы в конструкторе шаблона классов set. Тем самым определен порядок сортировки элементов контейнера:
void main ()
{
//====== Обычные неупорядоченные массивы символов
const int N = 6; const char* a[N] =
{
"Set", "Pet", "Net", "Get", "Bet", "Let"
};
const char* b[N] =
{
"Met", "Wet", "Jet",
"Set", "Pet", "Net",
} ;
//======== Создаем два множества обычных строк,
//======== определяя отношение порядка
set<const char*, LessStr> A(a, a + N);
set<const char*, LessStr> B(b, b + N);
//======== Создаем пустое множество
set<const char*, LessStr> C;
//======== Выходной итератор привязываем к cout
cout « "Set A: {";
copy (A.begin (), A.end.(),
ostream_iterator<const char*>(cout, "; "));
cout « ' } ' ;
cout « "\n\nSet B:
copy (B.begin (), B.end(), .. ostream_iterator<const char*>(cout, ", "));
//======= Создаем и выводим объединение двух множеств
cout « "\n\nUnion A U В: ";
set_union (A.begin () , A.end(), B.begin(), B.end(),
ostream_iterator<const char*>(cout, ", "),
LessStr () )';
//======= Создаем и выводим пересечение двух множеств
cout « "\n\nlntersection А & В: ";
set_intersection (A.begin () , A.end(), B.beginO, B.end(), ostream_iterator<const char*>(cout, " "), LessStrO);
//===== Создаем разность двух множеств
//===== Используем inserter для заполнения множества С
set_dif ference (A.begin () , A.end(), B.beginO, B.end(),
inserter (С, C.begin()),
LessStr() ) ;
cout « "\n\nDifference A/B: ";
//===== Копируем множество прямо в выходной поток сору
С. begin () , С.
end ();
ostream_iterator<const char*>(cout, " "));
С. clear () ;
//===== Повторяем в обратную сторону
set_dif ference (В. begin () , B.endO, A.begin(), A.end(),
inserter (С, C.begin()), LessStrO);
cout « "\n\nDifference B/A: ";
copy (C.begin (), C.end(),
ostream_iterator<const char*>(cout, " "));
cout « "\n\n";
//====== Выводим разделитель
vector<char> line(50, ' = ');
ostream_iterator<char> os(cout, "") ;
copy (line .begin О , line.endO, os) ;
//====== Обычные массивы символов
char D[] = { 'a', 'b', 'с', 'd', ' e', 'f' };
char E[] = { 'A', 'B', 'C1, 'G', 'H1, 'H' };
cout « "\n\nSet D: ";
for (int i=0; i<N; i++) cout « D[i] « ", ";
cout « "\n\nSet E: ";
for (int i=0; i<N; i + -i-)
cout « E[i]«",";
cout « "\n\nSymmetric Difference D/E (nocase): ";
//====== Используем алгоритм set_symmetric_difference
//====== для обычных массивов символов
set_symmetric_difference(D, D + N, E, E + N,
ostream_iterator<char>(cout, " "), NoCase);
cout«"\n\n"; }
Новые возможности STL, которые использованы в этом фрагменте, — это использование адаптера insert_iterator и копирование содержимого контейнера прямо в выходной поток (см. ostream_iterator). Вывод в поток осуществляется с помощью особого типа итератора ostream_iterator, который осуществляет форматируемый вывод объектов типа Т в указанный выходной поток (ostream). Шаблон класса ostream_iterator настраивается на тип данных, в нашем случае const char*, а затем char, и берет в качестве параметров объект потокового вывода (cout) и разделитель, который мы специально изменяем по ходу дела для того, чтобы вы его обнаружили.
Insert_iterator — это адаптер (настройщик) итератора, который настраивает операнд, являющийся мишенью операции. Присвоение с помощью (сквозь призму) такого итератора вставляет объект в контейнер, раздвигая его, то есть, используя метод insert. Он следит за текущей позицией в контейнере (insertion point) и производит вставку перед ней. Здесь вы, однако, должны учесть различную семантику операции вставки в различные типы контейнеров. Если это последовательность (sequence), то все происходит именно так, как только что было сказано, но если это сортируемый ассоциативный контейнер, то вы не можете управлять позицией вставки. Для таких контейнеров указание места вставки служит лишь отправной точкой для поиска реальной позиции в контейнере. В результате вставки при выводе вы увидите упорядоченную по возрастанию ключа последовательность. Порядок вставки в сортируемые ассоциативные контейнеры не влияет на порядок элементов, который вы увидите на экране. Однако он может повлиять на эффективность процесса вставки.
Пары
Парой называется шаблон класса, который хранит пару объектов различного типа. Пара похожа на контейнер в том, что она владеет своими элементами, но она не является контейнером, так как не поддерживает стандартных методов и итераторов, присущих контейнерам. У пары есть два элемента данных (first, second), которые дают возможность манипулировать вложенными объектами. Следующий фрагмент иллюстрирует логику использования пары:
pair<bool, double> result = FindRoot();

if (result.first)
print(result.second);
else
report_error() ;
Ассоциативные контейнеры используют тип пар _Pairib. Он определяет пару:
pair<iterator, bool>
Первый элемент каждой такой пары является итератором соответствующего типа, а второй — результатом какого-либо действия. Например, метод insert возвращает пару типа _Pairib, анализируя которую вы можете узнать результат вставки (успех или неудача). Рассмотрим пример:
void main ()
{
//========== Массив объектов класса Man
Man ar[] =
{
joy,duke, win, joy,charlie
);
uint size = sizeof(ar)/sizeof(Man);
//========== Создаем множество объектов класса Man
set<Man> s (ar, ar+size); pr(s, "Set of Man");
//========== Ищем объект и удаляем его
set<Man>::iterator p = s.find(joy);
if (p != s.end() )
{
s.erase(p);
cout « "\n\n"« joy «" found and erased";
}
pr(s,"After erasure");
//========== Объявляем пару
set<Man>::_Pairib pib;
//========== Пробуем вставить объект
pib = s.insert(joy);
//========== Анализируем результат вставки
cout « "\n\nlnserting: " « *pib.first « "\nResult is: " « pib.second;
//========== Пробуем вставить повторно
pib = s.insert(joy);
cout « "\n\nlnserting: " « *pib.first « "\nResult is: " « pib.second;
//========== Сравниваем ключи
cout « "\n\ns.key_comp() (zoran,count) returned "
« s.key_comp()(zoran,ar[0]);
cout « "\n\ns.key_comp()(count,zoran) returned "
« s.key_comp()(ar[0],zoran);
cout <<"\n\n";
}
Приведем результат работы этой программы:
Set of Man # Sequence:
1. Joy Amore, Age: 18
2. Winton Kelly, Age: 50
3. Charlie Parker, Age: 60
4. Duke Ellington, Age: 90
Joy Amore, Age: 18 found and erased After erasure # Sequence:
1. Winton Kelly, Age: 50
2. Charlie Parker, Age: 60
3. Duke Ellington, Age: 90
Inserting: Joy Amore, Age: 18
Result is: 1
Inserting: Joy Amore, Age: 18
Result is: 0
s.key_comp()(zoran,count) returned 0 s.key_comp()(count,zoran) returned 1
  
Контейнеры типа map
Отображение (map) является сортируемым ассоциативным контейнером, который ассоциирует объекты типа key с объектами типа value. Map — это Pair Associative Container, так как он хранит пары типа pair<const Key, Data>. Говорят также о Unique Associative Container, имея в виду, что в контейнере типа тар не может быть одинаковых элементов. Отображения являются одними из самых мощных и удобных типов контейнеров. Рассмотрим их работу на примерах. Не забудьте вставить директиву #include <map>:
void main ()
{
//========= Создаем отображение строки в целое
map<string,int> m;
map<string,int>::_Pairib pib;
map<string,int>::iterator it;
//========= Создаем новый тип для удобства
typedef pair<string, int> MyPair; MyPair p("Monday", 1); m.insert(p);
//========= Изменяем компоненты пары
p.first = "Tusday";
p.second = 2;
pib = m.insert(p);
cout « "\n\nlnserting: "
« (*pib.first).first « ","
« (*pib.first).second
« "\nResult is: " « pib.second;
pib = m.insert(p);
cout « "\n\nlnserting: "
« (*pib.first).first « ","
« (*pib.first).second
« "\nResult is: " « pib.second;
//========= Работаем с индексом
m["Wednesday"] = 3;
m["Thirsday"] = 4;
m["Friday"] = 5;
//========= Работаем с динамической памятью
MyPair *pp = new MyPair("Saturday", 6);
m.iftsert(*pp);
delete pp;
cout«"\n\n\t <string,int> pairs :\n";
for (it = m.begin ();
if != m.end(); it++)
cout « "\n(" « it->first«","<<it->second«") ";
cout«"\n\n";
}
Результат работы этого фрагмента выглядит так:
Inserting: Tusday, 2 Result is: 1
Inserting: Tusday, 2 Result is: 0
<string,int> pairs:
(Friday, 5) (Monday, 1) (Saturday, 6) (Thirsday, 4) (Tusday, 2) (Wednesday, 3)
Как видите, пары отсортированы в лексикографическом порядке. Если потребуется восстановить естественный порядок, то это можно сделать, поменяв порядок следования аргументов при объявлении шаблона на
map<int, string> m;
Такую замену придется сделать и для всех других, связанных с шаблоном типов данных. Отметьте также, что при работе с отображениями недостаточно разадресо-вать итератор (*it), чтобы получить объект им указываемый. Теперь вы должны писать (*it) .first или it->first, чтобы получить какой-то объект. Характерно, что эти выражения могут стоять как в левой, так и в правой части операции присвоения, то есть вы можете записать:
it->first = "Sunday";
int n = it->second;
  
Контейнеры типа hash_multimap
Хешированный ассоциативный контейнер типа hash_multimap основан на встроенной реализации хэш-таблиц. Вы помните, что преимуществом такого типа контейнеров является быстродействие, которое в среднем значительно выше, чем у сортированных ассоциативных контейнеров. Упорядоченность элементов в таком контейнере не гарантируется, но вы можете по определенной системе добывать их С ПОМОЩЬЮ метода hash_multimap: :equal_range.
Предположим, что ваша база данных содержит сведения о сотрудниках — объектах класса Man, многих отделов какой-то организации. В примере мы возьмем только два отдела (100 и 115). Так как мы хотим быстро получать информацию о сотрудниках, то выбираем в качестве структуры для хранения данных в памяти хешированный ассоциативный контейнер. Очевидно, что если в качестве ключевого поля для него выбрать номер отдела, то поле не будет уникальным. Этот факт окончательно определяет выбор типа контейнера— hash_multimap.
Вы также, вероятно, помните, что все контейнеры типа тар — это Pair Associative контейнеры, так как они хранят пары типа pair<const Key, Data>. В нашем случае этой парой является pair<int, Man>, где первый элемент задает номер отдела, а второй сотрудника этого отдела. Для удобства пользования контейнером введем новые типы данных:
//======= ManPair - это тип используемых пар
typedef pair <int, Man> ManPair;
//======= ManMap - это тип контейнера
typedef hash_multimap <int, Man> ManMap;
//======= ManMapIt — это тип итератора
typedef ManMap::const_iterator ManMapIt;
Отметьте, что мы выбрали самый простой способ определения контейнера. Более точным описанием, которое намекает вам на возможность усложнения структуры, будет:
typedef hash_multimap <int, Man,
hash_compare <int, less<int> > > ManMap;
Отсюда ясно, что можно изменить предикат, по которому производится сравнение элементов контейнера. Для выбора всех сотрудников определенного отдела мы собираемся использовать метод:
equal_range(int /*Номер отдела*/);
который возвращает пару итераторов. Первый итератор пары указывает на начало диапазона внутри контейнера из сотрудников указанного отдела, а второй — на конец этого диапазона. Теперь пора в бой. Надо писать код, реализующий работу контейнера.
void main( )
{
typedef pair <int, Man> ManPair;
typedef hash_multimap <int, Man> ManMap;
typedef ManMap::const_iterator ManMapIt;
//====== Создаем пустой контейнер типа hash_multimap ManMap h;
//====== Наполняем его сотрудниками
h.insert (ManPair (100, тагу));
h.insert (ManPair (115, joe));
h.insert (ManPair (100, win));
h.insert (ManPair (100, charlie));
h.insert (ManPair (115, liza));
h.insert TManPair (115, joy));
//====== При выводе пользуемся парой
cout « "Contents of Hash Multimap\n\n";
for (ManMapIt p = h.begin();
p != h.end(); p++)
cout « "\n" « p->first
«". " « p->second;
//====== Выбираем диапазон (сотрудники 100-го отдела)
pair<ManMap!t, ManMapIt> pp = h.equal_range(100);
//====== Вновь пользуемся парой
cout « "\n\nEmployees of 100 department\n\n";
for (p = pp.first; p != pp.second; ++p)
cout « "\n" « p->first
«"." « p->second; cout « "\n\n";
}
He лишнее напомнить, что приведенный код надо дополнить объявлениями объектов класса Man и вставкой директивы #include <hash_map>. Директивы должны копиться. Я надеюсь, что с этой задачей вы справитесь самостоятельно. Объявления людей мы приводили где-то в начале урока. Программа должна произвести такой вывод:
Contents of Hash Multimap
115. Liza Dale, Age: 17
115. Joy Amore, Age: 18
115. Joe Doe, Age: 30
100. Winton Kelly, Age: 50
100. Charlie Parker, Age: 60
100. Mary Poppins, Age: 36
Employees of 100 department
100. Winton Kelly, Age: 50
100. Charlie Parker, Age: 60
100. Mary Poppins, Age: 36

 

 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г. Яндекс.Метрика