Simple class to mimic a dynamic array

Question

for my c++ class I was asked to write a class with the following characteristics:

Implement a vector replacement that operates only on integers (you don't need to use templates like the normal STL). Your class should have the following interface:

• A no-argument constructor that allocates a 32-element vector

• A constructor that takes an initial size as the argument

• A method get, taking an index and returning the value at that index

• A method set, that takes an index and a value, and sets the value at that index

• A method pushback that adds an element to the end of the array, resizing if necessary

• A method pushfront that adds an element to the beginning of the array

• A copy constructor and assignment operator

Your class should not leak memory; any memory it allocates must be deleted. Try to think carefully about how your class can be misused, and how you should handle those scenarios. What do you do if a user gives a negative initial size? What about accessing a negative index?

here is the code:

#include <iostream>
#include <algorithm> 
#include <iterator>
#include <assert.h>
class vector
{
 private:
 int *p;
 int seenIndex[100] = {0};
 int size = 32;
 int largest_ndx = -1;
 int elements = 0;
 public:
 vector();
 vector(int size);
 vector (const vector& other);
 void set(int num, int i);
 int get(int i);
 void pushback(int i);
 void pushfront(int i);
 ~vector();
 vector& operator= (const vector& other);
 void print();
};
vector::vector()
{
 p = new int[32];
}
vector::vector(int size)
{
 assert(size > 0);
 this->size = size;
 p = new int[size];
}
void vector::set(int num, int i)
{
 assert(i >= 0);
 /* if index has not been seen, add it (we do not want to update element count if we are inserting in
 a previously used index */
 if (std::find(std::begin(seenIndex), std::end(seenIndex), i) == std::end(seenIndex))
 {
 /* ensures pushback method will push element after largest set index */
 if (i > largest_ndx)
 largest_ndx = i;
 seenIndex[elements++] = i;
 }
 p[i] = num;
}
int vector::get(int i)
{
 return p[i];
}
void vector::pushback(int num)
{
 /* if size of vector is equal to element count; resize vector */
 if (size == elements)
 {
 size *= 2;
 int *temp = new int[size];
 for (int i = 0; i < size/2; i++)
 temp[i] = p[i];
 delete [] p;
 p = temp;
 p[elements++] =num;
 } else if (largest_ndx >= elements) /* if number was set to furthest index, push back after that */
 {
 p[largest_ndx + 1] = num;
 elements++;
 } else
 {
 p[elements++] = num;
 }
}
void vector::pushfront(int num)
{
 int i = size - 1;
 while (i != -1)
 {
 p[i+1] = p[i];
 --i;
 }
 p[0] = num;
 elements++;
}
vector::~vector()
{
 delete [] p;
}
vector& vector::operator= (const vector& other)
{
 if (this == &other)
 return *this; /* returns copy of current object */
 /* delete old memory since it is not needed and assign new memory */
 delete [] p;
 p = new int[other.size];
 for (int i = 0; i < other.size; i++)
 {
 p[i] = other.p[i];
 }
 for (int i = 0; i < 100; i++)
 this->seenIndex[i] = other.seenIndex[i];
 this->size = other.size;
 this->largest_ndx = other.largest_ndx;
 this->elements = other.elements;
 return *this;
}
vector::vector (const vector& other)
{
 p = new int[other.size];
 for (int i = 0; i < other.size; i++)
 p[i] = other.p[i];
 for (int i = 0; i < 100; i++)
 this->seenIndex[i] = other.seenIndex[i];
 this->size = other.size;
 this->largest_ndx = other.largest_ndx;
 this->elements = other.elements;
}
void vector::print()
{
 for (int i = 0; i < size; i++)
 std::cout << p[i] << " ";
}

Main function:

int main(int argc, const char * argv[]) {
 int x = 8;
 vector vec(x);
 for (int i = 0; i < 5; ++i) {
 vec.pushback(i);
 }
 std::cout << "Original vectors contents: " << std::endl;
 vec.print();
 std::cout << std::endl;
 vector newVec;
 newVec = vec;
 std::cout << "newVec contents (testing assignment operator): " << std::endl;
 newVec.print();
 std::cout << std::endl;
 newVec.pushfront(100);
 std::cout << "newVec contents after pushfront: " << std::endl;
 newVec.print();
 std::cout << std::endl;
 newVec.set(10, 0);
 std::cout << "newVec contents after set: " << std::endl;
 newVec.print();
 std::cout << std::endl;
 vector vec3(newVec);
 std::cout << "vec3 using copy constructor (taking in newVec): " << std::endl;;
 vec3.print();
 std::cout << std::endl;
 return 0;
}

Output:

Original vectors contents: 
0 1 2 3 4 8 5 131072 
newVec contents (testing assignment operator): 
0 1 2 3 4 8 5 131072 
newVec contents after pushfront: 
100 0 1 2 3 4 8 5 
newVec contents after set: 
10 0 1 2 3 4 8 5 
vec3 using copy constructor (taking in newVec): 
10 0 1 2 3 4 8 5 
Program ended with exit code: 0

My program works (as far as I can see), the real thing thats bothering me is I need an array to store the current indices used in the set method. If I don't store them then I cant keep track of how many elements I have, I cant simply increment elements every time I call set due to the fact that the user can set the same index. So basically the user can only use set a finite amount of times. Also, I am very new to programming and c++ is my first language, I am wondering if I handled the allocated memory properly.

• fernando.reyes: pushfront, why doesn't it check the size of the array if it is enough? You need to reuse code everywhere and not do things repeatedly, like when you have the constructor parameterless and with paremeters, the parameterless can call the other with parameter (32)
• Obito: @fernando.reyes I should add a check for pushfront. As for the constructors, our question asks for one parameterless constructor which will set the size to 32, another constructor to specify the size the user wants and the last one is simply the copy constructor.
• Incomputable: What seenIndex and largest_ndx are for? They look like an anomaly.
• Obito: @Olzhas The seenIndex is used to keep indices the user uses when they call the set method. I keep track of how many things were added with the elements variable, if I didn't have this array I could not differentiate when a user adds an element or if they simply write over an existing element by using the same index. I use the largest_ndx for the edge case when a user sets a value far down the vector using the set method then uses the pushback method to make sure the new number is pushed back "behind" the furthest indexed entry.
• Incomputable: I think you misunderstood the problem statement: set() shouldn't do pushback. I believe if the index is out of bounds you should just crash/go into undefined behavior. Also, are you sure it's everything that been asked? Without function to retrieve size it's impossible to iterate over this thing, which makes it barely usable

Answer 1

I'll list the things you should know to fully comprehend the review:

1.Automatic storage (sometimes called stack) and free store (heap)

2.Exceptions

3.Sad story about new and operator new

4.Data layout in memory, the thing that C++ standard says about it

Code Review:

I will not consider small and nitpicking optimizations, but I will provide some basic ones. I'll add another interface at the bottom of the post, since this one, may be not worst, but still is not good enough.

Anomaly:

I've got confused by the member variables of the class. Most people usually use something like this:

int* arr;
std::size_t size;
std::size_t capacity;

and are done with it.No need for anything else. In fact, you can decrease this thing further, leaving only a pointer (to do that, people usually "prefix" the size and capacity). Even after some answers on my questions I couldn't get why seenIndex should be there.

std::size_t:

Why std::size_t(aka size_t from C) ? The reason is that C++ (and probably C) standard guarantees that std::size_t will be large enough to index the whole, theoretically possible memory. std::numeric_limits<std::size_t>::max() will give you theoretical maximum memory available on the platform, but not the memory installed in the machine.

new:

In my opinion, new is a fail. It is one of the worst fails in the history of C++. The new should be an allocation mechanism, not a factory, which it is, currently. So, even if others will disagree, I will advice using std::malloc(). The cast will look ugly, but it is the thing that is called at the end of the day. All major compilers (VC++, icc, g++, clang++) call malloc from operator new. Array version of new is even worse, since it requires it to calldelete[], when there is no technical reason to make people call it.

this->member:

Personally I don't like this way of accessing members.

Since the bug in the pushfront() has been mentioned I will omit it.

pushback():

new might throw std::bad_alloc() exception. This will cause the pushback to terminate without doing the thing it should. But it is not the real problem here. The real problem is that you modify the size before checking if the new allocation is succeeded. So, what will happen is that size will increase, but the array on the heap will not. I will leave the possible consequences to your imagination.

Miscellaneous:

• Asymmetry: the call to set does bounds checking, whereas get does not.

• No check for success of allocation, if new in constructor failed, you're in realm of undefined behavior.

• Everything vaguely related to array indices should be std::size_t, to guarantee that it will be possible to access furthest elements. It will also imply to the programmers that negative values are prohibited.

• <algorithm> and <iterator> are needed as a consequence of strange seenIndex. I find it great for the library class to have as few dependencies as possible.

• Looping to copy contents of one vector to another can be replaced by a very trivial std::memset(). It might be faster as well.

• May be it is about design, but get() not returning a reference is rather odd.

Better design:

The first thing I found ridiculous was that I can't get the size of the container, so I can't iterate over it. This is why you needed the print() function, since you don't know the size of the container. I recommend the interface of std::vector<>. May be it is not the best, but it is very close to perfection.

• Incomputable: I will also leave a note about std::bad_alloc here: it doesn't provide setting the message to it. Intended? Probably.

Answer 2

The use of seenIndex / largest_ndx is overcomplicating things for no benefit (and would cause errors in some cases), and should be dropped.

Set (index, value)
If index < elements, just set p[index], nothing else is needed.
If it's greater, the usual convention is to throw an exception, but if you wanted to support automatic resizing it could do that in this case.
Instead of checking for index < 0, why not just use size_t?
Also, as a stylistic thing, I would put index before value in the parameters.

Push Back (value)
The new value should be placed at elements++, as you're doing in the else case. The largest_ndx check should not be necessary, because having more values present than elements would be an invalid state.

Length
As Incomputable mentioned, you really need to provide this as a public method for the class to be usable.

Misc
data or array would be a better name than p.
get should be const, and should take size_t instead of int.

Edit: I'm not sure if you're using elements / size in the normal way. Most vector implementations have two size values:
* The size of the underlying array (size, in yours)
* The logical size of the vector (elements?)
But everything within the logical size is valid data. You can only set v[5] if the logical size is 6+, and thus v[0] through v[4] are all valid. The alternative is a sparse vector, which is a more advanced data structure and doesn't appear to be what you're implementing.