Пример создания динамического массива
Динамическим считается массив, который способен в любой момент изменять свой размер. Эта возможность обеспечивается за счет динамического выделения памяти под массив. При этом удобно создать класс, который является оболочкой для данного массива, отвечает за выделение и освобождение памяти под массив, а также обеспечивает доступ к элементам массива.
Когда пользователь создает объект класса-оболочки, конструктор класса выделяет память под массив, который имеет либо указанный пользователем размер, либо размер, заданный по умолчанию. Если по мере заполнения массива вся выделенная память окажется занятой, то при добавлении очередного элемента выделенная ранее память освобождается, все хранящиеся в массиве значения сохраняются во временном массиве. Затем выделяется память под массив большего размера и в него помещаются сохраненные значения. Таким образом, изменение размера массива происходит автоматически, невидимо для пользователя.
В настоящее время практически отпала необходимость использовать подобные динамические массивы, поскольку такие структуры данных, называемые контейнерами, в большом ассортименте представлены в стандартной библиотеке шаблонов С++ - Standard template library (STL), которая поддерживается практически всеми компиляторами. Наиболее типичным примером является класс vector, который содержит все необходимые функции и итераторы. Также полезными являются такие классы-контейнеры, как map, multymap, queue, deque, list, set, multyset.
Краткое описание:
- map - ассоциативный массив, который содержит пары "ключ - значение", обеспечивает доступ к значению по ключу.
- multymap -ассоциативный массив, в котором могут встречаться одинаковые по значению ключи.
- queue - очередь, т.е. массив, организованный по принципу FIFO ("first in first out")
- deque - очень напоминает vector; также как и vector поддерживает произвольный доступ к элементам, но не поддерживает некоторые функции, которые присутствуют в классе vector.
- list - список, которые не поддерживает доступ к элементу по индексу; вместо этого осуществляется поиск элемента по значению.
- set - множество (или простой ассоциативный массив), которое отличается от ассоциативного массива тем, что в нем ключ является одновременно и значением (имеет интерфейс, напоминающий интерфейс map, что позволяет безболезненно их чередовать)
- multyset - множество, в котором могут встречаться одинаковые по значению ключи.
В приведенной ниже программе на С++ реализованы далеко не все возможные и полезные функции для работы с динамическими массивами, т.к. она создана только для демонстрации принципа создания такого рода массивов.
Определение класса:
template<class T>
class DynamicArray {
long size; //размер массива
long count; //количество элементов в массиве
T* p; //указатель на начало массива
public:
//конструкторы
DynamicArray(long s = 10): size(s), count(0) {
p = new T[size];
if(!p)
cout << "Ошибка при создании массива" << endl;
}
DynamicArray(const DynamicArray& arr); //конструктор копирования
//деструктор
~DynamicArray() {
if(p) delete[] p;
}
//функции
void add(T x); //прибавить элемент в конец массива
void remove(); //удалить последний элемент
long length() const {return size;} //длина массива
void print() const; //вывод на экран
//операторы
DynamicArray& operator=(const DynamicArray& arr); //присваивание
T operator [] (long i) const; //индексация
DynamicArray& operator+(const DynamicArray& arr); //сложение
};
Реализация функций и операторов:
//копирующий конструктор
template<class T>
DynamicArray<T>::DynamicArray(const DynamicArray& arr) {
size = arr.size;
count = arr.count;
p = new T[size];
for(int i = 0; i<count; ++i)
p[i] = arr.p[i];
}
Здесь возвращаем значение по ссылке, чтобы можно было строить цепочку присваиваний:
template<class T>
DynamicArray<T>&
DynamicArray<T>::operator=(const DynamicArray& arr)
if(this != &arr) { //чтобы избежать присваивания самому себе
size = arr.size;
count = arr.count;
if(p) delete[] p;
p = new T[size];
for(int i = 0; i<count; ++i)
p[i] = arr.p[i];
}
return *this;
}
template<class T>
T DynamicArray<T>::operator[](long i) const {
if(i < size && i)
return p[i-1];
else
cout << "Неправильный индекс" << endl;
return 0;
}
template<class T>
DynamicArray<T>&
DynamicArray<T>::operator+(const DynamicArray& arr) {
DynamicArray temp(*this); //сохраняем значения во временном массиве
if(p) delete[] p;
size += arr.size;
count += arr.count;
p = new T[size];
for(int i = 0; i<temp.count; ++i)
p[i] = temp.p[i];
for(int i = 0; i<arr.count; ++i)
p[temp.count + i] = arr.p[i];
return *this;
}
template<class T>
void DynamicArray<T>::print() const {
cout << "The array contains:" << endl;
for(int i = 0; i<count; ++i)
cout << p[i] << ' ';
cout << endl;
}
template<class T>
void DynamicArray<T>::add(T x) {
if(count >= size) {
//увеличиваем размер массива
DynamicArray temp(*this);
if(p) delete[] p;
size += 10;
p = new T[size];
for(int i = 0; i<temp.count; ++i)
p[i] = temp.p[i];
}
p[count++] = x; //прибавить элемент в конец массива
}
template<class T>
void DynamicArray<T>::remove() {
if(count)
p[--count] = 0; //удалить последний элемент (если массив
//не пустой)
else
cout << "Массив пуст" << endl;
}
Оставить комментарий
Комментарии
