Page 1 of 1

The reasons for using vectors Rate Topic: -----

#1 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3585
  • View blog
  • Posts: 12,907
  • Joined: 08-August 08

Posted 17 September 2016 - 01:42 PM

It's fairly common on this site and others that a question will be related to dynamic arrays. Often the OP is asked why they're not using vectors instead, and the real answer to that is often that they're intimidated by them. My goal here is to make them familiar by showing how they came about. I'm not trying to show it in a historically accurate way, you can look that up if you like. I am trying to show how if vectors didn't yet exist, they'd be invented almost immediately, because they have some significant advantages.

Letís start by looking at a dynamically allocated array. The code below starts with an array capable of holding just 2 elements. As it adds elements and reaches the end of the array, it creates a new array twice the size of the previous array and copies the old array to the new before deleting the old array. This works well, but in practice there are a couple of things that are easy to mess up. Forgetting to delete or copy is easy to do in a larger project, and not always easy to debug.
#include <iostream>

using namespace std;

void showArray(int arr[], int arrayCount) {
	cout << "Array values:\n";
	for(int i = 0; i < arrayCount; i++) {
		cout << arr[i] << endl;
	}
	cout << endl;
}

int main(int argc, const char * argv[]) {
	int arraySize = 2, *myArray;
	myArray = new int[arraySize]; // Start out with an array of 2 uninitialized elements

	for(int i = 0; i < 11; i++) {
		if(i == arraySize) { // Need more space?
			int *temp = new int[2*arraySize]; // Double the space
			memcpy(temp,myArray,arraySize * sizeof(int)); // Copy to new, expanded space
			delete myArray; // delete the old
			myArray = temp; // set the pointer to new space
			arraySize *= 2; // set array size to double its old size
		}
		myArray[i] = i*10; // initialize the ith value to i*10
		showArray(myArray, i+1); // Array will have i+1 elements since we're starting from 0
	}

	cout << "\nSame thing using a 'normal' array:\n";
	int normalArray[11];
	for(int i = 0; i < 11; i++) {
		normalArray[i] = i;
		cout << "i = " << i << "\n";
		showArray(normalArray, i+1);
	}

	return 0;
}



Now letís look at a class that manages the dynamic array for us. The code below allows us to ďpushĒ elements onto an internally managed dynamic array. Using it, we donít need to worry about deleting or expanding our array. The class does it for us! There are still some limitations. For example, the array must be of the type declared in the class (here itís int) so weíd need many versions of the same class to handle doubles, strings, or other classes.
#include <iostream>

using namespace std;

class arrayClass {
	int mysize;
	int maxsize;
	int *myArray;

public:
	arrayClass() : maxsize(2) {
		myArray = new int[maxsize]; // Start out with an array of 2 uninitialized elements
		mysize = 0; // We haven't initialized either element
	}

	~arrayClass() {
		delete [] myArray;
	}
	void push_back(int num) {
		// Need more space?
		if(mysize < maxsize) {
			// No, so assign value and increment index
			myArray[mysize] = num;
			mysize++;
		} else {
			// Yes, so
			int *tmp = new int[maxsize*2]; // Double the space
			memcpy(tmp, myArray, sizeof(int)*maxsize); // Copy to new, expanded space
			delete myArray; // delete the old
			myArray = tmp; // set the pointer to new space
			maxsize *= 2; // set array size to double its old size
			myArray[mysize] = num; // initialize the ith value to num
			mysize++; // increment the index
		}
	}

	int operator [](int n) {
		return myArray[n];
	}

	void showArray() {
		cout << "Size of array: " << mysize << " maxsize: " << maxsize << endl;
		cout << "Array values:\n";
		for(int i = 0; i < mysize; i++) {
			cout << myArray[i] << endl;
		}
		cout << endl;
	}

};

int main(int argc, const char * argv[]) {

	arrayClass sample;

	for(int i = 0; i < 11; i++) {
		sample.push_back(i*10); // Add 10*i to the end of the dynamic array
		cout << "i = " << i << endl;
		sample.showArray();
	}

	return 0;
}


A more complete approach it to use C++ templates. The code below handles arrays of strings, integers, doubles, and classes like the one (apoint) provided. From here, I hope itís clear how the rest of the vector class would evolve into what it is today.
#include <iostream>

using namespace std;

template <class T>
class vectorSimulator {
	int mysize;
	int maxsize;
	T *myarray;

public:
	vectorSimulator() {
		mysize = 0;
		maxsize = 2;
		myarray = new T[maxsize];
	}

	vectorSimulator(vectorSimulator<T> &orig) {
		mysize = orig.mysize;
		maxsize = orig.maxsize;
		myarray = orig.myarray;
	}

	~vectorSimulator() {
		delete [] myarray;
	}

	void push_back(T &item) {
		if (mysize < maxsize) {
			myarray[mysize] = item;
			mysize++;
		} else {
			T *newarray;
			newarray = new T[maxsize*2];
			memcpy(newarray, myarray, maxsize*sizeof(T));
			delete [] myarray;
			myarray = newarray;
			maxsize *=2;
			myarray[mysize]=item;
			mysize++;
		}
	}

