###Comment on notes:
List::iterator functionality mimics pointer arithmetic.
If you call it an iterator then it really should.
But you should be careful. There are actually several classes of iterator. The pointer implements the Random Access Iterator. An iterator for a doubly linked list usually only implements Reversible Iterator. The difference is that Random Access Iterator can do i += 10 in O(1) while the reversible iterator does not need this functionality.
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]
Actually using sentinels (A special marker in the list) is a very common way of implementing a doubly linked list (it makes the implementation much easier because you don't need to worry about the empty list and NULL).
But just because you have a sentinel value internally you do not need to expose that to the user of your class (that is not common). Usually begin() would return the first value after the sentinel.
De-referencing begin/end will deference the closest data element, so *begin = data@0 & *end = data@end-1.
That's a strange behavior. Also it makes swapping your container with other peoples containers bothersome (as you have a change in expected behavior). You should definitely conform to the expected behavior (unless you have a very specific use case that only your class is good for and you document it thoroughly).
The List container plays more elegantly with basic loops...see main.
We will see about that.
A.... no it does not.
Because it does not do what people expect. If you stray from expected behavior then you confuse the maintainer. It may look very neat to you. But to experienced programmers it looks like you fucked up. Then we have to go and dig into the implementation to verify that it actually works as expected (thus wasting time for the maintainer which is probably not you (but does have an axe and your address)).
The classic loop looks like this:
for(auto loop = con.begin(); loop != con.end(); ++loop)
{
std::cout << *loop << "\n";
}
// With C++ 11 (or was it 14) it now looks like this:
for(auto const& item : con) // this works with any object
// that has begin() and end()
// methods that return iterators.
{
std::cout << item << "\n";
}
But even more often we use standard algorithms (they use iterators to perform actions on containers).
std::copy(con.begin(), con.end()
std::ostream_iterator<int>(std::cout, "\n"));
##Code Review ###struct element
This is am implmentation detail of your list.
So define the struct inside your List class (and make it private).
template <class T>
struct element {
element<T> *prev = NULL; // Correct but why not have a constructor
element<T> *next = NULL;
T data = NULL; // NOT correct.
int elem_ID = NULL; // NOT correct.
char t_flag = NULL;
};
NULL is supposed to be used for pointers only. It marks a pointer that points at nothing. The last three elements in your object are not pointers and thus assigning NULL makes no sense. It compiles because in C++03 NULL was usually the integer zero. In this case the NULL is being converted back to zero and assigned to these values. You will not be able to tell the difference between NULL and zero. In C++11 the nullptr was introduced. This is not convertible back to zero and thus will generate a compiler error when used above.
Also your type T may not be constructable with a NULL pointer (or zero). So this will generate compilation errors.
I would have done:
template <class T>
struct element {
element<T> *prev = nullptr;
element<T> *next = nullptr;
T data;
int elem_ID = 0;
char t_flag = '\0';
element(T const& copy)
: data(copy)
{}
// In C++11 we introduced the concept of moving data
// rather than copying it (as in C++03). This is as
// quick as copying and if the structure T is complicated
// then much faster. If the object T does not know how to
// move itself then it will use the copy above so it is
// also backwards compatible with old code.
element(T&& move)
: data(std::forward<T>(move))
{}
};
###struct List
Looks good at first glance. You need a couple of interface changes to make it standards compliant.
typedef elem_iter<T> iterator;
iterator begin(void);
iterator end(void);
One of the major important things in C++ (over C) is const correctness. It is very often that you see objects being passed around as const& (const references). This means you can read but not alter them. But it also means that your class must make available ways for your object to be read (via iterators). As a result I would also expect the following.
typedef elem_iter_const<T> const_iterator;
const_iterator begin() const;
const_iterator end() const;
Notice the extra const on the end of the function name. This is an indication that this call will not modify the object so the compiler will allow this method to be called when the object is const (ie actually const or being accessed via a const reference).
The iterator returned from these calls should also be slightly different from normal iterators in that they can read from the container but will not allow modification of the container.
Third thing to note is the use of void. This is uncommon in C++ (it means the same but is rarely used (best to not use it but not going to make any difference if you do)). Note this is different from the C meaning of void as a parameter.
###Sentential
Your use of sentenals is fine for simple types of T. But will not work for anything with a complex constructor. You should have a different object that does not have the T data load for your sentential.
Also most implementations only use a single sentential object. The pointers of the sentinel wrap around to point at itself. This way begin always points to the first element (or the sentinel if it is empty). While end always points at the sentinel. Then sentinel->next is the first element while sentinal->last is the last element (which could be itself if there are no elements).
If that was confusing I provide an example here.
http://codereview.stackexchange.com/a/28393/507
###elem_iter
It looks good (I have not read in detail).
But it is a bit more complex than it needs to be. If you change your implementation to use a single sentinel then your iterator becomes much simpler.
##Identifiers
Quick note on identifiers.
User defined types usually (and people could argue against this) have an initial uppercase letter. This makes it easy to identify user defined types over objects.
#If I was going to do it here is where I would start:
###Empty List
#############
/-># sentenal #<-
--#Prev Next#--/
#############
###One Element List
#############<-------------------------
# DATA # ############# |
/--#Prev Next#----------># sentenal # |
| #############<----------#Prev Next#--/
------------------------->#############
###Description:
The sentinel is always there. You also need to make the list circular. That way the first element is next from the sentinel and the last is element prev from the sentinel.
When you construct the end() iterator use the sentinel as it is one past the end.
When you construct the begin iterator use the sentinel->next. Note if the list is empty the the circula nature makes it the same as the end() iterator.
##Interface:
template<typename T>
class LList
{
// Define the `Element` internally
struct Element { /* STUFF */ };
// Just need one member (the end)
// Because we are using a sentenal first and last are
// one element away. So we can get to both ends by following
// a single pointer.
Element* sentenal;
std::size_t size; // keep track of size locally
public:
// constructors/destructors.
// Because we are a doing memory management we need to
// implement the rule of 3. Since we can do move semantics
// and it makes sense to extend this to the rule of 5.
LList(); // default constructor
LList(LList const& copy); // copy constructor
LList(LList&& move); // move constructor
~LList(); // destructor
LList& operator=(LList copy); // copy assignment (use copy and swap)
LList& operator=(LList&& move); // move assignment (use swap)
void swap(LList& rhs) noexcept; // swap (is no exception) but
// useful in so many ways.
void push_back(T const& value); // push back copy by value
void push_back(T&& value); // push back move value into container.
/* VERY Advanced but useful the new emplace back */
template<ARGS...>
void emplace_back(ARGS args...); // Use T's constructor
// Always want to test if a container is empty.
// Some methods are only valid if empty is not true.
bool empty() const;
bool size() const;
// Undefined behavior if empty()
// Access front or back members.
// But provide normal and const versions.
T& front();
T const& front() const;
T& back();
T const& back() const;
// Define an internal iterator.
// Use the `std::iterator` as a base for your iterator.
struct Iterator: public std::iterator<std::bidirectional_iterator_tag, T>
{ /* STUFF */ };
// Need to define types that
// are used by standard algorithms.
typedef STUFF_WITH Iterator iterator;
typedef STUFF_WITH Iterator const_iterator;
// The iterator interface.
iterator begin();
const_iterator begin() const;
const_iterator cbegin() const;
iterator end();
const_iterator end() const;
const_iterator cend() const;
// Deleting elements.
void pop_front();
void pop_back();
void del(iterator iter); // Note delete via iterator
};
We can simplify the iterator:
struct Iterator: public std::iterator<std::bidirectional_iterator_tag, T>
{
Element* current;
Iterator(Element* start)
: current(start)
{}
// Increment/Decrement pre and post fix
Iterator& operator++() {current = current->next;return *this;}
Iterator& operator--() {current = current->prev;return *this;}
Iterator operator++(int) {Iterator r(*this);this->operator++();return r;} // Note define in terms of prefix.
Iterator operator--(int) {Iterator r(*this);this->operator--();return r;} // Note define in terms of prefix.
// Test against other iterators.
bool operator==(Iterator const& rhs) const {return current == rhs.current;}
bool operator!=(Iterator const& rhs) const {return current != rhs.current;}
};
// Have specific versions for normal iterator.
// And another for a const version of the iterator.
struct IteratorNorm: public Iterator
{
IteratorNorm(Element* st): Iterator(st) {}
T& operator*() {return static_cast<DataElement*>(this->current)->data;}
};
struct IteratorConst: public Iterator
{
IteratorConst(Element* st): Iterator(st) {}
T const& operator*() const {return static_cast<DataElement*>(this->current)->data;}
};
// Create the appropriate types need by algorithm
typedef IteratorNorm iterator;
typedef IteratorConst const_iterator;