C++ List & Template Help I need to write code for the following: A nested class
ID: 3679083 • Letter: C
Question
C++ List & Template Help
I need to write code for the following:
A nested class reverse_iterator that will enable reverse-traversal of a list.
A copy constructor and a function (not a member function)
template<typename T>
testCopyConst<T> (const List<T> list) { /* ... */}
to test it.
A constructor for initializer lists:
List(const initializer_list<T> &il) : List() { /* ... */ }
Member functions
void push_back(const T&t), void pop_back(), void clear()
(this last one will make the list empty).
An assignment operator (a.k.a copy assignment):
List &operator=(const List &other) { /* ... */ }
A function (not a member)
template <typename T>
void print(const List<T> *list) { /* ... */}
Similarly, write a reverse_print function
This is what I have so far:
#ifndef LIST_H
#define LIST_H
#include <iterator>
template<typename T>
class List
{
// List<...>::Node ... will not be allowed outside of List scope, so we make the Node data items public.
private:
class Node {
public:
Node(const T &i = T{}, Node *p = nullptr, Node *n = nullptr) : item(i), prev(p), next(n) {};
T item;
Node *prev, *next;
}; // class Node
public:
// We derive iterator from the STL iterator class to be able to use existing STL algorithms.
class iterator : public std::iterator <std::input_iterator_tag, T> {
public:
// Needed for conversion Node* --> iterator
iterator(Node *p) : current{ p } {}
T &operator*() {
return current->item;
}
// Prefix ++
iterator &operator++() {
current = current->next;
return *this;
}
// Prefix --
iterator &operator--() {
current = current->prev;
return *this;
}
bool operator==(const iterator &other) const {
return current == other.current;
}
bool operator!=(const iterator &other) const {
return !(*this == other);
}
Node *getCurrent() {
return current;
}
private:
Node *current;
}; // class iterator
List() : head(new Node), theSize(0) {
head->next = head;
head->prev = head;
}
~List() {
clear();
delete head;
}
iterator begin() const {
return{ head->next };
}
iterator end() const {
return{ head };
}
void push_back(const T &t) {
insert(end(), t);
}
void pop_back() {
erase(--end());
}
// Insert just before the node pointed to by current.
iterator insert(iterator it, const T &t) {
Node *p = it.getCurrent();
theSize++;
Node *pNewNode = new Node{ t, p->prev, p };
p->prev->next = pNewNode;
p->prev = pNewNode;
return pNewNode;
}
// Returns an iterator to the item following the one erased
iterator erase(iterator it) {
Node *p = it.getCurrent();
if (p == head)
return end();
p->prev->next = p->next;
p->next->prev = p->prev;
// Suggestion by S. Baijoo
++it;
delete p;
theSize--;
return it;
}
void clear() {
while (!empty())
erase(begin());
}
bool empty() {
return theSize == 0;
}
private:
Node *head;
int theSize;
};
#endif
Explanation / Answer
#ifndef LIST_H
#define LIST_H
#include <iostream>
using namespace std;
template<typename T>
class List{
private:
class Node {
public:
T item;
Node* prev;
Node* next;
};
public:
Node* current;
List(){
current = NULL;
}
void insert(T v){
Node* temp = new Node(v);
temp->prev = current;
temp->next = NULL;
current = temp;
};
void reverse_traversal(Node* node){
if (node == NULL){
cout << endl;
return;
}
reverse_traversal(node->next);
cout << node->value << " ";
}
};
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.