Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »
реклама
Недорогие очки виртуальной реальности для ПК на magazin-vr.ru.

Почтовая рассылка

Подписчиков: 11829
Последний выпуск: 19.06.2015

Пример создания динамического массива

Автор: Трубецкой Алексей
trubetskoy1.narod.ru
1 декабря 2009 года

Динамическим считается массив, который способен в любой момент изменять свой размер. Эта возможность обеспечивается за счет динамического выделения памяти под массив. При этом удобно создать класс, который является оболочкой для данного массива, отвечает за выделение и освобождение памяти под массив, а также обеспечивает доступ к элементам массива.

Когда пользователь создает объект класса-оболочки, конструктор класса выделяет память под массив, который имеет либо указанный пользователем размер, либо размер, заданный по умолчанию. Если по мере заполнения массива вся выделенная память окажется занятой, то при добавлении очередного элемента выделенная ранее память освобождается, все хранящиеся в массиве значения сохраняются во временном массиве. Затем выделяется память под массив большего размера и в него помещаются сохраненные значения. Таким образом, изменение размера массива происходит автоматически, невидимо для пользователя.

В настоящее время практически отпала необходимость использовать подобные динамические массивы, поскольку такие структуры данных, называемые контейнерами, в большом ассортименте представлены в стандартной библиотеке шаблонов С++ - 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;
}

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 

Комментарии

1.
59K
08 марта 2010 года
Arktos
0 / / 08.03.2010
+2 / -0
Мне нравитсяМне не нравится
8 марта 2010, 20:57:20
Неэкономично увеличивать массив каждый раз на 10 элементов. Лучше увеличивать в n раз (как правило 2, а размер держать как степень 2), тогда получим линейную асимптотику. И урезать массив нужно при уменьшении элементов в нем, но делать это осторожно - оставив линейную асимптотику
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог