I have a List class which uses two objects: Element & Iterator
I considered making Element & Iterator classes but decided on structs.
template <class T>
struct Element
template <class T>
struct Iterator
template <typename T>
class List {
public:
typedef Iterator<T> iterator;
private:
};
Which allows a List iterator as you might expect:
List<int> list;
List<int>::iterator iter = list.begin();
template <typename T>
class List {
public:
template <class T>
struct Element
template <class T>
struct Iterator
private:
};
However having to include the second <> when creating iterator is a little less elegant & structs are public:
List<int> list;
List<int>::Iterator<int> iter = list.begin();
template <class T>
class Iterator;
template <typename T>
class List {
public:
typedef Iterator<T> iterator;
private:
template <class T>
struct Element
template <class T>
struct Iterator
};
.
List<int> list;
List<int>::iterator iter list.begin();
Error 1 error C2079: 'begin' uses undefined class 'Iterator<T>' main.cpp 216
How do I make structs private, allow public access to Iterator & keep the List::iterator syntax ?
eg List::iterator iter list.begin();
note: Iterator depends on Element
code:
#ifndef GUARD_List_h
#define GUARD_List_h
template <class T>
struct Element {
Element() : prev(nullptr), next(nullptr), data(), t_flag(" ") {}
Element<T>* prev;
Element<T>* next;
T data;
int elem_ID;
std::string t_flag;
};
template <class T>
struct Iterator {
Iterator(Element<T>* e = nullptr) : elem(e) {}
T& operator*(void) const {
if (elem->t_flag == "sentinel"){ std::cerr << "No Element to De-Reference - End of List Reached"; }
return elem->data;
}
T& operator++(void) { // ++prefix
elem = elem->next;
return elem->data;
}
T operator++(const int) { // postfix++
elem = elem->next;
return elem->prev->data;
}
T& operator--(const int) { // --prefix
elem = elem->prev;
return elem->data;
}
T operator--(void) { // postfix--
elem = elem->prev;
return elem->next->data;
}
Iterator<T>& operator+(const int val) {
for (int i = 0; i < val; i++){
elem = elem->next;
}
return *this;
}
Iterator<T>& operator-(const int val) {
for (int i = 0; i < val; i++){
elem = elem->prev;
}
return *this;
}
bool operator!=(const Iterator<T>& rhs) const {
return elem->elem_ID != rhs.elem->elem_ID;
}
bool operator==(const Iterator<T>& rhs) const {
return elem->elem_ID == rhs.elem->elem_ID;
}
bool operator>(const Iterator<T>& rhs) const {
return elem->elem_ID > rhs.elem->elem_ID;
}
bool operator<(const Iterator<T>& rhs) const {
return elem->elem_ID < rhs.elem->elem_ID;
}
bool operator>=(const Iterator<T>& rhs) const {
return elem->elem_ID >= rhs.elem->elem_ID;
}
bool operator<=(const Iterator<T>& rhs) const {
return elem->elem_ID <= rhs.elem->elem_ID;
}
Element<T>* elem;
};
template <typename T>
class List {
public:
List() : sentinel(new Element<T>), Element_count(0) {
sentinel->t_flag = "sentinel";
// double link: sentinel to itself
sentinel->next = sentinel;
sentinel->prev = sentinel;
}
virtual ~List() {
Element<T>* index = sentinel->next;
Element<T>* index_next = sentinel->next->next;
while (index->t_flag != "sentinel"){
delete index;
index = index_next;
index_next = index_next->next;
}
delete sentinel;
}
typedef Iterator<T> iterator;
Iterator<T> begin(void) const {
Iterator<T> it(sentinel->next);
return it;
}
Iterator<T> end(void) const {
Iterator<T> it(sentinel);
return it;
}
void push_back(const T val) {
Element<T>* elem = new Element<T>; // create Element<T> object
elem->data = val; // set Element<T> data
sentinel->prev->next = elem; // link: end of List to Element object
elem->prev = sentinel->prev; // link: Element object to end of List
elem->next = sentinel; // link: new end of List to sentinel
sentinel->prev = elem; // link: sentinel to new end of List
elem->elem_ID = Element_count++; // update: Element_count on grow
}
T at(const size_t pos) const {
return get_Element(pos)->data;
}
void del(const size_t pos) const {
Element<T>* elem = get_Element(pos); // get: Element for deletion
elem->prev->next = elem->next; // rejoin: double link
elem->next->prev = elem->prev; // rejoin: double link
delete elem;
Element_count--; // update: Element_count on shrink
}
void clear(void) {
Element<T>* index = sentinel->next;
Element<T>* index_next = sentinel->next->next;
while (index->t_flag != "sentinel"){
delete index;
index = index_next;
index_next = index_next->next;
}
// double link: sentinel to itself
sentinel->next = sentinel;
sentinel->prev = sentinel;
Element_count = 0;
}
size_t size(void) const {
return Element_count;
}
bool empty(void) const {
if (Element_count == 0){ return true; }
else { return false; }
}
private:
Element<T>* sentinel; // List sentinel
size_t Element_count; // List size
Element<T>* get_Element(const size_t pos) const {
if (empty()) {
std::cerr << "No Element - Empty List";
throw;
}
if (pos < 0 || pos >= Element_count){
std::cerr << "No Element - Out of Range";
throw;
}
Iterator<T> it;
if ((Element_count / 2) > pos) { // Determine efficent direction ?
it = begin()+1;
while ( it.elem->elem_ID != pos ){ it++; }
}
else {
it = end()-1;
while ( it.elem->elem_ID != pos ){ it--; }
}
return it.elem;
}
};
#endif
As far as "elegance" is concerned, redundant typename declarations seem to be the biggest issue:
If you have a nested class or struct, you don't need to templetize it; it is already bound to the templetized typename T declaration.
So:
template <typename T>
class List {
public:
struct Element;
struct Iterator;
private:
};
Allows you to do:
List<int> x;
List<int>::iterator iter ( x.begin() );
Since Iterator is being returned in a public method, it cannot be marked private. Element, on the other hand, is purely an implementation detail and can be marked private. You need to make sure that it is declared before any method that uses it or is simply forward declared.
template<typename T>
class List {
private:
struct Element; // or struct Element { <impl> };
public:
struct Iterator { < impl > };
private:
};