Last active
August 29, 2015 14:11
-
-
Save faithandbrave/ac1a37f1f53fe6480634 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Copyright Akira Takahashi 2014 | |
// Use, modification and distribution is subject to the Boost Software License, | |
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
// http://www.boost.org/LICENSE_1_0.txt) | |
#include <cstddef> | |
namespace my_stl { | |
template <class Iterator> | |
struct iterator_traits { | |
static typename Iterator::reference dereference(Iterator& it) | |
{ | |
return it.dereference(); | |
} | |
static Iterator next(const Iterator& it) | |
{ | |
return it.next(); | |
} | |
static bool equal(const Iterator& a, const Iterator& b) | |
{ | |
return a.equal(b); | |
} | |
}; | |
template <class T> | |
struct iterator_traits<T*> { | |
static T& dereference(T* it) | |
{ | |
return *it; | |
} | |
static T* next(T* it) | |
{ | |
return ++it; | |
} | |
static bool equal(const T* a, const T* b) | |
{ | |
return a == b; | |
} | |
}; | |
template <class T> | |
struct node { | |
T value; | |
node* next = nullptr; | |
}; | |
template <class T> | |
class singly_linked_list_iterator { | |
node<T>* node_ = nullptr; | |
public: | |
using reference = T&; | |
singly_linked_list_iterator() = default; | |
singly_linked_list_iterator(node<T>* node) | |
: node_(node) {} | |
reference dereference() | |
{ | |
return node_->value; | |
} | |
singly_linked_list_iterator next() const | |
{ | |
return node_->next; | |
} | |
bool equal(const singly_linked_list_iterator& it) const | |
{ | |
return node_ == it.node_; | |
} | |
}; | |
template <class T> | |
class singly_linked_list { | |
node<T>* node_ = nullptr; | |
std::size_t size_ = 0u; | |
public: | |
using iterator = singly_linked_list_iterator<T>; | |
~singly_linked_list() | |
{ | |
node<T>* current = node_; | |
while (current) { | |
node<T>* next = current->next; | |
delete current; | |
current = next; | |
} | |
} | |
void push_front(const T& x) | |
{ | |
node<T>* current = new node<T>(); | |
current->value = x; | |
current->next = node_; | |
node_ = current; | |
++size_; | |
} | |
std::size_t size() const | |
{ return size_; } | |
iterator begin() | |
{ | |
return iterator(node_); | |
} | |
iterator end() | |
{ | |
return iterator(); | |
} | |
}; | |
template <class Iterator, class F> | |
void for_each(Iterator first, Iterator last, F f) | |
{ | |
using traits = my_stl::iterator_traits<Iterator>; | |
// no use raw pointer interface | |
Iterator it = first; | |
while (!traits::equal(it, last)) { | |
f(traits::dereference(it)); | |
it = traits::next(it); | |
} | |
} | |
} // namespace my_stl | |
#include <iostream> | |
int main() | |
{ | |
my_stl::singly_linked_list<int> ls; | |
ls.push_front(3); | |
ls.push_front(2); | |
ls.push_front(1); | |
my_stl::for_each(ls.begin(), ls.end(), [](int& x) { | |
std::cout << x << std::endl; | |
}); | |
int ar[3] = {4, 5, 6}; | |
my_stl::for_each(ar, ar + 3, [](int& x) { | |
std::cout << x << std::endl; | |
}); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment