Ввод массива неизвестной длины

266

02 января 2018, 15:42

В строку вводятся n чисел, n неизвестно. Как лучше реализовать подобный ввод массива?

while(cin >>value) 
{
    arr1[i]=value;
    i+=1;
}

Знаю, что есть ф-ция strtok, может, она лучше подойдет? Использовать можно лишь простейшие функции, стандартные типы.

Answer 1

Как всегда, решение подобных задач может идти по одному из вариантов:

Двойной проход: сначала сделать "холостой проход" по входным данным, в котором просто вычислить требуемый размер массива. Затем выделить массив требуемого размера. Затем выполнить второй проход по тем же входным данным, уже помещая их в готовый массив.

Этот способ применим только тогда, когда есть возможность многопроходной обработки входных данных и выполнение двух проходов вместо одного не является слишком дорогой операцией.
Перевыделение массива: читаемые данные помещаются в массив, размер которого по необходимости наращивается (путем перевыделения памяти) в процессе чтения.

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

Этот способ является попыткой соединить в себе преимущества первого и второго способа. Платой за это является повышенный расход памяти в процессе чтения (список вместо массива).

У каждого способа есть свои преимущества и недостатки. В вашем - простейшем - случае скорее всего применимы они все. Однако если никаких ограничений на количество входных чисел не накладывается, то, наверное, разумнее всего будет пойти по второму пути.

Схематично, работу по второму пути можно изобразить так

// Изначально у нас есть "массив" нулевого размера
std::size_t n = 0;
int *a = nullptr;
// Читаем значения      
int value;
for (std::size_t i = 0; std::cin >> value; ++i)
{
  if (i >= n)
  { // Необходимо увеличить размер массива
    // Вычисляем новый (больший) размер массива в соответствии с 
    // какой-нибудь выбранной стратегией наращивания размера
    std::size_t new_n = ...;
    // Например
    //   new_n = i + 1
    // или
    //   new_n = n > 0 ? n * 2 : 1;
    // Выделяем новую память
    int *new_a = new int[new_n];
    // Как-то копируем уже существующие данные из старого массива в новый
    ...;
    // Уничтожаем старый массив и переходим на использование нового
    delete[] a;
    n = new_n;
    a = new_a;
  }
  // Записываем в массив прочитанное значение         
  a[i] = value;
}