Returning a List

[yem]

Hey,
I'm supposed to merge two list in a non descending order.
I'm given a main that I have to use and cannot change. The merge function has to be a global function and cannot be friend of List or Link. When I debug I see that the merge function seems to work but just as it returns it it "resets" and points to NULL. Anyone know what's wrong?
Thanks
I'm including the 3 program files.

  //Main.cpp
#include<iostream>
#include"List.h"

using namespace std;

List merge(List& lst1, List& lst2);

void makeSet(List& lst);

int main()
{
	List lst1, lst2, mergedList;

	cout << "enter sorted values for the first list:" << endl;
	cin >> lst1;
	cout << "enter sorted values for the second list:" << endl;
	cin >> lst2;

	mergedList = merge(lst1, lst2);
	cout << "the new merged list: " << mergedList << endl;

	makeSet(mergedList);
	cout << "the new merged set: " << mergedList << endl;

	system("pause");

	return 0;
}

List merge(List& lst1, List& lst2)
{
	List lst3;

	while (!lst1.isEmpty() )
	{
		lst3.add(lst1.firstElement());
		lst1.removeFirst();
	}
	
	while (!lst2.isEmpty())
	{
		lst3.insert(lst2.firstElement());
		lst2.removeFirst();
	}

	return lst3;
}

void makeSet(List& lst)
{
	List l = lst;

	int temp,instanceOf;

	while (!l.isEmpty())
	{
		temp = l.firstElement();

		instanceOf = lst.countInstance(temp);

		if (instanceOf > 1)
			for (int i = 0; i < instanceOf - 1; i++)
				l.remove(temp);	
	}
}

//List.h
#pragma once

#include<iostream>

using namespace std;

//------------------------------------------------
// class List
// arbitrary size Lists
// permits insertion and removal
// only from the front of the List
//------------------------------------------------
class List
{
protected:
	//--------------------------------------------
		// inner class link
		// a single element for the linked List
		//--------------------------------------------
#pragma once
	class Link
	{
	public:
		// constructor
		Link(int linkValue, Link * nextPtr);
		Link(const Link &);
		// data areas
		int value;
		Link * next;
	}; //end of class Link
public:
	// constructors
	List();
	List(const List&);
	~List();

	// operations
	void add(int value);
	int firstElement() const;
	bool search(const int &value) const;
	bool isEmpty() const;
	void removeFirst();
	void clear();
	void insert(int key);
	void remove(int key);
	int countInstance(int key);
	List operator=(List a);
	//List& operator=(List& a);

	friend istream& operator>>(istream& is, List& l);
	friend ostream& operator<<(ostream& os, List l);

protected:
	// data field
	Link* head;
};

//List.cpp
#include "List.h"
//#include "Link.h"
#include <iostream>

using namespace std;

//------------------------------------------------
// class Link implementation
//------------------------------------------------
List::Link::Link(int val, Link* nxt) :
	value(val), next(nxt) {}
List::Link::Link(const Link& source) :
	value(source.value), next(source.next) {}


//--------------------------------------------
 // class List implementation
 //--------------------------------------------
List::List() : head(NULL)
{
	// no further initialization
}
List::List(const List &l)
{
	Link *src, *trg;
	if (l.head == NULL)
		head = NULL;
	else
	{
		head = new Link((l.head)->value, NULL);
		src = l.head;
		trg = head;
		while (src->next != NULL)
		{
			trg->next = new Link
			((src->next)->value, NULL);
			src = src->next;
			trg = trg->next;
		}
	}
}
List::~List()
{
	clear();
}
void List::clear()
{
	// empty all elements from the List
	Link* next;
	for (Link * p = head; p != NULL; p = next)
	{
		// delete the element pointed to by p
		next = p->next;
		p->next = NULL;
		delete p;
	}
	// mark that the List contains no elements
	head = NULL;
}
bool List::isEmpty() const
{
	// test to see if the List is empty
		// List is empty if the pointer to the head
		// Link is null

	return head == NULL;
}
void List::add(int val)
{
	if (head == NULL)
	{
		head = new Link(val, NULL);
		return;
	}
	//Add a new value to the end of a Linked List
	Link* p = head;
	for (; p->next != NULL; p = p->next) {}

	p->next = new Link(val, NULL);

	if (head == NULL)
		throw "failed in memory allocation";
}
int List::firstElement() const
{
	// return first value in List
	if (isEmpty())
		throw "the List is empty, no first Element";
	return head->value;
}
bool List::search(const int &val) const
{
	// loop to test each element
	for (Link* p = head; p != NULL; p = p->next)
		if (val == p->value)
			return true;
	// not found
	return false;
}
void List::removeFirst()
{
	// make sure there is a first element
	if (isEmpty())
		throw "the List is empty, no Elements to remove";
	// save pointer to the removed node
	Link* p = head;
	// reassign the first node
	head = p->next;
	p->next = NULL;
	// recover memory used by the first element
	delete p;
}

