A strange error with definition and declaration of a member function

[tomy12]

Hello,

Please take a look at this code. I'm going to make Mylist class as an STL list:

#include <std_lib_facilities_4.h>
using namespace std;

template <class Elem> 
class Link {

public:
	Link* prev;
	Link* succ;
	Elem val;
};

//***************************************

template<class Elem> 
class Mylist {

 public:
	class iterator;

	iterator begin();  // iterator to the first element
	iterator end();  // iterator to one beyond the last element

	iterator insert(iterator p, const Elem& v);  // insert v into the list after p
	iterator erase(iterator p);  // remove p from the list

	void puch_back(const Elem& v);  // insert v at end
	void push_front(const Elem& v); // insert v at front
	void pop_front();  // remove the first element
	void pop_back();  // remove the last element

	Elem& front();  // the first element
	Elem& back();  // the last element
};

//*****************************

int main()
{

	system("pause");
	return 0;
}

//*****************************************

template<class Elem> class Mylist<Elem>::iterator {
	Link<Elem>* curr;

public:
	iterator(Link* p) : curr(p) { }

	iterator& operator++() { curr = curr->succ; return *this; } // forward
	iterator& operator--() { curr = curr->prev; return *this; } // backward

	Elem& operator*() { return curr->val; } // get value (dereference)

	bool operator==(const iterator& b) const { return curr == b.curr; }
	bool operator!=(const iterator& b) const { return curr != b.curr; }
};

//****************************************************************************

template<class Elem>
iterator Mylist<Elem>::begin()
{
	
}

//****************************************

template<class Elem>
iterator Mylist<Elem>::end()
{
	
}

//*****************************************

template<class Elem>
iterator Mylist<Elem>::insert(iterator p, const Elem & v)
{
	
}

//*****************************************

template<class Elem>
iterator Mylist<Elem>::erase(iterator p)
{

}

//**************************************

template<class Elem>
void Mylist<Elem>::puch_back(const Elem & v)
{

}

//******************************************

template<class Elem>
void Mylist<Elem>::push_front(const Elem & v)
{

}

//************************************

template<class Elem>
void Mylist<Elem>::pop_front()
{

}

//*********************************

template<class Elem>
void Mylist<Elem>::pop_back()
{

}

//*************************************

template<class Elem>
Elem & Mylist<Elem>::front()
{
	// TODO: insert return statement here
}

//************************************

template<class Elem>
Elem & Mylist<Elem>::back()
{
	// TODO: insert return statement here
}

I get 5 errors:

Some of of them:

Severity Code Description Project File Line Suppression State
Error C2955 'std::iterator': use of class template requires template argument list

Severity Code Description Project File Line Suppression State
Error C2244 'Mylist<Elem>::begin': unable to match function definition to an existing declaration

Why do I get these errors please?

[VictorN]

...
Severity Code Description Project File Line Suppression State
Error C2955 'std::iterator': use of class template requires template argument list

Severity Code Description Project File Line Suppression State
Error C2244 'Mylist<Elem>::begin': unable to match function definition to an existing declaration

Why do I get these errors please?

Did you try to search for some these errors with Google?

[tomy12]

I saw some of the threads but couldn't find any error in my code.

[2kaud]

 public:
	class iterator;

Why are you forward declaring the STL class iterator here?

PS When you use the class iterator, you need to specify a template parameter (eg input_iterator_tag). See http://www.cplusplus.com/reference/iterator/iterator/

[tomy12]

That forward declaration is part of a code in the book Programming Principles And Practice Using C++ which as an exercise wants us to compete it. (exercise 12)

It seems that iterator is a built-in type and has some arguments that at least two of them should be filled when using it. If iterator is such way, why does the author have declared a class named iterator!?
Seems odd for me!

[2kaud]

