C++ Implementation using a List

This is the second 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 list. Let’s first look at the code used to implement the main() function.

int main ()
{

	list		li;

	int		element	= 0,
			pos	= 0;

	// **** ****

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

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

	clock_t	begin = clock();

	// **** populate list with random numbers ****

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

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

		element = NextInt();

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

		InsertElement(li, element);

		// **** display the list ****

		DumpList(li);
	}

	// **** ****

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

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

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

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

		pos = RandomPosition(N - i);

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

		RemoveElement(li, pos);

		// **** display the list ****

		DumpList(li);
	}

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

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

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

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

	// **** ****

	return 0;
}

The first loop is used to populate the list with N random numbers. The first function in the loop generates a random integer and the second inserts the integer into the list at the proper position. The requirement calls for keeping the list in ascending order. For testing we invoke a third function to display the contents of the list after a new element is inserted.  This is used to make sure the mechanism is working properly.

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

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

void	InsertElement (list &li, int element)
{

	list::iterator	it;

	// **** insert element in an empty list ****

	if (li.empty())
		{
		li.push_front(element);
		return;
		}

	// **** look for the element in the list that is greater
	//	than the element we wish to insert ****
	
	for (it = li.begin(); it != li.end(); it++)
	{
		if (element < *it)
		{
			li.insert(it, element);
			return;	
		}
	}

	// **** ****

	li.push_back(element);
}

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

If the list 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 list is found, the new element is inserted and the function returns.

Finally, if we finish traversing the sorted list, the new integer must be larger that all elements in the list. The new element is appended to the list.

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

void	RemoveElement(list &li, int pos)
{

	int			i = 0;

	list::iterator	it;

	// **** search for the element to be removed ****

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

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

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

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 list.

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

As one can tell, all the requirements are met using a list.

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

John Canessa