I'm using a doubly linked list container I've written as the working example. The textbook I'm using is from 2001, so feel free to point out where later versions of the C++ standard should be used instead.
Notes:
List::iterator
functionality mimics pointer arithmetic.- Unlike most containers, list beginning is marked by a specific element which holds no data, to make reverse iteration easier: [begins][data][data][data][data][data][ends]
- De-referencing
begin
/end
will deference the closest data element, so*begin
= data@0 &*end
= data@end-1. - The
List
container plays more elegantly with basic loops (seemain
).
list.h:
#ifndef GUARD_List_h
#define GUARD_List_h
template <class T>
struct element {
element<T> *prev = NULL;
element<T> *next = NULL;
T data = NULL;
int elem_ID = NULL;
char t_flag = NULL;
};
template <class T>
struct elem_iter {
elem_iter() { target = NULL; }
elem_iter(element<T>* e) { target = e; }
element<T>* target;
element<T>* elem_iter::operator++(void) {
if (target->next->t_flag == 'e'){
return NULL;
}
target = target->next;
return target;
}
element<T>* elem_iter::operator--(void){
if (target->prev->t_flag == 'b'){
return NULL;
}
target = target->prev;
return target;
}
T elem_iter::operator*(void){
if (target->t_flag == 'e'){
target = target->prev;
return target->data;
}
else if (target->t_flag == 'b'){
target = target->next;
return target->data;
}
return target->data;
}
bool elem_iter::operator!=(elem_iter& rhs){
return (rhs.target != this->target);
}
bool elem_iter::operator>=(elem_iter& rhs){
return (this->target->elem_ID >= rhs.target->elem_ID);
}
bool elem_iter::operator<=(elem_iter& rhs){
return (this->target->elem_ID <= rhs.target->elem_ID);
}
bool elem_iter::operator>(elem_iter& rhs){
return (this->target->elem_ID > rhs.target->elem_ID);
}
bool elem_iter::operator<(elem_iter& rhs){
return (this->target->elem_ID < rhs.target->elem_ID);
}
elem_iter elem_iter::operator+(int val){
for (int i = 0; i < val; i++){
this->target = this->target->next;
}
return *this;
}
elem_iter elem_iter::operator-(int val){
for (int i = 0; i < val; i++){
this->target = this->target->prev;
}
return *this;
}
};
template <typename T>
class List {
public:
List::List(void) {
element_count = 0;
// create begin
element<T>* b = new element <T>;
b->t_flag = 'b';
begins = b;
// create end
element<T>* e = new element <T>;
e->t_flag = 'e';
ends = e;
// double link: begins & ends
begins->next = ends;
ends->prev = begins;
element_count = 0;
}
typedef elem_iter<T> iterator;
iterator begin(void) {
iterator it(begins);
return it;
}
iterator end(void) {
iterator it(ends);
return it;
}
void push_back(T val) {
element<T>* elem = new element<T>; // create: new-elem
elem->data = val; // set data
elem->elem_ID = element_count++; // set ID
elem->prev = ends->prev; // link: new-elem to last-data-elem
ends->prev->next = elem; // link: last-data-elem to new-element
elem->next = ends; // link: new-elem to List-end
ends->prev = elem; // link: List-end to new-elem
ends->elem_ID = element_count; // update: ends-ID when List grows
}
T at(size_t pos) {
return get_element(pos)->data;
}
void del(size_t pos) {
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;
ends->elem_ID = (element_count--); // update: when List shrinks
}
void clear(void) {
element<T>* ep = begins->next;
element<T>* ep_next = ep->next;
while (ep->t_flag != 'e'){
delete ep;
ep = ep_next;
ep_next = ep->next;
}
begins->next = ends;
ends->prev = begins;
begins->data = NULL;
ends->elem_ID = NULL;
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>* begins; // List begins
element<T>* ends; // List ends
size_t element_count; // List size
element<T>* get_element(size_t pos) {
if (empty()) {
std::cerr << "No Element - Empty List";
throw;
}
if (pos < 0 || pos >= element_count){
std::cerr << "No Element - Out of Range";
throw;
}
iterator it;
// Determine the more efficent iteration direction(forward or reverse) ?
if ((element_count / 2) > pos) {
it = begin();
for (size_t i = 0; i <= pos; i++){
it++;
}
}
else {
it = end();
for (size_t i = size() - pos; i > 0; i--){
it--;
}
}
return it.target;
}
};
#endif
typedef List<int> container;
main.cpp:
#include <iostream>
#include <vector>
#include <list>
#include "list.h"
int main() {
container ls;
container::iterator begin = ls.begin();
container::iterator end = ls.end();
container::iterator iter = begin;
std::cout << "Attempt to retrieve data from empty list: ls.at(3)" << std::endl;
std::cout << "--------------------------------------------------" << std::endl;
//std::cout << ls.at(3) << std::endl << std::endl;
std::cout << "Test: growing list does not invalidate iter" << std::endl;
std::cout << "-------------------------------------------" << std::endl;
std::cout << "Empty list" << std::endl << std::endl;
std::cout << "begin addr: " << &begin << " " << std::endl;
std::cout << "begin t_flag: " << begin.target->t_flag << " " << std::endl;
std::cout << "end addr: " << &end << " " << std::endl;
std::cout << "end t_flag: " << end.target->t_flag << " " << std::endl;
std::cout << std::endl << "Add data to list: 33 " << std::endl << std::endl;
ls.push_back(33);
std::cout << "begin addr: " << &begin << " " << std::endl;
std::cout << "begin t_flag: " << begin.target->t_flag << " " << std::endl;
std::cout << "end addr: " << &end << " " << std::endl;
std::cout << "end t_flag: " << end.target->t_flag << " " << std::endl;
std::cout << std::endl << "Add data to list: 33 " << std::endl << std::endl;
ls.push_back(856);
std::cout << "begin addr: " << &begin << " " << std::endl;
std::cout << "begin t_flag: " << begin.target->t_flag << " " << std::endl;
std::cout << "end addr: " << &end << " " << std::endl;
std::cout << "end t_flag: " << end.target->t_flag << " " << std::endl << std::endl;
std::cout << "clear() " << std::endl << std::endl;
ls.clear();
std::cout << std::endl << std::endl;
std::cout << "Add data to list: 0 1 2 3 4 5 6 7 8 9" << std::endl;
std::cout << "-------------------------------------------------" << std::endl;
for (int i = 0; i != 10; i++){
ls.push_back(i);
}
std::cout << std::endl << std::endl;
std::cout << "data@ begin+4" << std::endl;
std::cout << "-------------" << std::endl;
std::cout << *(iter + 4) << std::endl;
std::cout << std::endl << std::endl;
std::cout << "data@ begin->end" << std::endl;
std::cout << "----------------" << std::endl;
iter = begin;
while (iter++){
std::cout << *iter << " ";
}
std::cout << std::endl << std::endl << std::endl;
std::cout << "data@ end->begin" << std::endl;
std::cout << "----------------" << std::endl;
iter = end;
while (iter--){
std::cout << *iter << " ";
}
std::cout << std::endl << std::endl << std::endl;
std::cout << "for/iter: begin->end" << std::endl;
std::cout << "----------------" << std::endl;
for (iter = begin; iter++;){
std::cout << *iter << " ";
}
std::cout << std::endl << std::endl << std::endl;
std::cout << "iter arith: +4 +1 -1" << std::endl;
std::cout << "--------------------" << std::endl;
iter = ls.begin();
iter = iter + 4;
std::cout << *iter << " ";
std::cout << *(iter + 1) << " ";
std::cout << *(iter - 1) << " ";
std::cout << std::endl << std::endl << std::endl;
std::cout << "data@: (0)(1)(2)(3)(4)(5)(6)(7)(8)(9)" << std::endl;
std::cout << "-------------------------------------" << std::endl;
for (int i = 0; i != 10; i++){
std::cout << ls.at(i) << " ";
}
ls.clear();
return 0;
}