C++ Implementation using a Vector

This is the third blog entry in the sequence that deals with a conversation with a couple colleagues.

This blog entry shows the implementation using the C++ programming language for the problem described in the first blog entry using a vector. As in the previous blog entry, let’s first look at the code used to implement the main() function.

int main()
{

	vector	vect;

	int		element = 0,
			pos	= 0;

	// **** ****

	cout << "<<< inserting ..." << endl;

	// **** start timing ****

	clock_t	begin = clock();

	// **** populate the vector with random numbers ****

	for (int i = 0; i < N; i++)
	{

		// **** generate a random integer in the specified range ****

		element = NextInt();

		// **** insert the element into the vector (sorted ascending order) ****

		InsertElement(vect, element);

		// **** display the vector ****

		DumpVector(vect);
	}

	// **** ****

	cout << "<<< removing ..." << endl;

	// **** loop removing elements from random positions ****

	for (int i = 0; (i < N) && (vect.size() > 0); i++)
	{

		// **** generate random position ****

		pos = RandomPosition(vect.size());

		// **** remove the element at the specified position from vector ****

		RemoveElement(vect, pos);

		// **** display the vector ****

		DumpVector(vect);
	}

	// **** compute the elapsed time ****

	clock_t	end = clock();
	double	elapsedTime = double(end - begin) / CLOCKS_PER_SEC;

	// **** display we are done ****

	cout << "<<< vector done N: " << N << " elapsedTime: " << elapsedTime << endl;

	// **** ****

	return 0;
}

The first loop is used to populate the vector with N random numbers. The first function in the loop generates a random integer and the second inserts the integer into the vector at the proper position. The requirement calls for keeping the sequence of integers in the vector in ascending order. For testing purpose, we invoke a third function to display the contents of the vector after an element is inserted.  This is used to visually verify that the mechanism is working properly.

The second loop generates a random position in the vector to be used to remove an element.  It is followed by a function that removes the element form the vector at the specified position. The function used to display the vector to verify the proper operation of the removal mechanism is then called.

Following is the code used by the InsertElement() function to insert the random generated integer element into the vector at the proper location.

void	InsertElement(vector &vect, int element)
{

	vector::iterator	it;

	// **** insert the element in an empty vector ****

	if (vect.size() == 0)
	{
		vect.push_back(element);
		return;
	}

	// **** look for the element in the vector that is greater than 
	//	the element we wish to insert and insert the element ****

	for (it = vect.begin(); it != vect.end(); it++)
	{
		if (element < *it)
		{
			vect.insert(it, element);
			return;
		}
	}

	// **** insert the element in the vector ****

	vect.push_back(element);
}

First a check is made to determine if the vector is empty.  If so, the specified element is inserted into the empty vector and the function returns.

If the vector is not empty, the loop is used to look for the proper location at which the new element should be inserted.  When the position in the vector is found, the new element is inserted and the function returns.

Finally, if we finish traversing the sorted vector without inserting the element, the new integer must be larger that all elements in the vector. The new element is inserted into the vector after the last entry.

The code for the function RemoveElement() used to remove an element from the vector at a random position follows.

void	RemoveElement(vector &vect, int pos)
{

	int			i = 0;

	vector::iterator	it;

	// **** get to the element that will be removed ****

	for (it = vect.begin(); it != vect.end(); it++, i++)
	{
		if (i == pos)
		{
			vect.erase(it);
			return;
		}
	}
}

The loop traverses the vector all the way up to the specified position. As the vector is traversed, the counter is compared with the specified position. Once the position is found, the element is removed from the vector.

The RandomPostion() function generates a random number in the range of elements in the specified vector.

int	RandomPosition(int totalElements)
{
	return randGen() % totalElements;
}

NextInt() as the RandomPosition() are convenience functions. The NextInt() function generates a random value for an element to be inserted into the vector.

int	NextInt()
{
	return minRand + (randGen() % maxRand) - minRand;
}

As one should be able to tell, all requirements for the problem are met using a vector instead of a list. At first, most developers would go for a vector implementation to address the requirements.  Such approach is reasonable. If there is additional time, or if the performance is not as desired, additional avenues should be explored.

In the next blog, a similar implementation based on arrays is presented.

John Canessa