ЛАБОРАТОРНАЯ РАБОТА № 10
ВЕКТОРЫ. МОДУЛИ
1. Векторы
Контейнерные классы – это классы, предназначенные для хранения данных, организованных определенным образом. Для каждого типа контейнера определены методы для работы с его элементами, не зависящие от конкретного типа данных, которые хранятся в контейнере, поэтому один и тот же вид контейнера можно использовать для хранения данных различных типов.
К контейнерам, реализующим основные структуры данных, используемые при написании программ, можно отнести векторы, двусторонние очереди, списки и их разновидности, словари и множества. Контейнеры можно разделить на два типа: последовательные и ассоциативные.
Последовательные контейнеры обеспечивают хранение конечного количества однотипных величин в виде непрерывной последовательности. К ним относятся векторы (vector), двусторонние очереди (deque) и списки (list), а также так называемые адаптеры, то есть варианты, контейнеров – стеки (stack), очереди (queue) и очереди с приоритетами (priority_queue).
Ассоциативные контейнеры обеспечивают быстрый доступ к данным по ключу. Эти контейнеры построены на основе сбалансированных деревьев. Существует пять типов ассоциативных контейнеров: словари (map), словари с дубликатами (multimap), множества (set), множества с дубликатами (multiset) и битовые множества (bitset).
Контейнерные классы обеспечивают стандартизованный интерфейс при их использовании. Смысл одноименных операций для различных контейнеров одинаков, основные операции применимы ко всем типам контейнеров.
Практически в любом контейнерном классе определены поля следующих типов (табл. 1).
Таблица 1. Поля контейнеров
Поле |
Пояснение |
value_type |
Тип элемента контейнера |
size_type |
Тип индексов, счетчиков элементов и т.д. |
iterator |
Итератор |
const_iterator |
Константный итератор |
reverse_iterator |
Обратный итератор |
const_reverse_iterator |
Константный обратный итератор |
reference |
Ссылка на элемент |
const_reference |
Константная ссылка на элемент |
key_type |
Тип ключа (для ассоциативных контейнеров) |
key_compare |
Тип критерия сравнения |
Итератор является аналогом указателя на элемент. Он используется для просмотра контейнера в прямом или обратном направлении. Все, что требуется от итератора – уметь ссылаться на элемент контейнера и реализовывать операцию перехода к его следующему элементу.
Для итераторов определены следующие методы (табл. 2).
Таблица 2. Методы итераторов
Метод |
Пояснение |
iterator begin(), const_iterator begin() const |
Указывают на первый элемент |
iterator end(), const_iterator end() const |
Указывают на последний элемент |
reverse_iterator rbegin(), const_reverse_iterator rbegin() const |
Указывают на первый элемент в обратной последовательности |
reverse_iterator rend(), const_reverse_iterator rend() const |
Указывают на элемент, следующий за последним, в обратной последовательности |
Во всех контейнерах определены методы, позволяющие получить сведения о размере контейнеров (табл. 3).
Таблица 3. Методы для получения сведений о размере контейнеров
Метод |
Пояснение |
size() |
Число элементов |
max_size() |
Максимальный размер контейнера |
empty() |
Булевская функция, показывающая, пуст ли контейнер |
Примеры создания векторов:
//Создается вектор из 10 равных единице элементов
vector <int> v2 (10, 1);
//Создается вектор, равный вектору v1:
vector <int> v4(v1);
//Создается вектор из двух элементов,
//равных первым двум элементам v1
vector <int> v3(v1.begin(), v1.begin()+2);
//Создается вектор из 10 объектов класса Train
//Работает конструктор по умолчанию
vector <Train> t1(10);
Определены следующие методы для изменения объектов класса vector.
void push_back(const T& value);
Функция push_back добавляет элементы в конец вектора.
void pop_back();
Функция pop_back удаляет элементы из конца вектора.
iterator insert(iterator position, const T& value);
void insert(iterator position, size_type n, const T& value);
template <class InputIter> void insert(iterator position, InputIter first, InputIter last);
Функция insert служит для вставки элемента в вектор. Первая форма функции вставляет элемент value в позицию, заданную первым параметром (итератором), и возвращает итератор, ссылающийся на вставленный элемент. Вторая форма функции вставляет в вектор n одинаковых элементов. Третья форма функции позволяет вставить несколько элементов, которые могут быть заданы любым диапазоном элементов подходящего типа, например:
vector <int> v(2), v1(3,9);
int m[3] = {3, 4, 5};
v.insert(v.begin(), m, m+3); // Содержимое v: 3 4 5 0 0
v1.insert(v1.begin() + 1, v.begin(), v.begin() + 2);
//Содержимое v1: 9 3 4 9 9
Функция erase служит для удаления одного элемента вектора (первая форма функции) или диапазона, заданного с помощью итераторов (вторая форма):
vector <int> v;
for (int i = 1; i<6; i++) v.push_back(i);
//Содержимое v: 1 2 3 4 5
v.erase(v.begin()); //Содержимое v: 2 3 4 5
v.erase(v.begin(), v.begin() + 2); //Содержимое v: 4 5
Следует обратить внимание, что вторым параметром задается не последний удаляемый элемент, а элемент, следующий за ним.
Функция swap служит для обмена элементов двух векторов одного типа, но необязательно одного размера:
vector <int> v1, v2;
…
v1.swap(v2); //Эквивалентно v2.swap(v1)
Для векторов определены операции сравнения ==, !=, <, <=, > и >=. Два вектора считаются равными, если равны их размеры и все соответствующие пары элементов. Один вектор меньше другого, если первый из элементов одного вектора, не равный соответствующему элементу другого, меньше него (то есть сравнение лексикографическое).
Для эффективной работы с векторами в стандартной библиотеке определены шаблоны функций, называемые алгоритмами. Они включают в себя поиск значений, сортировку элементов, вставку, замену, удаление и другие операции.
2. Модули
Имена программных элементов, таких как переменные, функции, классы и т. д., должны быть объявлены до их использования. Например, нельзя просто написать x = 42 без первого объявления "x".
Объявление указывает компилятору, является ли элемент переменной, функцией классом или какой-либо другой вещью. Кроме того, каждое имя должно быть объявлено (прямо или косвенно) в каждом CPP-файле, в котором он используется. При компиляции программы каждый CPP-файл компилируется независимо в единицу компиляции. Компилятор не знает, какие имена объявляются в других единицах компиляции. Это означает, что если программист определяет класс или функцию или глобальную переменную, необходимо предоставить объявление этой вещи в каждом дополнительном CPP-файле, который использует его. Каждое объявление этой вещи должно быть точно идентичным во всех файлах. Небольшое несоответствие приведет к ошибкам или непреднамеренное поведение, когда компоновщик пытается объединить все блоки компиляции в одну программу.
Чтобы свести к минимуму вероятность ошибок, C++ принял соглашение об использовании файлов заголовков для хранения объявлений. Программист делает объявления в файле заголовка, а затем использует директиву #include в каждом CPP-файле или другом файле заголовка, который требует этого объявления. Директива #include вставляет копию файла заголовка непосредственно в CPP-файл перед компиляцией.
В следующем примере показан распространенный способ объявления класса и последующего использования его в другом исходном файле.
Сначала следует создать файл заголовка – my_class.h Он содержит определение класса, но следует обратить внимание, что определение является неполным; Функция-метод do_something не определена:
// my_class.h
namespace N
{
class my_class
{
public:
void do_something();
};
}
Затем следует создать файл реализации (обычно с расширением CPP или аналогичного расширения). Потом надо вызвать файл my_class.cpp и предоставить определение для объявления метода. Далее добавим директиву #include для файла "my_class.h", чтобы объявление my_class вставлено в этот в CPP-файл. Следует обратить внимание, что кавычки используются для файлов заголовков в том же каталоге, что и исходный файл, а угловые скобки используются для заголовков стандартной библиотеки.
// my_class.cpp
#include "my_class.h" // header in local directory
#include <iostream> // header in standard library
using namespace N;
using namespace std;
void my_class::do_something()
{
cout << "Doing something!" << endl;
}
Теперь можно использовать my_class в другом CPP-файле. Добавим с помощью #include файл заголовка, чтобы компилятор извлекал объявление. Все, что компилятор должен знать, заключается в том, что my_class является классом, который имеет метод do_something().
// my_program.cpp
#include "my_class.h"
using namespace N;
int main()
{
my_class mc;
mc.do_something();
return 0;
}
Как правило, файлы заголовков имеют директиву #pragma once , чтобы убедиться, что они не вставляются несколько раз в один CPP-файл.
Так как файл заголовка может быть включен несколькими файлами, он не может содержать определения, которые могут создавать несколько определений одного и того же имени. Следующие действия не допускаются или считаются очень плохой практикой.
– встроенные определения типов в пространстве имен или глобальной области;
– определения функций, отличных от встроенных;
– определения переменных, отличных от const;
– агрегатные определения;
– безымянные пространства имен;
– директивы using.
Использование директивы using не обязательно приведет к ошибке, но может вызвать проблему, так как она добавляет пространство имен в область в каждом CPP-файле, который прямо или косвенно включает этот заголовок.
3. Пример программы на C++