Merge List for arrays and lists

[Howdydoody]

1) Write a function that merges two instances of the List ADT using the following specifications:
MergeList (List list1, List list2, List& result)
• list1 and list2 have been initialized and are sorted using function ComparedTo
• result is a sorted list that contains all of the items
a. Write the prototype for MergeLists.
b. Write the function definition, using an array-based implementation.
c. Write the function definition, using a linked implementation.
d. Describe the algorithm in terms of Big-O.

I think I've got some of this right but im not so sure about Lists or exactly what shes looking for on the prototype.

This is for the prototype.

void Merge(int[], int[], int[]);

This is the code for b that i have so far.

void Merge(int*list1[], int*list2[],int*listResult[])
{
	int num1 =0;
	int num2 =0;
	int num3 =0;
	while((num1<list1.length()) && (num2<list2.length())
	{
		if(list1[num1]<list2[num2])
		{
			listResult[num3]=list1[num1];
			num1++;
		}
		else
		{
			listResult[num3]=list2[num2];
			num2++;
		}
		num3++;
	}
	while(num2<list2.length())
	{
		listResult[num3] = list2[num2];
		num2++;
		num3++;
	}
	while(num1<list1.length())
	{
		listResult[num3] = list1[num1];
		num1++;
		num3++;
	}
}

As for the rest im pretty lost. Any help would be appreciated.

[Howdydoody]

I've started trying to work out the part with the list implementation.

void Merge(list<int> one, list<int> two, list<int> result)
{
	while((!one.empty()) && (!two.empty))
	{
//Right here i want to compare the head's value of the two lists
		if(ones head<twos head)
		{
//Right here i want to add the head of one in the parentheses but dont know how 
			result.push_back(ones head);			
                        one.pop_front();
		}
		else
		{
//same thing here except the head of two
			result.push_back(twos head);			
                        two.pop_front();
		}

[ravenous]

You should pass the result list by reference, otherwise it will never be changed in the calling function. So, the prototype should look like:

void Merge(list< int > one, list< int > two, list< int > &result);

You might consider passing them all by reference, for faster passing. In this case, you should make the ones that you don't want to change const . Something like:

void Merge(const list< int > &one, const list< int > &two, list< int > &result);

[Howdydoody]

This is what i ended up with =D.
Thanks for the response and the tip. Using references and pointers is also a little gray for me so the tip was much appreciated. Now im just worried about my syntax since C++ is still new to me.

void Merge(list<int> &one, list<int> &two, list<int> &result)
{
	while((!one.empty()) && (!two.empty))
	{
		if(one.front() < two.front())
		{
			result.push_back(one.front());
			one.pop_front();			
		}
		else
		{
			result.push_back(two.front());
			two.pop_front();		
}		
	}
	while(!one.empty())
	{
		result.push_back(one.front());
		one.pop_front();
	}
	while(!two.empty())
	{
		result.push_back(two.front());
		two.pop_front();
	}
}

[ravenous]

Passing by reference is powerful, but must be done with responsibility. When you pass to a function like this, it has access to the actual data in the arguments (in this case, your lists). This is good if you want to return the result, like you do here for result list. However, there's also the possibility that lists one and two could also get changed (if you forget that you're not supposed to change them, which won't happen here but can easily happen on a much bigger project). To prevent this, you can pass a const reference to the function, like this:

void Merge(const list<int> &one, const list<int> &two, list<int> &result);

That way, if you try and change them inside Merge , you'll get a friendly compile-time error, rather than a nasty, lawsuit-inducing run-time error! This is part of the principle of least privilege.

EDIT: I've just re-read your code. A const-reference won't work for you since you're using pop_front() . This is going to have the result of permanently removing the data from the original lists (even in the calling function) is this what you want? If not, you should either pass one and two by value, or find an algorithm that doesn't use pop_front() .

[Howdydoody]

Thanks rav. Cleared up alot for me right here =)

Edit: im not really concerned with what happens to the original lists as long as the data gets merged into the new list fine.

[ravenous]

Edit: im not really concerned with what happens to the original lists as long as the data gets merged into the new list fine.

You mean you're not concerned right now. You may be in the future, and at that point you'll wonder why everything's crashing all the time!

In general, functions shouldn't change variables unless changing those variables is the point of the function. In this case, you would expect result to be changed, but not necessarily one or two . It's, therefore, good programming practice to politely leave those variables untouched :) You'll regret it if you don't!