Выделение дополнительных элементов динамического массива в C++

Question

Я пытаюсь выяснить, могу ли я выделить дополнительную память для дополнительных элементов для динамического массива в C++. Для упрощения кода приведенный ниже код разделяется на просто важные вещи.

Что я в основном пытаюсь сделать, это прочитать элементы в arr в файле someClass из файла, но я хочу сделать так, чтобы файл не указывал, сколько элементов он содержит (это необходимо для полного проекта I я работаю). Я, очевидно, думал о решении выделить новый массив с size+1, а затем скопировать все текущие элементы в него и прочитать новый элемент, но я считаю, что это будет жестокая трата времени обработки и памяти, если возможно просто выделите следующий адрес памяти и используйте его для моего массива. Есть ли способ сделать это на C++?

Подводя итог, я хочу прочитать элемент, выделить новый адрес памяти для моего массива и затем прочитать другой элемент в этом вновь выделенном адресе памяти. Повторяйте до конца файла.

Не буду утомлять вас причинами, но использование простого std::vector не является вариантом.

Вот код:

class someClass { 
public: 
    int *arr; 
    void Read(ifstream&,int&); 
}; 

void someClass::Read(ifstream &inFile, int &size) { 
    arr = new int[0]; 
    inFile.open("input.txt"); 

    int index = 0; 
    int element; 
    while (!inFile.eof()) { 
     inFile >> element; 
     *(arr + index) = element; 
     index ++; 
    } 

    size = index; 
    inFile.close(); 
} 

int main() { 

    int size; 
    someClass a; 
    ifstream inFile; 

    a.Read(inFile,size); 
    //obviously unnecessary, just for testing 
    for(int i = 0; i < size; i ++) { 
     cout << a.arr[i] << " "; 
    } 
    cout << endl; 
} 

Answer 1

arr = new int[1]; 
int capacity = 1, size = 0; 
inFile.open("input.txt"); 

int element; 
while (!inFile.eof()) { 
    inFile >> element; 
    if (size == capacity){ 
     capacity *= 2; 
     int * newbuf = new int[capacity]; 
     std::copy_n(arr, size, newbuf); 
     delete[] arr; 
     arr = newbuf; 
    } 
    arr[size] = element; 
    size++; 
} 

size = index; 

inFile.close(); 

Вы можете имитировать то, что std::vector делает. Двойную емкость каждый раз, когда она заполняется.

Answer 2

Вам нужно будет сделать новое пространство для большего массива и перемещать старые значения:

void resize() { 
    size_t newSize = size * 2; 
    int* newArr = new int[newSize]; 
    memcpy(newArr, arr, size * sizeof(int)); 
    size = newSize; 
    delete [] arr; 
    arr = newArr; 
} 

Answer 3

Я предлагаю вам другое решение, в котором не нужно будет копировать каждый раз, когда ранее прочитанные содержимое файла. Идея состоит в том, чтобы использовать связанный список, в котором каждый элемент имеет размер, равный удвоенному его предшественнику (другая возможность - заставить его расти как серия Фибоначчи). Таким образом, распределения становятся все реже и реже по мере роста размера файла, и, в случае необходимости, вы можете освободить память из начала файла, освободив первые элементы в списке. Конечно, вы платите больше за чтение, так как доступ не является последовательным. Вот пример, иллюстрирующий идею:

struct buffer_list 
{ 
    void append_next_chunk(size_t size, char * buff) 
    { 
     if(buffer == nullptr) { 
      buffer = buff; 
      local_size = size; 
      return; 
     } 
     if(next == nullptr) next = new buffer_list(); 
     next->append_next_chunk(size, buff); 
    } 


    char read(int offset) 
    { 
     if(offset >= local_size) return next->read(offset-local_size); 
     return buffer[offset]; 
    } 
    buffer_list * next = nullptr; 
    char *buffer = nullptr; 
    size_t local_size = 0; 
    ~buffer_list() 
    { 
     delete[] buffer; 
     delete next; 
    } 
}; 


