M.M M.M - 10 days ago 4
C++ Question

Can't access last element in Doubly Linked List when using end() in for loop

I am implementing a doubly linked List using iterators. The code works fine, except when using

iterator::end()
I am unable to access the last element in the list. For example the copy constructor cant access the last element(!!whenever I use
for(iterator it = lst.begin(); it != lst.end();++it)
). The problem looks simple but I cant get my head around it.

#pragma once

#include <iterator>
#include <initializer_list>
#include <iostream>


using namespace std;

template <typename T, class Allocator = std::allocator<T>>
class MyList {
private:
class Link {
public:
Link(const T& d, Link *n = NULL, Link *p = NULL) :next(n), prev(p), data(d) {}
~Link() { }

T data;
Link *next;
Link *prev;
};
Link *head ;
Link *tail ;
size_t s = 0; // ease things up

public:

class iterator:public std::iterator<std::bidirectional_iterator_tag, Link>
{
private:
Link *itr;
public:
iterator() :itr(nullptr) {}
iterator(Link* x) :itr(x) {}
// iterator& operator=(const iterator& i2) {itr = i2.itr;}
iterator(const iterator& i2) : itr(i2.itr) {}
iterator& operator++() {
itr=itr->next;
return *this;
}

iterator& operator--() {
itr = itr->prev;
return *this;
}


bool operator==(const iterator& rhs) {
return itr == rhs.itr;
}
bool operator!=(const iterator& rhs) {
return itr != rhs.itr;
}
T& operator*() {
return itr->data;
}
Link* getLink()const{
return itr;
}



};

MyList() {

head = nullptr;
tail= head;

s=0;

}

MyList(std::initializer_list<T> l)
:MyList(){
for(const auto& i : l){
push_back(i);}
}
//copy consructor
MyList( const MyList<T> &lst)
:MyList(){

for(iterator it = lst.begin(); it != lst.end(); ++it){
push_back(it.getLink()->data);
}
}

MyList& operator=(std::initializer_list<T> &lst) {
//clear any data before adding new one
while(head){
Link *tmp = head;
head = head->next;
delete tmp;
}
head = nullptr;
tail = nullptr;
s = 0;
for(auto i: lst){
push_back(i);
}
}

MyList& operator=(MyList<T> &lst) {
while(head){
Link *tmp = head;
head = head->next;
delete tmp;
}
head = nullptr;
tail = nullptr;
s = 0;
for(iterator it = lst.begin(); it != lst.end();++it) {push_back(it.getLink()->data);}
}




~MyList() {
Link* temp = head;
while (temp != nullptr)
{
temp = temp->next;
delete(head);
head = temp;
}
}

iterator begin() const{
iterator i(this->head);
return i;
}

iterator end() const{

iterator return{tail};

}

void push_back(const T& t) {

Link* newnode = new Link(t);
if (empty()) {
head = newnode;
tail = head;
}
else {
tail->next = newnode;
newnode->prev = tail;
tail = newnode;
}
s++;
}
std::size_t size() const {
return s;
}
bool empty() const {
return !(this->size());
}
};


This is the main.cpp I am testing my code, you can see in () when is the code working and when its failing.

//test default constructor(works!!!)

std::cout << "Testing default constructor"<< std::endl;
MyList<int> a{};
std::cout << "a should be empty: " << (a.empty() ? string("and it is!") : string("but it is not!")) << std::endl;

// push_back two elements(works!!!)
std::cout << "Testing push_back"<< std::endl;
a.push_back(1);
a.push_back(2);
std::cout << "a should be 1,2, and is: " << a << std::endl;




// test initializer list constructor(works!!!!)

std::cout << "Testing initializer list constructor"<< std::endl;
MyList<int> b{1, 2, 3, 4};
std::cout << "b should be 1,2,3,4, and is: " << b << std::endl;


//test copy constructor(doesnt work!! Misses the last element)

std::cout << "Testing copy constructor"<< std::endl;
MyList<int> c(b);
std::cout << "c should be " << b << " and is: " << c << std::endl;

MyList<int> ml{1,2,3,4,5,6};

// (doesnt work!! misss the last element)

for(const int& elem : ml)
std::cout << elem << std::endl;

Answer

This is because the standard convention in C++ is that end() points not to the last element, but to the next nonexsitent would-be element after the last.

http://www.cplusplus.com/reference/list/list/end/

In your implementation, iterator end() returns an actual last element which is obviously skipped in the it != lst.end() condition in the for loop:

for(iterator it = lst.begin(); it != lst.end();++it)