#ifndef LIST_H_
#define LIST_H_
template<typename Elem>
class Link
{
public:
Link *prev;
Link *succ;
Elem val;
};
template<typename Elem>
class list
// representation and implementation details
{
public:
using size_type = unsignedlong;
using value_type = Elem;
class iterator;
class const_iterator;
list(const Elem &v)
: first{ nullptr }, last{ nullptr }
{
Link<Elem> *new_node = new Link<Elem>;
new_node->prev = nullptr;
new_node->succ = last;
new_node->val = v;
first = new_node;
last = first;
}
list()
: first{ nullptr }, last{ nullptr } { }
~list()
{
iterator iter = end();
while (iter != begin())
{
delete iter.current_link();
--iter;
}
}
iterator begin() { return iterator(first); }
iterator end() { return iterator(last); }
const_iterator begin() const { return iterator(first); }
const_iterator end() const { return iterator(last); }
size_type size();
iterator insert(iterator p, const Elem &v); // insert v into list after p
iterator erase(iterator p); // remove p from list
void push_back(const Elem &v); // insert v at end
void push_front(const Elem &v); // insert v at front
void pop_front(); // remove the first element
void pop_back(); // remove the last element
Elem &front() { return *first; } // the first element
Elem &back() { return *last; } // the last element
private:
Link<Elem> *first;
Link<Elem> *last;
};
#endif
// requires Element<Elem>() (§19.3.3)
template<typename Elem>
class list<Elem>::iterator
{
Link<Elem> *curr; // current link
public:
iterator(Link<Elem> *p)
: curr{ p } { }
iterator &operator++() { curr = curr->succ; return *this; } // forward
iterator &operator--() { curr = curr->prev; return *this; } // backword
Elem &operator*() { return curr->val; }
booloperator==(const iterator &b) { return curr == b.curr; }
booloperator!=(const iterator &b) { return curr != b.curr; }
Link<Elem> *current_link() { return curr; }
};
template<typename Elem>
typename list<Elem>::iterator list<Elem>::insert(typename list<Elem>::iterator p, const Elem &v)
{
Link<Elem> *new_node = new Link<Elem>;
new_node->val = v;
new_node->prev = nullptr;
new_node->succ = nullptr;
if (new_node)
{
if (first == last)
{
first = new_node;
return iterator(new_node);
}
elseif (!p.current_link()->prev && p.current_link()->succ)
{
push_front(new_node);
return iterator(new_node);
}
elseif (p.current_link()->prev && p.current_link()->succ)
{
new_node->prev = p.current_link();
p.current_link()->succ->prev = new_node;
new_node->succ = p.current_link()->succ;
p.current_link()->succ = new_node;
return iterator(new_node);
}
elseif (!p.current_link()->succ && p.current_link()->prev)
{
push_back(new_node);
return iterator(new_node);
}
}
return p;
}
template<typename Elem>
typename list<Elem>::iterator list<Elem>::erase(typename list<Elem>::iterator p)
{
if (p.current_link())
{
if (p.current_link->succ)
{
p.current_link()->succ->prev = p.current_link()->prev;
}
if (p.current_link()->prev)
{
p.current_link()->prev->succ = p.current_link->succ;
}
delete p.current_link();
return iterator(p.current_link()->succ);
}
return p;
}
template<typename Elem>
typename list<Elem>::size_type list<Elem>::size()
{
typename iterator iter = begin();
typename size_type size = 0;
while (iter != end())
{
++iter;
++size;
}
return size;
}
template<typename Elem>
void list<Elem>::push_back(const Elem &v)
{
Link<Elem> *new_node = new Link<Elem>;
new_node->val = v;
new_node->prev = nullptr;
new_node->succ = nullptr;
if (first == last)
{
last = new_node;
first = last;
}
else
{
iterator trav = end();
trav.current_link()->succ = new_node;
new_node->prev = trav->current_link();
last = new_node;
}
}
template<typename Elem>
void list<Elem>::push_front(const Elem &v)
{
Link<Elem> *new_node = new Link<Elem>;
new_node->val = v;
new_node->prev = nullptr;
new_node->succ = nullptr;
if (first == last)
{
first = new_node;
last = first;
}
else
{
iterator trav = begin();
trav.current_link()->prev = new_node;
new_node->succ = trav.current_link();
first = new_node;
}
}
template<typename Elem>
void list<Elem>::pop_back()
{
iterator iter = end();
--iter;
last = last->prev;
iter.current_link()->succ = nullptr;
delete iter.current_link()->succ;
}
template<typename Elem>
void list<Elem>::pop_front()
{
iterator iter = begin();
++iter;
first = first->succ;
iter.current_link()->prev = nullptr;
delete iter.current_link()->prev;
}
template<typename Iter>
void advance(Iter &p, int n)
{
if (n > 0)
{
while (n > 0)
{
++p;
--n;
}
}
elseif (n < 0)
{
while (n < 0)
{
--p;
++n;
}
}
}
Some help with the deletion and the destructor would be good, too.
Edit: I just tried using my constructor. list::size() still returned 0. So either my constructor isn't working right or list::size() isn't. And there are leaks, so I need help on the destructor as well.
So either my constructor isn't working right or list::size() isn't.
In a typical standardish container, end will return an iterator to one-past-the-end. That is not the case in your code. start and end return values are identical for a one-item list. If this is intentional, then size is wrong. If it isn't, you need to maintain the proper class invariants.
"last" has to equal "end" for an empty list. I didn't do anything for the case when there's one element in the list.
So how do I return an iterator to one-past-the-end here? ++<iterator>; after getting to the last element?
What about the rest of the code, though? There are leaks, so that means there might be a problem in the destructor, right? Since it's trying to free the allocated memory. And how about erase()?
// Osman Zakir
// 11 / 11 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 20 Section 20.4: Linked Lists
#include "../../cust_std_lib_facilities.h"
#include <algorithm>
#include <iostream>
#include "list.h"
#include <vld.h>
template<typename Iter>
Iter high(Iter first, Iter last);
void f();
int main()
{
f();
keep_window_open();
}
template<typename Iter>
Iter high(Iter first, Iter last)
// return an iterator to the element in [first,last) that has the highest value
{
Iter high = first;
for (Iter p = first; p != last; ++p)
{
if (*high < *p)
{
high = p;
}
}
return high;
}
void f()
{
list<int> lst;
for (int x; std::cin >> x;)
{
lst.push_front(x);
}
list<int>::iterator p = high(lst.begin(), lst.end());
// did we reach the end?
if (p == lst.end())
{
std::cout << "The list is empty\n";
}
std::cout << "The highest value was " << *p << '\n';
}
On lines 47 - 50 when it checks if the list is empty, that check is coming out true. I also tried to check begin() == end(), and that too is coming out true.
Okay, I almost have it all figured out except for insert() and the destructor and maybe erase() and the other node-removing functions. This is the Gist link for my latest update code: https://gist.github.com/DragonOsman/87a1e9fba06d49cab9b5b556c7dd31eb . When I run the code in my debugger, I can see that insert() places the new node into the list. But the function high() still reports the node before it as the highest one (I input 100, 200, 300, 400, and 500, and then use insert() to insert 600 after position 5, but high still returns the iterator to position 5 as being the iterator to the highest value). What am I missing or what am I doing wrong?
By the way, in case anyone wonders why I'm decrementing iter twice in the destructor: With the first --iter, I'm trying to get to the previous node to delete the one after it. And with the second --iter, I move the loop itself along.
Actually, it turns out that erase() is fine except for the fact that it doesn't reset the head or tail as needed after deleting the node at the given position. So I need help in resetting the head or tail as needed when deleting the node.
I have yet to test pop_back() and pop_front(), but push_back() and push_front() are fine. I do need to test whether I can have advance() go backwards correctly when I give it a negative number as the second argument.