	void erase(int n) {
		if(n < mysize && n >= 0) {
			for (int i = n; i < mysize-1; i++) {
				myarray[i] = myarray[i+1];
			}
			mysize--;
		}
	}

	void erase(int n, int m) {
		if(n+m < mysize && n >= 0 && m > 0) {
			for (int i = n; i <= n + m; i++) {
				myarray[i] = myarray[i+m];
			}
			mysize = mysize - m;
		}
	}


	int vectorsize() {
		return mysize;
	}

	T operator [](int n) {
		return myarray[n];
	}

};

template <class T2>
void show(vectorSimulator<T2> &vec) {
	for (int i = 0; i < vec.vectorsize(); i++) {
		cout << i << ": " << vec[i] << endl;
	}
}

template <typename T3>
void show_special(vectorSimulator<T3> &vec) {
	for (int i = 0; i < vec.vectorsize(); i++) {
		cout << i << ": " << vec[i].print() << endl;
	}
}


class apoint {
	double x,y;
public:
	apoint() {}
	apoint(double a, double b ) {x=a;y=b;}
	string print() {
		char p[50];
		sprintf(p, "%1.2f, %1.2f", x, y);
		return p;
	}
};

int main() {
	vectorSimulator<string> test_strings;
	vectorSimulator<int> test_integers;
	vectorSimulator<double> test_doublefloats;
	vectorSimulator<apoint> point_tests;

	string test_string[10] = {"One","two","three","four","five","six","seven","eight","nine","ten"};
	int test_ints[10] = {1,2,3,4,5,6,7,8,9,10};
	double test_doubles[10] = {.1,.2,.3,.4,.5,.6,.7,.8,.9,1.0};
	string temp;
	int index;
	
	for (int i = 0; i < 33; i++) {
		index = i % 10;
		test_strings.push_back(test_string[index]);
	}
	for (int i = 0; i < 10; i++) {
		test_integers.push_back(test_ints[i]);
	}
	for (int i = 0; i < 10; i++) {
		test_doublefloats.push_back(test_doubles[i]);
	}

	for (int i = 0; i < 6; i++) {
		apoint temp(test_ints[i],test_doubles[i]);
		point_tests.push_back(temp);
	}

	cout << "Strings\n";
	show(test_strings);
	test_strings.erase(1,2);
	cout << endl << "test erase\n";
	show(test_strings);
	cout << endl << "Integers\n";
	show(test_integers);
	cout << endl << "Doubles\n";
	show(test_doublefloats);
	cout << endl << "Points\n";
	show_special(point_tests);
	return 0;
}



Is This A Good Question/Topic? 0
  • +

Replies To: The reasons for using vectors

#2 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3585
  • View blog
  • Posts: 12,907
  • Joined: 08-August 08

Posted 17 September 2016 - 09:29 PM

View PostCTphpnwb, on 17 September 2016 - 04:42 PM, said:

Forgetting to delete or copy is easy to do in a larger project

As if to emphasize this fact, it turns out I have a mistake in line 17 of the second set of code above: delete myArray; should be delete [] myArray;. The actual vector class has been tested much more thoroughly than this code, so you can be sure issues like this have been shaken out. ;)
Was This Post Helpful? 0
  • +
  • -

#3 andrewsw  Icon User is online

  • don't rely on secrecy
  • member icon

Reputation: 6086
  • View blog
  • Posts: 24,170
  • Joined: 12-December 12

Posted 18 September 2016 - 01:45 AM

I have corrected the original code.
Was This Post Helpful? 0
  • +
  • -

#4 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3585
  • View blog
  • Posts: 12,907
  • Joined: 08-August 08

Posted 18 September 2016 - 05:10 AM

That's fine, but I was going to leave it as it was. It served as an example of how little mistakes can hide in the larger project and bolstered the case for using vectors!
Was This Post Helpful? 0
  • +
  • -

#5 andrewsw  Icon User is online

  • don't rely on secrecy
  • member icon

Reputation: 6086
  • View blog
  • Posts: 24,170
  • Joined: 12-December 12

Posted 18 September 2016 - 05:14 AM

Okay. I can put it back and remove these last few posts if you like? I like to keep tutorials tidy ;)
Was This Post Helpful? 0
  • +
  • -

#6 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3585
  • View blog
  • Posts: 12,907
  • Joined: 08-August 08

Posted 18 September 2016 - 05:24 AM

It's fine either way, since we now have the discussion about it. I just noticed another issue. On my system apparently std::string is included somewhere in iostream, so it still works when I use it without including string. Other systems may need #include <string> at the top of the third code set.
Was This Post Helpful? 0
  • +
  • -

#7 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3585
  • View blog
  • Posts: 12,907
  • Joined: 08-August 08

Posted 26 September 2016 - 04:28 AM

P.S.: This tutorial teaches the logic behind the development of vectors (the why) so it has some similarities to the vector class in the standard, but it's not designed to teach how to use them. For those interested in a tutorial on how to use the actual vector class, there is this.

This post has been edited by CTphpnwb: 26 September 2016 - 04:28 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1