2. Какие простые вопросы мы обычно задаем, думая о данных?
3. Перечислите разные способы хранения данных?
4. Какие основные операции можно выполнить с коллекцией данных?
5. Каких принципов следует придерживаться при хранении данных?
6. Что такое последовательность в библиотеке STL?
7. Что такое итератор в библиотеке STL? Какие операции поддерживают итераторы?
8. Как установить итератор на следующий элемент?
9. Как установить итератор на предыдущий элемент?
10. Что произойдет, если вы попытаетесь установить итератор на ячейку, следующую за концом последовательности?
11. Какие виды итераторов могут перемещаться на предыдущий элемент?
12. Почему полезно отделять данные от алгоритмов?
13. Что такое STL?
14. Что такое связанный список? Чем он в принципе отличается от вектора?
15. Что такое узел (в связанном списке)?
16. Что делает функция
insert()
? Что делает функция
erase()
?
17. Как определить, что последовательность пуста?
18. Какие операции предусмотрены в итераторе для класса
list
?
19. Как обеспечить перемещение по контейнеру, используя библиотеку STL?
20. В каких ситуациях лучше использовать класс
string
, а не
vector
?
21. В каких ситуациях лучше использовать класс
list
, а не
vector
?
22. Что такое контейнер?
23. Что должны делать функции
begin()
и
end()
в контейнере?
24. Какие контейнеры предусмотрены в библиотеке STL?
25. Перечислите категории итераторов? Какие виды итераторов реализованы в библиотеке STL?
26. Какие операции предусмотрены в итераторе с произвольным доступом, но неподдерживаются двунаправленным итератором?
Термины
Упражнения
1. Если вы еще не выполнили задания из врезок ПОПРОБУЙТЕ, то сделайте это сейчас.
2. Попробуйте запрограммировать пример с Джеком и Джилл из раздела 20.1.2. Для тестирования используйте несколько небольших файлов.
3. Проанализируйте пример с палиндромом (см. раздел 20.6); еще раз выполните задание из п. 2, используя разные приемы.
4. Найдите и исправьте ошибки, сделанные в примере с Джеком и Джилл в разделе 20.3.1, используя приемы работы с библиотекой STL.
5. Определите операторы ввода и вывода (
>>
и
<<
) для класса
vector
.
6. Напишите операцию “найти и заменить” для класса
Document
, используя информацию из раздела 20.6.2.
7. Определите лексикографически последнюю строку в неупорядоченном классе
vector<string>
.
8. Напишите функцию, подсчитывающую количество символов в объекте класса
Document
.
9. Напишите программу, подсчитывающую количество слов в объекте класса
Document
. Предусмотрите две версии: одну, в которой слово — это последовательность символов, разделенных пробелами, и вторую, в которой слово — это неразрывная последовательность символов из алфавита. Например, при первом определении выражения
alpha.numeric
и
as12b
— это слова, а при втором — каждое из них рассматривается как два слова.
10. Напишите программу, подсчитывающую слова, в которой пользователь мог бы сам задавать набор символов-разделителей.
11. Создайте объект класса
vector<double>
и скопируйте в него элементы списка типа
list<int>
, передавая его как параметр (по ссылке). Проверьте, что копия полна и верна. Затем выведите на экран элементы в порядке возрастания их значений.
12. Завершите определение класса
list
из разделов 20.4.1 и 20.4.2 и продемонстрируйте работу функции
high()
. Выделите память для объекта класса
Link
, представляющего узел, следующий за концом списка.
13. На самом деле в классе
list
нам не нужен реальный объект класса
Link
, расположенный за последним элементом. Модифицируйте свое решение из предыдущего упражнения так, чтобы в качестве указателя на несуществующий объект класса
Link (list<Elem>::end())
использовалось значение
0
; иначе говоря, размер пустого списка может быть равен размеру отдельного указателя.
14. Определите односвязный список
slist
, ориентируясь на стиль класса
std::list
. Какие операции из класса list стоило бы исключить из класса
slist
, поскольку он не содержит указателя на предыдущий элемент?
15. Определите класс
pvector
, похожий на вектор указателей, за исключением того, что он содержит указатели объекта и каждый объект уничтожается его деструктором.
16. Определите класс
ovector
, похожий на класс
pvector
, за исключением того, что операции
[ ]
и
*
возвращают не указатели, а ссылки на объект, на который ссылается соответствующий элемент.
17. Определите класс
ownership_vector
, хранящий указатели на объект как и класс
pvector
, но предусматривающий механизм, позволяющий пользователю решить, какие объекты принадлежат вектору (т.е. какие объекты удалены деструктором). Подсказка: это простое упражнение, если вы вспомните главу 13.
18. Определите итератор с проверкой выхода за пределы допустимого диапазона для класса
vector
(итератор с произвольным доступом).
19. Определите итератор с проверкой выхода за пределы допустимого диапазона для класса
list
(двунаправленный итератор).
20. Выполните эксперимент, посвященный сравнению временных затрат при работе с классами
vector
и
list
. Способ измерения длительности работы программы изложен в разделе 26.6.1. Сгенерируйте
N случайных целых чисел в диапазоне [0:
N]. Вставьте каждое сгенерированное число в вектор
vector<int>
(после каждой вставки увеличивающийся на один элемент). Храните объект класса
vector
в упорядоченном виде; иначе говоря, значение должно быть вставлено так, чтобы все предыдущие значения были меньше или равны ему, а все последующие значения должны быть больше него. Выполните тот же эксперимент, используя класс
list<int>
для хранения целых чисел. При каких значениях
N класс
list
обеспечивает более высокое быстродействие, чем класс
vector
? Попробуйте объяснить результаты эксперимента. Впервые этот эксперимент был предложен Джоном Бентли (John Bentley).