struct custom_vector 
{ 
    custom_vector(const size_t size) { 
     write_ptr = new char[size]; 
     inner_list.append_next_chunk(size, write_ptr); 
     total_size = size; 
     last_created_size = size; 
    } 


    void push_back(char c){ 
     if(written_size == total_size) 
     { 
      last_created_size *= 2; 
      write_ptr = new char[last_created_size]; 
      write_offset = total_size; 
      inner_list.append_next_chunk(last_created_size, write_ptr); 
      total_size += last_created_size; 
     } 
     write_ptr[written_size - write_offset] = c; 
     written_size++; 
    } 

    char read(int offset) 
    { 
     return inner_list.read(offset); 
    } 

    size_t size() { return written_size; } 

    char * write_ptr = nullptr; 
    buffer_list inner_list; 
    size_t written_size = 0; 
    size_t total_size = 0; 
    size_t write_offset = 0; 
    size_t last_created_size = 0; 
}; 

На моей машине custom_vector performes путь лучше, чем std::vector на операциях записи, в то время как большой штраф оплачивается при чтении. Однако я считаю, что некоторые оптимизации для последовательного чтения могут быть легко реализованы, решая проблему.

Answer 4

Мне просто понравился вопрос и сделал некоторые эксперименты самостоятельно, используя компилятор MSVC14 (оптимизация отключена).
C++, 11/14 имеет следующие контейнеры последовательности (преднамеренно исключены dynarry, введенные в С ++ 14):

1. Нет динамического изменения размера (до программиста, чтобы выделить и DEALLOCATE)
   • Raw массив (например, int char[])
   • Массив (например,new array<int, size>(){...})
2. С динамическое изменение размера
   • Vector (последовательное выделение памяти)
   • список (связанный список как массив)
   • forward_list (подобный список)
   • Deque (двусвязная очередь)

Позвольте мне начать с вопросов,

the solution of allocating a new array with a size+1, and then copying all the current elements into it and reading a new element, but I find that this would be a brutal waste of processing time and memory

Вы правы, но для уменьшения накладных расходов, при выделении памяти для использования и затем выяснить, что вам нужно больше памяти, чем выделенные, вам нужно выделить новую память и скопируйте предыдущие данные, затем освободите предыдущую выделенную память.
Но подождите! Сколько выделяется (размер + 1 плохо)? Каждый раз, когда вы вынуждены выделять больший объем памяти, вам лучше выделять в два раза больше того размера, который у вас уже был в руках, чтобы вы уменьшили вероятность повторного распределения памяти; потому что считается чрезвычайно дорогостоящей операцией.

if it is possible to simply allocate the next memory address and use it for my array. Is there a way to do that in C++?

Это не полностью под вашим контролем, поскольку среда выполнения C++ реализовала функции управления памятью. Если ваша вновь выделенная память будет, не находится под вашим контролем, однако иногда бывает так, что новое выделенное пространство будет иметь тот же базовый адрес, что и предыдущий; это зависит от времени выполнения и от memory fragmentation.

Я получил некоторые тесты с использованием malloc и realloc функций заимствованы из C. Вот код: (. Для вставки 100000000 целых чисел, время в среднем 3 прогонов)

auto start = chrono::steady_clock::now(); 

    auto partialSize = 100; 
    auto arr = (int *) malloc(sizeof(int) * partialSize); 


    for (auto i = 0; i < SIZE; i++) { 
     arr[i] = i; 
     if (i == partialSize - 1) { 
      partialSize = partialSize << 1; // for 2X 
      arr = (int *) realloc(arr, sizeof(int) * partialSize); 
     } 
    } 

    auto duration = chrono::steady_clock::now() - start; 

    free(arr); 

    cout << "Duration: " << chrono::duration_cast<chrono::milliseconds>(duration).count() << "ms" << endl; 

Результаты:

• Start Размер = 100, инкремент Steps = 1.5X, Time (s) = 1.35s
• Start Размер = 100, инкремент Steps = 2X, Time (s) = 0.65s

