Динамическое выделение памяти, C ++

Question

Мне нужно написать функцию, которая может читать файл, и добавить все уникальные слова в динамически распределяемый массив. Я знаю, как создать динамически размещенный массив, если, например, вы запрашиваете количество записей в массиве:

int value;
cin >> value;
int *number;
number = new int[value];

Моя проблема в том, что я заранее не знаю, сколько уникальных слов будет в файле, поэтому я не могу сначала просто прочитать значение или попросить его. Кроме того, мне нужно сделать эту работу с массивами, а не с векторами. Есть ли способ сделать что-то похожее на push_back с использованием динамически распределенного массива?

Прямо сейчас, единственное, что я могу придумать, - это сначала создать массив, в котором хранятся ВСЕ слова в файле (1000), затем пройти через него и найти количество уникальных слов. Затем используйте это значение для создания динамически распределенного массива, который я затем передам снова, чтобы сохранить все уникальные слова. Очевидно, что это решение звучит довольно заурядно для чего-то, что должно иметь более эффективное решение.

Может ли кто-нибудь указать мне правильное направление относительно того, есть ли лучший путь? Я чувствую, что это было бы довольно легко сделать с векторами, поэтому я думаю, что глупо требовать, чтобы он был массивом (если нет какой-то важной вещи, которую мне нужно узнать о динамически размещаемых массивах в этом домашнем задании).

РЕДАКТИРОВАТЬ: Вот еще один вопрос. Я знаю, что в файле будет 1000 слов, но я не знаю, сколько будет уникальных слов. Вот идея. Я мог бы создать массив из 1000 элементов, записать все уникальные слова в этот массив, отслеживая, сколько я сделал. Как только я закончил, я мог бы обеспечить динамическое выделение нового массива с этим счетчиком, а затем просто скопировать слова из исходного массива во второй. Не уверен, что это наиболее эффективно, но поскольку у нас нет возможности использовать векторы, я не думаю, что эффективность является серьезной проблемой в этом задании.

Answer 1

Вектор действительно лучше подходит для этого, чем массив.Действительно.

Но если вам необходимо использовать массив, вы можете по крайней мере заставить его вести себя как вектор: -).

Вот как: выделить массив с некоторой емкостью.Сохраните выделенную емкость в переменной «Capacity».Каждый раз, когда вы добавляете в массив, увеличивайте отдельную переменную "length".Когда вы добавите что-то в массив и обнаружите, что он недостаточно большой (длина == емкость), выделите второй, более длинный массив, затем скопируйте содержимое оригинала в новый и, наконец, освободите оригинал.

Это дает эффект увеличения массива.Если производительность становится проблемой, увеличивайте ее более чем на один элемент за раз.

Поздравляю, после выполнения этих простых шагов вы реализовали небольшое подмножество функций std :: vector поверх массива!

Answer 2

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

Поскольку этот вопрос касается C ++, выделение памяти будет выполняться с помощью ключевого слова new. Но было бы хорошо, если бы можно было использовать функцию realloc(), которая изменяет размер памяти и сохраняет значения в ранее выделенной памяти. Таким образом, не нужно будет копировать новые значения из старого массива в новый. Хотя я не уверен, что realloc() будет хорошо играть с памятью, выделенной new.

Answer 3

Как вы правильно заметили, это тривиально для вектора.

Однако, учитывая, что вы ограничены использованием массива, вам, вероятно, потребуется выполнить одно из следующих действий:

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

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

Answer 4

Вы можете немного обмануть:

используйте std :: set, чтобы получить все уникальные слова, а затем скопируйте набор в динамически размещенный массив (или, предпочтительно, вектор).

#include <iterator>
#include <set>
#include <iostream>
#include <string>


    // Copy into a set
    // this will make sure they are all unique   
    std::set<std::string>   data;
    std::copy(std::istream_iterator<std::string>(std::cin),
              std::istream_iterator<std::string>(),
              std::inserter(data, data.end()));

    // Copy the data into your array (or vector).
    std::string* words  = new std::string[data.size()];
    std::copy(data.begin(), data.end(), &words[0]);

Answer 5

Вы можете «изменить размер» массива следующим образом (N - это размер currentArray, T - это тип его элементов):

// create new array
T *newArray = new T[N * 2];
// Copy the data
for ( int i = 0; i < N; i++ )
 newArray[i] = currentArray[i];
// Change the size to match
N *= 2;
// Destroy the old array
delete [] currentArray;
// set currentArray to newArray
currentArray = newArray;

Используя это решение, вы должны скопировать данные. Там может быть решение, которое не требует этого.

Но я думаю, вам будет удобнее использовать std :: vectors . Вы можете просто push_back в них, и они автоматически изменят размер для вас.

Answer 6

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

Реализация довольно проста: просто указатель на следующий и предыдущий узлы и хранение «головного» узла в месте, к которому можно легко получить доступ. Тогда, просто просматривая список, вы сможете проверить, какие слова уже есть, а какие нет. Вы могли бы даже реализовать счетчик и подсчитать, сколько раз слово повторяется по всему тексту.