STL5 / lab0-introduction / lab0-Container-element-requirements
.docТребования к элементам контейнеров STL
Стандартная библиотека шаблонов предоставляет реализации следующих фундаментальных структур данных:
-
Одномерный массив элементов типа Т с возможностью изменения размера (класс vector)
-
Двухсвязный список элементов типа Т (класс list)
-
Очередь элементов типа Т с двумя концами (класс deque)
-
Очередь элементов типа Т (класс queue)
-
Стек элементов типа Т (класс stack)
-
Ассоциативный массив элементов (класс map)
-
Набор элементов (класс set)
-
Набор булевых переменных (класс bitset)
Перечисленные контейнеры отличаются предоставляемыми возможностями, интерфейсами1, внутренним способом хранения элементов, временем выполнения различных операций, однако все контейнеры STL накладывают одинаковые требования к типам данных, которые могут быть помещены в контейнере.
Элементы в контейнере – копии вставленных элементов.
Таким образом, чтобы стать элементом контейнера, объект должен быт такого типа, который бы позволил реализации контейнера скопировать его. Контейнер может копировать элементы при помощи копирующего конструктора или присваивания; в обоих случаях полученная копия должны быть эквивалентным объектом. Другими словами любая проверка значений объектов на равенство должна считать копию равной оригиналу, копирование объекта должно работать очень похоже на обычное копирование встроенных типов.
Если по каким-то причинам копирование элементов не приемлемо имеет смысл рассмотреть хранение в контейнере не самих элементов, а например указателей на них. Наиболее очевидный пример – реализация полиморфных типов, в этой ситуации вместо vector<Shape> имеет смысл использовать vector<Shape*>.
Ниже приведен ряд примеров иллюстрирующих данные ограничения.
Пример 1.
vector<int> vec;
Целые числа (как и любые другие встроенные типы) удовлетворяю требования стандартных контейнеров к своим элементам, копия числа всегда эквивалентна оригиналу.
Пример 2.
class Rect
{
public:
int x;
int y;
int width;
int height;
};
vector<Rect> vec;
В данном класс удовлетворяет требованиям контейнеров к своим элементам, для копирования объектов этого класса будут использованы конструктор копирования и оператор присваивания сгенерированные компилятором, которые реализуют правильное копирование.
Пример 3:
class NonCopiable
{
public:
…. /* открытый интерфейс класса*/
private:
…. /* данные и закрытые методы */
/* Конструктор копирования */
NonCopiable(const NonCopiable&);
/* Оператор присваивания */
const NonCopiable& operator=( const NonCopiable&);
};
vector<NonCopiable> vec;
В данном примере объекта класса NonCopiable не могут быть элементами вектора, так как они не могут быть скопированы в контейнер (конструктор копирования и оператор присваивания объявлены закрытыми и могут быть вызваны только методами данного класса)
Пример 4:
class Dialog : public Window
{
public:
…. /* открытый интерфейс класса*/
/* Конструктор копирования */
Dialog(const Dialog& dlg)
{
position_x = dlg.position_x;
position_y = dlg.position_y;
width = dlg.width;
height = dlg.height;
}
/* Оператор присваивания */
const Dialog& operator=( const Dialog& dlg)
{
position_x = dlg.position_x;
position_y = dlg.position_y;
width = dlg.width;
height = dlg.height;
}
private:
String caption;
int position_x, position_y;
int width, height;
…. /* другие данные и закрытые методы */
};
vector<Dialog> vec;
В данном примере операции копирования реализованы не правильно и класс не удовлетворяет требованиям контейнеров STL к своим элементам. Попытка использовать данный класс в качестве элемента стандартного контейнера приведет неопределенному поведению, которое выразится в сложных для поиска ошибках.
Правильная реализация копирования приведена ниже.
class Dialog : public Window
{
public:
…. /* открытый интерфейс класса*/
/* Конструктор копирования */
Dialog(const Dialog& dlg) :
Window(dlg),
caption(dlg.caption),
position_x(dlg.position_x),
position_y(dlg.position_y),
width(dlg.width),
height(dlg.height)
{
}
/* Оператор присваивания */
const Dialog& operator=( const Dialog& dlg)
{
if (this != &dlg)
{
Window::operator=(dlg);
caption = dlg.caption;
position_x = dlg.position_x;
position_y = dlg.position_y;
width = dlg.width);
height = dlg.height;
}
}
private:
String caption;
int position_x, position_y;
int width, height;
…. /* другие данные и закрытые методы */
};
Необходимо обратить внимание, что должны быть скопированы все поля класса, а также должны быть скопированы базовые классы.
1 Различные контейнеры могут иметь различные интерфейсы, однако STL был спроектирована так, чтобы принцип работы с ними был единообразным. Таким образом, часть функций интерфейсов классов контейнеров пересекается, например все контейнеры имеют функцию получения количества элементов содержащихся в нем.