Thread: implementing iterator in copy ctor

Originally Posted by anon

You should change the end () method, to make it more efficient and not crash with empty lists

Code:

iterator end() const { return iterator(0); };

I also suspect that if you only allow readonly access through the iterator, it should be called const_iterator more properly.

Of coruse, agree on both accounts - although I suppose there's no reason why this design couldn't allow access through the iterators - I just didn't implement that. I just wanted to see if I could implement something that made use of iterators.

--
Mats

Code:

iterator(Node* n = 0) : curr(n) {}

says that "iterator is constructed using a node n, which has a default value of 0".
So we can do:
iterator i; // curr = 0;
or
iterator i(43); // curr = 43 [ignoring that the type isn't a Node * for now].

So, when we do

Code:

iterator begin() const {return iterator(head);}

the iterator is constructed with the value of head, not with zero.

--
Mats

Code:

template <typename T> void List<T>::display(){

for(mlist<int>::iterator i = this->begin(); i != this->end(); i++) {
			std::cout << "node = " << *i << std::endl;
		}
}

Some selective replacements will probably make it work. The red bit is quite obviously from my code and should most likely be "List<T>" instead.

since *i (in my case) returns an object of type T, you also need to have operator<<(ostream, T) [not that you would have to be responsible for writing that, but it needs to exist somewhere].

Edit: And it would probably work just as well without the "this->" because that is the default for any function within the class.

--
Mats

Originally Posted by sh3rpa

another thing i'd like to add, and i don't understand why, but moving the private node before the public interface, cleared up some of the errors i was getting like:


SOME_ERROR: cannot declare someFunc() of type Node with no type

Yes, you need to declare that the class by name of Node exists before you can say "this returns something of type Node".

--
Mats

Sherpa sent a PM asking how I would implement pop_back() and pop_front(), so I had to do that then...

This is the additional code to what I posted earlier:

Code:

// in class declaration:
	void pop_back();
	void pop_front();
...
// And here's the implementation.
template <typename T>
void mlist<T>::pop_back()
{
	Node *curr(head);
	Node *prev(0);

	while (curr != tail) {
      prev = curr;
	  curr = curr->next;
	}
	if (prev) {
		delete prev->next;
		prev->next = 0;
		tail = prev;
	} else {
		head = tail = 0;
	}
}

template <typename T>
void mlist<T>::pop_front()
{
	if (head) {
		Node *temp(head);
		head = head->next;
		delete temp;
		if (!head) tail = 0;
	}
}

As you see, the pop_back() is rather ugly with a big while-loop, since I only implemented a single-linked list, I can't use the tail to find the previous node, I have to walk all the way from the head to the end of the list. But it's an implementation. If it's a common operation to remove data from the back of the list, it's obviously a better idea to make the list double-linked [but that also makes the entire implementation more complex, and I wanted something that was trivial to implement - more code just makes it harder to follow].

--
Mats

In a singly linked list, you usually wouldn't implement pop_back at all, just as your iterators are not bidirectional.

Originally Posted by CornedBee

In a singly linked list, you usually wouldn't implement pop_back at all, just as your iterators are not bidirectional.

Yes. But if someone asks you "how do I implement this", it's not a good answer to say "well, I wouldn't" - or maybe it is, because it certainly wouldn't be a good idea to use this method if there are thousands or millions of entries in the linked list - very bad performance indeed.

--
Mats