1. Обзор методов и алгоритмов решения поставленной задачи
При решении поставленной задачи необходимо определить, как хранить информацию и как ее обрабатывать.
Классы С++ предоставляют прекрасный механизм для создания библиотеки структур данных. В стандарт С++ входит собственная встроенная библиотека классов-контейнеров. Она называется Стандартной библиотекой шаблонов. Она может использоваться для хранения и обработки данных.
Контейнер – способ организации хранения данных. Они подключаются к программе с помощью шаблонных классов, а значит, можно легко изменять тип хранимых в них данных. Рассмотрим достоинства и недостатки некоторых контейнеров.
Векторы – последовательный контейнер. Занимается автоматическим размещением себя в памяти, расширением и сужением своего размера по мере вставки или удаления данных. Случайный доступ (по индексу), вставка и изъятие данных из хвоста выполняется очень быстро. Медленная вставка и изъятие данных из середины.
Контейнер под названием список представляет собой дважды связный список, в котором каждый элемент хранит указатель на соседа слева и справа. Контейнер содержит адрес первого и последнего элементов, поэтому доступ к обоим концам списка осуществляется очень быстро. Медленный случайный доступ.
Очередь с двухсторонним доступом представляет собой нечто похожее и на вектор, и на связный список. Как и вектор, этот тип контейнера поддерживает производный доступ. Как и к списку, доступ может быть получен к началу и к концу очереди. Для векторов и двухсторонних очередей память резервируется по-разному. Вектор всегда занимает смежные участки памяти. Поэтому при его разрастании резервируется новый участок памяти, где контейнер может разместиться целиком. С другой стороны, очередь с двухсторонним доступом может размещаться в нескольких сегментах памяти, не обязательно смежных. В этом есть и плюсы, и минусы. Очередь практически всегда будет гарантированно размещена в памяти, но доступ к сегментированным объектам всегда осуществляется с более медленной скоростью.
Программе необходимо сохранять данные на диск и считывать их. Старые функции С, такие как fprint(), fwrite() не так хорошо вписываются в концепцию объектно-ориентированной среды программирования. Новый подход предлагаемый в С++, гораздо прозрачнее и проще в использовании.
При форматированном вводе/выводе числа хранятся на диске в виде серии символов. Есть несколько потенциальных проблем с форматированным выводом в дисковые файлы. Во-первых, надо разделять числа нечисловыми константами. Поскольку они хранятся в виде последовательности символов, а не в виде полей фиксированной длины, это единственный шанс узнать при извлечении, где кончается одно и начинается другое число. Во-вторых, между строками должны быть разделители – по тем же причинам. Это подразумевает, что внутри строки не может быть пробелов.
Форматированный файловый ввод/вывод чисел целесообразно использовать только при их небольшой величине и малом количестве. В противном случае, гораздо эффективнее использовать двоичный ввод/вывод, при котором числа хранятся таким же образом, как в оперативной памяти компьютера, а не виде символьных строк.