Skip to content

Instantly share code, notes, and snippets.

@faithandbrave
Last active August 29, 2015 14:11
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save faithandbrave/ac1a37f1f53fe6480634 to your computer and use it in GitHub Desktop.
Save faithandbrave/ac1a37f1f53fe6480634 to your computer and use it in GitHub Desktop.
// 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