List List::operator=(List a)
{
	Link* pointer = a.head;

	List copyList;

	while (pointer->next != NULL)
	{
		copyList.add(pointer->value);
		pointer = pointer->next;
	}

	copyList.add(pointer->value);

	return copyList;
}
/*
List& List::operator=(List& a)
{
	head = a.head;

	Link* pointer1 = a.head;

	Link* pointer2 = head;

	while (pointer1 != NULL)
	{
		pointer2->next = pointer1->next;

		pointer1 = pointer1->next;
		pointer2 = pointer2->next;
	}

	return *this;
}*/

istream& operator>>(istream& is, List& l)
{
	int temp, prev;
	while (true)
	{
		if (l.isEmpty())
		{
			is >> temp;
			l.add(temp);
			prev = temp;
		}
		else
		{
			is >> temp;

			if (temp <= prev)
				return is;

			l.add(temp);
			prev = temp;
		}
	}

	return is;
}

ostream& operator<<(ostream& os, List l)
{
	//Copy construct the list to a temp list
	List temp(l);

	//Run through the whole list
	while (!temp.isEmpty())
	{
		//print the first element and then remove it 
		os << temp.firstElement() << " ";
		temp.removeFirst();
	}

	return os;
}

//insert the element while keeping the list in a non desending order
void List::insert(int key)

{
	//create a duplicate of the head
	Link* pointer = head;

	//If the list is empty then key becomes the first element
	if (head == NULL)
	{
		head = new Link(key, NULL);
		return;
	}

	//If the list is not empty but the key is supposed to be the first element
	else if (key < head->value)
	{
		head = new Link(key, head);
		return;
	}

	//Go through the list
	while (key > pointer->value && pointer->next != NULL)
	{
		//Check if the key is supposed to be in between two elements, if so, insert it
		if (key <= pointer->next->value)
		{
			pointer->next = new Link(key, pointer->next);
			return;
		}

		pointer = pointer->next;
	}

	//If the key is supposed to be after the last element
	pointer->next = new Link(key, NULL);
}

//remove the link with the key without disrupting the rest of the List
void List::remove(int key)
{
	//If we need to remove the first element
	if (head->value == key)
	{
		//set the head to the next link and end function
		head = head->next;
		return;
	}

	//run through the list until you find the key
	Link* p = head;
	for (; p->next != NULL; p = p->next)
		if (key == p->next->value)
		{
			p->next = p->next->next;
			return;
		}

	//we reached the end of the list but couldn't find the key
	throw "value not found\n";
}

int List::countInstance(int key)
{
	int counter = 0;

	for (Link* p = head; p != NULL; p = p->next)
		if (key == p->value)
			counter++;

	return counter;
}

[kbw]

Your List() should implement move constructor and operator.

The compiler will want to use copy elision to optimise the return, and for that, you need move semantics.

If you don't implement move, copy will be used. And if you have a but, that's where it'll be.

EDIT:
Turns out you don't implement copy operator. That's asking for trouble. BTW, copy's signature is: List& operator=(const List &);. That other operator thing you defined is wrong and pointless.

[yem]

I tried making it a reference, but the main that was given didn't accept a reference.
It failed when it got to the following line in the main:
mergedList = merge(lst1, lst2);

[yem]

Also, I'm a little confused at what you're recommending to fix the issue. Are you saying that I should make a move constructor?

[kbw]

Give the copy constructor:

List::List(const List &other) : head(nullptr)
{
	if (!other.head)
		return;

	head = new Link(other.head->value);

	Link* src = other.head;
	Link* dst = head;
	while (src->next) {
		dst->next = new Link(src->next->value);

		src = src->next;
		trg = trg->next;
	}
}

The copy operator might be:

List& List::operator=(const List &other) {
	if (this != &other) {
		clear;

		head = new Link(other.head->value);

		Link* src = other.head;
		Link* dst = head;
		while (src->next) {
			dst->next = new Link(src->next->value);

			src = src->next;
			trg = trg->next;
		}
	}
	return *this;
}

Move moves the content of one object to the next:

List::List(List &&other) : head(other.head)
{
	other.head = nullptr;
}

And likewise:

List& operator=(List &&other)
{
	if (this != &other) {
		clear();

		head = other.head;
		other.head = nullptr;
	}
	return *this;
}

And finally, the link is just a data structure to hold pointer and data.

struct Link
{
	Link(int data, Link *nextPtr = nullptr) : value(data), next(nextPtr) {}
	int value;
	Link * next;
};

[yem]

Thanks!
I'm going to try that!

[dutch]

@kbw, move semantics are not needed for return value optimisation since RVO constructs the return value at the call site, so no move would be necessary. In fact, if you explicitly "move" the object in the return statement you get a compiler warning (clang):

rvo.cpp:16:12: warning: moving a local object in a return statement prevents copy elision

#include <utility>

class Object { };

Object func() {
    Object o;
    return std::move(o);
}

int main() {
    Object o = func();
}

[yem]

Thanks guys!
I got it working!
The issue seemed to be that I mistakenly copied the pointer instead of copying what was in the pointer when I wrote the operator= function.
As in: head=a.head;
Instead of: head = new Link (a.head->value, nullptr);
It works now and passed all test that my college website ran on it.
@kbw, I actually noticed the problem while comparing your code to mine side by side. Thanks for taking the time to write it out for me.
@dutch, what you're saying sounds about right to me, thanks