• Start Размер = 100, инкремента Steps = 4X, Time (s) = 0.42s

• Start Size = 10000, инкремента Steps = 1.5X, Time (s) = 0.96s

• Start Size = 10000, инкремент Steps = 2X, Time (s) = 0.79s

• Start Размер = 10000, инкремент шаги = 4X, Time (s) = 0.51s

  Другого случая использование C++ 's new ключевого слова и проверку перемещения :

  auto start = chrono::steady_clock::now(); 
  auto partialSize = 100; 
  auto arr = new int[partialSize]; 
  
  
  for (auto i = 0; i < SIZE; i++) { 
      arr[i] = i; 
      if (i == partialSize - 1) { 
       auto newArr = new int[partialSize << 2]; // for 4X 
       partialSize = partialSize << 2; 
       arr = newArr; 
      } 
  } 
  
  auto duration = chrono::steady_clock::now() - start; 
  
  delete[] arr; 
  
  cout << "Duration: " << chrono::duration_cast<chrono::milliseconds>(duration).count() << "ms" << endl; 
  

Результаты (для вставки 100 000 000 целых чисел; время - среднее. из 3 пробегов):

• Начальный размер = 100, приращение шагов = 1.5X, время (ы) = 0.63S
• Start Размер = 100, инкремент Steps = 2X, Time (s) = 0.44s

• Start Размер = 100, инкремент Steps = 4X, Time (s) = 0.36s

• Start Size = 10000, инкремент Steps = 1.5X, Time (s) = 0.65s

• Start Size = 10000, инкремент Steps = 2X, Time (s) = 0.52s
• Start Size = 10000, инкремент Steps = 4X, время (ы) = 0,42 с

Для остальных (контейнеры с изменяемой динамической способностью):

auto start = chrono::steady_clock::now(); 

//auto arr = vector<int>{}; 
//auto arr = list<int>{}; 
//auto arr = new std::array<int, SIZE>{}; 
//auto arr = new int[SIZE]; 
//auto arr = deque<int>{}; 
auto arr = forward_list<int>{}; 

for (auto i = 0; i < SIZE; i++) { 
    arr.push_front(i); 
    // arr.push_back(i) 
} 

auto duration = chrono::steady_clock::now() - start; 

cout << "Duration: " << chrono::duration_cast<chrono::milliseconds>(duration).count() << "ms" << endl; 

Результаты (для вставки 100 000 000 целых чисел; время - среднее. от 3 работает):

1. вектор

   • Время (s) = 2.17s

2. список

   • Время (s) = 10,31 s

3. массив (без Перераспределение)

   • Время (с) = N/A; Ошибка: компилятор из кучи.

4. сырья INT массива (без Перераспределение)

   • Время (с) = 0.22s

5. Deque

   • Время (с) = 3.47s

6. forward_list

   • Время (s) = 8.78s

Надеется, что это помогает.

Answer 5

Вы можете прочитать количество элементов в файле, посчитав разделители, а затем размер массива.Например, давайте предположим, что ваш файл ограничен линиями, как:

1 
2 
3 
4 
5 

Вы можете подсчитать количество строк в файле с соответствующим сепаратором линии. В Linux это можно сделать:

int elemCount = std::count(std::istreambuf_iterator<char>(inFile), 
    std::istreambuf_iterator<char>(), '\n'); 
inFile.clear(); 
inFile.seekg(0, std::ios::beg); 

Затем вы можете выделить массив как:

arr = new int[elemCount]; 

Если вы используете пространство или табуляцией, чем изменение от '\n' к ' ' или '\t' или любой другой. Затем вы можете читать информацию, как и раньше. Возможно, вам потребуется добавить или вычесть 1 в зависимости от вашего разделителя и способа создания файла. Это также немного опасно, поскольку пустые строки, двойные разделители и т. Д. Могут испортить счет. Если бы я это сделал, я бы заполнил массив некоторым значением по умолчанию, а затем удалил их после прочтения, чтобы убедиться, что все мои значения были хорошими. Это потребует изменения размера после завершения чтения.