it would seem that using std::unique_ptr makes sense, but there still needs to be other pointers "sharing" the unique_ptr. I.e if nxt is a unique_ptr, what do I do with prv and iterator::it?
Don't. (1) It makes various internal algorithms trickier to perform without accidentally deleting a node, and (2) unique_ptr stores the deleter, in your case that's either (A) a copy of the iterator, or (B) a pointer to the iterator. Either one is a waste of space. The container should store the allocator, and the container should handle deletions.
it would seem that it should take an allocator as a template paraemter, but it will be an allocator of type T, not LLNode?
Containers take an allocator of type T, though all of them use a rebound type internally. The standard is that allocators to containers take type T
, and that way every std::vector<T, allocator<?>>
matches every other. Also, outsiders should not be able to access LLNode. You'd probably store a given_allocator<LLNode>
internally though. That's why we have rebinding.
are there any traits, that need to be "registered"?
For containers, no. There are interfaces to match, but those are relatively obvious.
Yes, your iterators are supposed to register traits, but that's easily done by merely adding five typedefs at the front.
typedef ptrdiff_t difference_type; //usually ptrdif_t
typedef T value_type; //usually T
typedef T& reference; //usually T&
typedef T* pointer; //usually T*
typedef std::bidirectional_iterator_tag iterator_category;
if move semantics are used, what methods should be defined e.g. operator=() && etc.?
Obviously the container should be move constructable and move assignable if it makes sense, which it does 99.99% of the time. Even std::array
has move operators. Also decide which member functions should support move-only-T (insert range via iterators, but not insert range + count), and which member functions support any T (emplace one).
what undefined behavior (if any) needs to be corrected?
It would appear that your
insert(iterator, data)
inserts the data after the iterator, when the standard is to insert before the iterator. Your way makes it impossible to add data to the beginning, and makes it possible to add data after the after-the-end.Your iterators have but do not need
remove
andinsert
functions. I wouldn't have mentioned it, but in this case they require the iterators to be twice as big as needed. I'd offer a tentative suggestion to remove them, but only tentative. That's a small penalty, and potentially a useful feature.Your
operator =
deallocates everything and then reallocates. It might be handy to simply copy element by element skipping that when possible. Trickier to code though.You're missing a constructor that constructs from a pair of iterators.
Your iterators allow mutating of data from
const
containers. THIS ONE IS BIGget_first
andget_last
are normally calledfront
andback
.
what am i not concerned about that I should be?
The big one that everyone overlooks is exception safety. Your code is exception safe, but that appears to be because your code is amazingly simple, and you skipped all of the "hard" parts :P
For more information review these:
Writing your own STL Container
How to implement an STL-style iterator and avoid common pitfalls?
Edit for your C++11 followup:
missing:
- template LLNode(U&& x) //or, one
T&&
and oneconst T&
- LinkedList(std::initializer_list x)
- T& LLNode::get_data() const //important, your code doesn't even compile
- T* iterator::operator->() const //important
- const_iterator cbegin() const
- const_iterator cend() const
- const T& front() const //important
- const T& back() const //important
- template void assign(iter, iter);
- void assign(std::initializer_list);
- void swap(const X&);
Incorrect:
- insert_* should probably take a
U&&
and usestd::forward<U>(x)
. Variadic templates would be better. - no iterator pair constructor.
- memory leak in alloc_node, and you should be constructing a LLNode, you have uninitialized prv/nxt.
- unalloc_node never destroys, only deallocates, leading to a memory leak
Missing but pretty unimportant
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
- reverse_iterator rbegin(); //optional
- const_reverse_iterator rbegin() const;
- const_reverse_iterator crbegin() const;
- reverse_iterator rend(); //optional
- const_reverse_iterator rend() const;
- const_reverse_iterator crend() const;
Optional:
- not sure why
my_alloc
andmy_traits
and they're identical. - inherit privately from the allocator. It's a little wierd, but commonly saves you 8 bytes.