OK. I've looked at my copy of the book I see what's he doing (I'm not a fan of this book). He's not using the c++ STL iterator class. He's defining his own class called iterator. Naughty! That's why he's forward declaring class iterator in class Mylist - as the definition of his class iterator comes later. Doh!!

template<class Elem>
iterator Mylist<Elem>::begin()
{
	
}

So here there's going to be the code for begin(). It returns a type iterator - but iterator is a member of class Mylist. So you need to use scope resolution to specify where is iterator.

template<class Elem>
Mylist<Elem>::iterator Mylist<Elem>::begin()
{

}

However, if you try to compile this you get an error 'dependent name is not a type'. That's because the compiler needs to be told that this is actually a type! So you need

template<class Elem>
typename Mylist<Elem>::iterator Mylist<Elem>::begin()
{

}

which does compile - and the same for the other functions that return iterator.

[tomy12]

Yeah naughty!!

>> So here there's going to be the code for begin(). It returns a type iterator - but iterator is a member of class Mylist. So you need to use scope resolution to specify where is iterator.

Why do we need to use scope resolution while both begin() and iterator are of the same area and know each other?

>> an error 'dependent name is not a type'. That's because the compiler needs to be told that this is actually a type! So you need

Why doesn't the compiler identify this?! It's a little odd because we have been taught that classes are user defined types!

You got the issue properly. Bravo 2Kuad (or better if I knew your real name!)

[2kaud]

Why do we need to use scope resolution while both begin() and iterator are of the same area and know each other?

They know each other within the definition of class Mylist. Within the body of begin() they know. But the function return type is outside of the body...

Why doesn't the compiler identify this?

There's probably a god explanation somewhere in the c++ standard documentation. Rule of thumb. If the compiler complains about "'xxx' dependent name is not a type" you'll probably need to use typename! Try leaving typename out and see.

See also http://en.cppreference.com/w/cpp/lan...dependent_name

[Larnaco]

They know each other within the definition of class Mylist. Within the body of begin() they know. But the function return type is outside of the body...



There's probably a god explanation somewhere in the c++ standard documentation. Rule of thumb. If the compiler complains about "'xxx' dependent name is not a type" you'll probably need to use typename! Try leaving typename out and see.

See also http://en.cppreference.com/w/cpp/lan...dependent_name

Thanks for that link

[tomy12]

Thank you.
As the exercise 12 says I should complete the code for the Mylist. It's specific list and not that complicated and massive like the STL::list. (Screenshots are above)

I exceeded a little and wrote the code below for the Mylist:

#include <std_lib_facilities_4.h>
using namespace std;

template<class Elem>
class Mylist {

private:
	int sz;

public:
	class Link;
	class Iterator;

	Mylist<Elem>() { 
		Link(0, 0, 0);
		sz = 0;
		first = 0;
		last = 0;
	}

	int size() { return sz; }

	Iterator begin();  // iterator to the first element
	Iterator end();  // iterator to one beyond the last element

	Iterator insert(Iterator p, const Elem& v);  // insert v into the list after p
	Iterator erase(Iterator p);  // remove p from the list

	void puch_back(const Elem& v);  // insert v at end
	void push_front(const Elem& v); // insert v at front
	void pop_front();  // remove the first element
	void pop_back();  // remove the last element

	Elem& front();  // the first element
	Elem& back();  // the last element

protected:
	Link* first;
	Link* last;
};

//*****************************

int main()
{
	Mylist<int> l1;
	cout << l1.size() << endl;
	l1.puch_back(12);
	l1.puch_back(15);

	for (auto p = l1.begin(); p != l1.end(); ++p)
	   cout << *p << ' ';
	cout << endl;

	system("pause");
	return 0;
}

//*****************************************

template<class Elem>
class Mylist<Elem>::Link {

public:
	Link(Elem v, Link* p = 0, Link* s = 0) : val(v), prev(p), succ(s) { }

private:
	Link* prev;
	Link* succ;
	Elem val;
};

//****************************************

template<class Elem>
class Mylist<Elem>::Iterator {

private:
  Link* curr;    

public:
	Iterator(Link* p) : curr(p) {  }


	Iterator& operator++() { curr = curr->succ; return *this; } // forward
	Iterator& operator--() { curr = curr->prev; return *this; } // backward

	Elem& operator*() { return curr->val; } // get value (dereference)

	bool operator==(const Iterator& b) const { return curr == b.curr; }
	bool operator!=(const Iterator& b) const { return curr != b.curr; }
};

//****************************************************************************

template<class Elem>
typename Mylist<Elem>::Iterator Mylist<Elem>::begin()
{
	Iterator I(first);
	return I;
}

//************************************

template<class Elem>
typename Mylist<Elem>::Iterator Mylist<Elem>::end()
{
	Iterator I(last + 1);
	return I;
}

//*************************************************************

template<class Elem>
typename Mylist<Elem>::Iterator Mylist<Elem>::insert(Iterator p, const Elem& v)
{
	return iterator();
}

//************************************************

template<class Elem>
typename Mylist<Elem>::Iterator Mylist<Elem>::erase(Iterator p)
{
	return iterator();
}

//*****************************

template<class Elem>
void Mylist<Elem>::puch_back(const Elem& v)
{
	Link* l = new Link(v,0,0);
	if (first == 0 && last == 0) {
		first = &l;
		last = &l;
	}
	else {

		l->prev = last;
		last->succ = l;
		last = l;
	}
	
}

//**************************************************

template<class Elem>
void Mylist<Elem>::push_front(const Elem& v)
{
}

//******************************

template<class Elem>
void Mylist<Elem>::pop_front()
{
}

//*********************************

template<class Elem>
void Mylist<Elem>::pop_back()
{
}

//************************************

template<class Elem>
Elem & Mylist<Elem>::front()
{
	// TODO: insert return statement here
}

//********************************

template<class Elem>
Elem & Mylist<Elem>::back()
{
	// TODO: insert return statement here
}

I get (as usual!) 5 errors! When I look at them logically, I see no clear issue. Would you please guide me on finding and solving them? All of them belong to the following part of the main() function:
for (auto p = l1.begin(); p != l1.end(); ++p)
cout << *p << ' ';


Severity Code Description Project File Line Suppression State
Error C2027 use of undefined type 'Mylist<int>::Iterator' 51

Severity Code Description Project File Line Suppression State
Error C2678 binary '!=': no operator found which takes a left-hand operand of type 'Mylist<int>::Iterator' (or there is no acceptable conversion) 51

Severity Code Description Project File Line Suppression State
Error C2675 unary '++': 'Mylist<int>::Iterator' does not define this operator or a conversion to a type acceptable to the predefined operator 51

Severity Code Description Project File Line Suppression State
Error C2100 illegal indirection 52


Severity Code Description Project File Line Suppression State
Error C2088 '<<': illegal for class 52

[2kaud]

Move main() to the end of the program. main() is using class Mylist which uses the incomplete iterator which isn't defined until after main(). Incomplete types (classes etc) have to be defined before they can be used as anything other than pointers.

Once you're done this you'll find that you still have a couple of unrelated compile errors which you should be able to sort out.

Once you get it to compile and run, you'll notice that you have a run-time problem. This is caused by how you initialise end(). You set it to point to the memory location one past last. However, in iterator ++ you set ++ to point to the next element. But the next element from last in a list is 0 - so you're trying to dereference 0 which causes the error.

[2kaud]

Also note that instead of setting pointers to 0 (and testing for 0), you should use nullptr. Also if the class variables are default defined then you don't need to initialise them in constructors.

protected:
	Link* first = nullptr;
	Link* last = nullptr;
...

private:
	Link* prev = nullptr;
	Link* succ = nullptr;
	Elem val {};
...
	Mylist<Elem>() {}
...

if (first == nullptr)

etc.

Also, you do know, don't you, that the code as posted has some serious errors - no destructors, no copy constructors etc Whilst Mylist needs a destructor as it uses dynamic memory (otherwise there is a memory leak), you can tell the compiler not to use the default copy constructor and copy assignment by

	Mylist(const Mylist&) = delete;
	Mylist& operator=(const Mylist&) = delete;

The default copy constructor/copy assignment do a shallow copy rather than the required deep copy with dynamic memory usage. With the =delete, if code attempts a copy constructor or copy assignment with Mylist, then the compiler generates an error.

PS

Mylist<Elem>() { 
		Link(0, 0, 0);

Link() doesn't do what you think it does. This creates a temporary initialised instance of class Link which as it's not used is immediately deleted!

Also, size(), begin() and end() should be const as they don't change the values of he member variables.

Once you have begin() and end() working properly, then in main() you can also have

	for (const auto& l : l1)
		cout << l << ' ';

[tomy12]

Move main() to the end of the program.

2kaud: When I saw this part of your message I went for manipulating the code at once. :-)
And get the code to run successfully with this part of code in main():

int main()
{
	Mylist<int> l1;
	cout << l1.size() << endl;
	l1.puch_back(12);
	l1.puch_back(15);
	l1.puch_back(30);
	cout << l1.size() << endl;

	for (auto p = l1.begin(); p != l1.end(); ++p)
		cout << *p << ' ';
	cout << endl;

	system("pause");
	return 0;
}

Then I read the rest of the message. It's OK now.
Then read your next post here and:

1- I changed the zeros to nullptr for all pointers pointing to zero. And simply removed

Link(0, 0, 0);

2- Created a copy constructor as follows and it works fine:

Mylist& operator=(const Mylist& N) {  // Copy constructor
		this->sz = N.sz;
		this->first = N.first;
		this->last = N.last;
	}

3- I also tried to write a destructor as below:

~Mylist<Elem>() { delete first; delete last; }

But 2kaud, I didn't make those functions at the first because the exercise hadn't wanted us to provide that specific (non-complete) list with those, but your comments, as always pushed me one further step to front.

4- And the functions that you mentioned that should be const like for example:

int size() { return sz; }

It in its body doesn't make any manipulations/changes to sz, so why do we need to define it this way?
int size() const { return sz; }

Thanks for all of your comments.

[2kaud]

2. Your copy constructor is not correct. You are doing a shallow copy (like the default constructor) when you should be doing a deep constructor (you need to create a new list and copy the elements from the original). With a shallow copy, you copy the memory pointers rather than allocating new memory. Your copy constructor may seem to work but it is fatally flawed.

3. The destructor is not correct. You have to delete each node of the list, not just the first and the last. In your version the memory allocated for the nodes between first and last won't be deleted and what if first equals last?

4. Precisely because it doesn't make changes. Member functions that don't change member variables should be defined as const. See http://www.learncpp.com/cpp-tutorial...ber-functions/

[2kaud]

I don't know what your current code is like, but based upon the code in post #10, for interest this is the code I used that compiled and ran.

//#include <std_lib_facilities_4.h>
#include <iostream>
using namespace std;

template<class Elem>
class Mylist {

public:
	class Iterator;

	Mylist<Elem>() {}
	~Mylist<Elem>();

	Mylist(const Mylist&) = delete;
	Mylist& operator=(const Mylist&) = delete;

	size_t size() const;

	Iterator begin() const;  // iterator to the first element
	Iterator end() const;  // iterator to one beyond the last element

	Iterator insert(const Iterator& p, const Elem& v);  // insert v into the list after p
	Iterator erase(const Iterator& p);  // remove p from the list

	void push_back(const Elem& v);  // insert v at end
	void push_front(const Elem& v); // insert v at front

	void pop_front();  // remove the first element
	void pop_back();  // remove the last element

	Elem& front() const;  // the first element
	Elem& back() const;  // the last element

private:
	struct Link;

	Link* first = nullptr;
	Link* last = nullptr;

	size_t sz = 0;
};

//****************************************

template<class Elem>
struct Mylist<Elem>::Link {
	Link(Elem v, Link* p = nullptr, Link* s = nullptr) : val(v), prev(p), succ(s) {}

	Link* prev = nullptr;
	Link* succ = nullptr;

	Elem val {};
};

//****************************************

template<class Elem>
class Mylist<Elem>::Iterator {

public:
	Iterator(Link* p = nullptr) : curr(p) {}

	Iterator& operator++() {curr = curr->succ; return *this; }
	Iterator& operator--() {curr = curr->prev; return *this; }
	Elem& operator*() const {return curr->val; }
	bool operator==(const Iterator& b) const {return curr == b.curr; }
	bool operator!=(const Iterator& b) const {return !operator==(b); }

private:
	Link* curr = nullptr;
};

//****************************************

template<class Elem>
Mylist<Elem>::~Mylist<Elem>() {
	for (auto e = first; e != nullptr; ) {
		auto d = e;
		e = e->succ;
		delete d;
	}
}

//****************************************

template<class Elem>
size_t Mylist<Elem>::size() const {
	return sz;
}

//****************************************

template<class Elem>
typename Mylist<Elem>::Iterator Mylist<Elem>::begin() const
{
	return Iterator(first);
}

//****************************************

template<class Elem>
typename Mylist<Elem>::Iterator Mylist<Elem>::end() const
{
	return Iterator();
}

//****************************************

template<class Elem>
typename Mylist<Elem>::Iterator Mylist<Elem>::insert(const Iterator& p, const Elem& v)
{
	return Iterator();
}

//****************************************

template<class Elem>
typename Mylist<Elem>::Iterator Mylist<Elem>::erase(const Iterator& p)
{
	return Iterator();
}

//*****************************************

template<class Elem>
void Mylist<Elem>::push_back(const Elem& v)
{
	last = (first == nullptr) ? (first = new Link(v)) : (last->succ = new Link(v, last));
	++sz;
}

//*****************************************

template<class Elem>
void Mylist<Elem>::push_front(const Elem& v)
{
	first = (last == nullptr) ? (last = new Link(v)) : (first->prev = new Link(v, nullptr, first));
	++sz;
}

//*****************************************

template<class Elem>
void Mylist<Elem>::pop_front()
{
}

//*****************************************

template<class Elem>
void Mylist<Elem>::pop_back()
{
}

//*****************************************

template<class Elem>
Elem& Mylist<Elem>::front() const
{
	return first->val;
}

//*****************************************

template<class Elem>
Elem& Mylist<Elem>::back() const
{
	return last->val;
}


int main()
{
	Mylist<int> l1;

	l1.push_back(12);
	l1.push_back(15);

	l1.push_front(23);
	l1.push_front(45);

	for (const auto& l : l1)
		cout << l << ' ';

	cout << endl;

	cout << "front: " << l1.front() << endl;
	cout << "back: " << l1.back() << endl;

	system("pause");
	return 0;
}