Dynamic memory allocation, C++

Question

I need to write a function that can read a file, and add all of the unique words to a dynamically allocated array. I know how to create a dynamically allocated array if, for instance, you are asking for the number of entries in the array:

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

My problem is that I don't know ahead of time how many unique words are going to be in the file, so I can't initially just read the value or ask for it. Also, I need to make this work with arrays, and not vectors. Is there a way to do something similar to a push_back using a dynamically allocated array?

Right now, the only thing I can come up with is first to create an array that stores ALL of the words in the file (1000), then have it pass through it and find the number of unique words. Then use that value to create a dynamically allocated array which I would then pass through again to store all the unique words. Obviously, that solution sounds pretty overboard for something that should have a more effective solution.

Can someone point me in the right direction, as to whether or not there is a better way? I feel like this would be rather easy to do with vectors, so I think it's kind of silly to require it to be an array (unless there's some important thing that I need to learn about dynamically allocated arrays in this homework assignment).

EDIT: Here's another question. I know there are going to be 1000 words in the file, but I don't know how many unique words there will be. Here's an idea. I could create a 1000 element array, write all of the unique words into that array while keeping track of how many I've done. Once I've finished, I could provision a dynamically allocate a new array with that count, and then just copy the words from the initial array to the second. Not sure if that's the most efficient, but with us not being able to use vectors, I don't think efficiency is a huge concern in this assignment.

Answer 1

A vector really is a better fit for this than an array. Really.

But if you must use an array, you can at least make it behave like a vector :-).

Here's how: allocate the array with some capacity. Store the allocated capacity in a "capacity" variable. Each time you add to the array, increment a separate "length" variable. When you go to add something to the array and discover it's not big enough (length == capacity), allocate a second, longer array, then copy the original's contents to the new one, then finally deallocate the original.

This gives you the effect of being able to grow the array. If performance becomes a concern, grow it by more than one element at a time.

Congrats, after following these easy steps you have implemented a small subset of std::vector functionality atop an array!

Answer 2

As you have rightly pointed out this is trivial with a Vector.

However, given that you are limited to using an array, you will likely need to do one of the following:

1. Initialize the array with a suitably large size and live with poor memory utilization
2. Write your own code to dynamically increase the size of the array at run time (basically the internals of a Vector)

If you were permitted to do so, some sort of hash map or linked list would also be a good solution.

Answer 3

If I had to use an array, I'd just allocate one with some initial size, then keep doubling that size when I fill it to accommodate any new values that won't fit in an array with the previous sizes.

Since this question regards C++, memory allocation would be done with the new keyword. But what would be nice is if one could use the realloc() function, which resizes the memory and retains the values in the previously allocated memory. That way one wouldn't need to copy the new values from the old array to the new array. Although I'm not so sure realloc() would play well with memory allocated with new.

Answer 4

You can "resize" array like this (N is size of currentArray, T is type of its elements):

// 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;

Using this solution you have to copy the data. There might be a solution that does not require it.

But I think it would be more convenient for you to use std::vectors. You can just push_back into them and they will resize automatically for you.

Answer 5

You can cheat a bit:

use std::set to get all the unique words then copy the set into a dynamically allocated array (or preferably vector).

#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 6

This could be going a bit overboard, but you could implement a linked list in C++... it would actually allow you to use a vector-like implementation without actually using vectors (which are actually the best solution).

The implementation is fairly easy: just a pointer to the next and previous nodes and storing the "head" node in a place you can easily access to. Then just looping through the list would let you check which words are already in, and which are not. You could even implement a counter, and count the number of times a word is repeated throughout the text.