From 7af930f2242f933f79dfbb4ddc84bfd532069556 Mon Sep 17 00:00:00 2001 From: Charles Date: Sat, 1 Feb 2020 10:37:15 +0100 Subject: Basic list methods --- include/List.hpp | 186 ++++++++++++++++++++++++++++++++++++++++++++++ include/Stack.hpp | 29 ++++++++ include/Vector.hpp | 128 +++++++++++++++++++++++++++++++ include/ft_containers.hpp | 22 ++++++ 4 files changed, 365 insertions(+) create mode 100644 include/List.hpp create mode 100644 include/Stack.hpp create mode 100644 include/Vector.hpp create mode 100644 include/ft_containers.hpp (limited to 'include') diff --git a/include/List.hpp b/include/List.hpp new file mode 100644 index 0000000..096660c --- /dev/null +++ b/include/List.hpp @@ -0,0 +1,186 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* List.hpp :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/02/01 09:31:07 by cacharle #+# #+# */ +/* Updated: 2020/02/01 10:36:03 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#ifndef LIST_HPP +# define LIST_HPP + +# include + +namespace ft +{ + template < typename T, typename Alloc = std::allocator > + class List + { + + typedef T value_type; + typedef Alloc allocator_type; + typedef typename allocator_type::reference reference; + // typename allocator_type::const_reference const_reference; + // typename allocator_type::pointer pointer; + // typename allocator_type::const_pointer const_pointer; + + typedef size_t size_type; + + public: + List(const allocator_type& alloc = allocator_type()) + { + ptr_front = nullptr; + ptr_back = nullptr; + p_size = 0; + } + // List(size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type()); + // template + // List(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type()); + // List(const list& x); + ~List() + { + while (size() > 0) + pop_front(); + } + // List& operator = (const List& x); + + // iterators + // iterator begin(); + // iterator end(); + // reverse_iterator rbegin(); + // reverse_iterator rend(); + // const_iterator begin() const; + // const_iterator end() const; + // const_reverse_iterator rbegin() const; + // const_reverse_iterator rend() const; + + // capacity + bool empty() const + { + return ptr_front == nullptr; + } + size_type size() const + { + return p_size; + } + + // size_type max_size() const; + + // element access + reference front() + { + return *ptr_front; + } + + reference back() + { + return *ptr_back; + } + // const_reference front() const; + // const_reference back(); + + // modifiers + // template + // void assign (InputIterator first, InputIterator last); + // void assign (size_type n, const value_type& val); + void push_front (const value_type &val) + { + PrivateList *nfront = new PrivateList(val); + nfront->next = ptr_front; + ptr_front = nfront; + if (ptr_back == nullptr) + ptr_back = ptr_front; + p_size++; + } + void pop_front() + { + PrivateList *nfront = ptr_front->next; + if (size() == 1) + ptr_back = nullptr; + delete ptr_front; + ptr_front = nfront; + p_size--; + } + void push_back (const value_type& val) + { + PrivateList *nback = new PrivateList(val); + if (empty()) + { + ptr_back = nback; + ptr_front = ptr_back; + return; + } + ptr_back->next = nback; + ptr_back = nback; + p_size++; + } + void pop_back() + { + PrivateList *tmp = ptr_front; + + while (tmp->next != ptr_back) + tmp = tmp->next; + delete ptr_back; + ptr_back = tmp; + p_size--; + } + // iterator insert (iterator position, const value_type& val); + // void insert (iterator position, size_type n, const value_type& val); + // template + // void insert (iterator position, InputIterator first, InputIterator last); + // iterator erase (iterator position); + // iterator erase (iterator first, iterator last); + // void swap (list& x); + // void resize (size_type n, value_type val = value_type()); + // void clear(); + + // operations + // void splice (iterator position, list& x); + // void splice (iterator position, list& x, iterator i); + // void splice (iterator position, list& x, iterator first, iterator last); + // void remove (const value_type& val); + // template + // void remove_if (Predicate pred); + // void unique(); + // template + // void unique (BinaryPredicate binary_pred); + // + // void merge (list& x); + // template + // void merge (list& x, Compare comp); + // void sort(); + // template + // void sort (Compare comp); + // void reverse(); + + // observers + // allocator_type get_allocator() const; + + private: + class PrivateList + { + public: + PrivateList(const value_type &val) : val(val) + { + next = nullptr; + } + + // ~PrivateList() + // { + // delete val; + // } + + PrivateList *next; + const value_type &val; + }; + PrivateList *ptr_front; + PrivateList *ptr_back; + size_type p_size; + }; +} + +#endif diff --git a/include/Stack.hpp b/include/Stack.hpp new file mode 100644 index 0000000..64bfc66 --- /dev/null +++ b/include/Stack.hpp @@ -0,0 +1,29 @@ +#ifndef STACK_HPP +# define STACK_HPP + +# include "vector.hpp" + +namespace ft +{ + template > + class stack : public vector + { + public: + explicit stack (const container_type& ctnr = container_type()); + value_type& top() + { + return back(); + } + void push (const value_type& val) + { + push_back(val); + } + void pop() + { + pop_back(); + } + }; +} + +#endif + diff --git a/include/Vector.hpp b/include/Vector.hpp new file mode 100644 index 0000000..0f21995 --- /dev/null +++ b/include/Vector.hpp @@ -0,0 +1,128 @@ +#ifndef VECTOR_HPP +# define VECTOR_HPP + +# include + +# define GROWTH_FACTOR 1.5 + +typedef size_t size_type; + + +namespace ft +{ + template < class T, class Alloc = allocator > + class vector + { + typedef T value_type; + typedef T& reference; + + public: + // capacity + size_type size() const; + { + return size; + } + void resize (size_type n, value_type val = value_type()) + { + if (n < size) + { + for (int i = n; i < size; i++) + ~T(under[i]); + size = n; + return; + } + if (n > capacity) + grow(); + size_type prev_n; + for (prev_n = n; prev_n < size; prev_n++) + under[n] = val; + size = n; + } + size_type capacity() const + { + return capacity; + } + bool empty() const + { + return size == 0; + } + void reserve (size_type n) + { + if (n > capacity) + grow_to(n); + } + + // element access + reference operator[] (size_type n) + { + return under[n]; + } + reference at (size_type n) + { + if (n >= size) + raise std::out_of_range; + return under[n]; + } + reference front() + { + return under[0]; + } + reference back() + { + return under[size - 1]; + } + + // modifiers + template + void assign (InputIterator first, InputIterator last); + void assign (size_type n, const value_type& val); + void push_back (const value_type& val) + { + if (size >= capacity) + grow(); + under[size] = val; + size++; + } + void pop_back() + { + ~T(back()); + size--; + } + iterator insert (iterator position, const value_type& val) + { + + } + void insert (iterator position, size_type n, const value_type& val); + template + void insert (iterator position, InputIterator first, InputIterator last); + + + + + private: + T *under; + size_type size; + size_type capacity; + + void grow() + { + capacity *= GROWTH_FACTOR; + grow_to(capacity); + } + + void grow_to(size_type new_capacity) + { + T *under_copy = new T[capacity]; + for (int i = 0; i < capacity; i++) + under_copy[i] = under[i]; + delete [] under; + capacity = new_capacity; + under = new T[capacity]; + for (int i = 0; i < capacity; i++) + under[i] = under_copy[i]; + delete [] under_copy; + } + }; +} + +#endif diff --git a/include/ft_containers.hpp b/include/ft_containers.hpp new file mode 100644 index 0000000..76637ac --- /dev/null +++ b/include/ft_containers.hpp @@ -0,0 +1,22 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_containers.hpp :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/02/01 10:09:01 by cacharle #+# #+# */ +/* Updated: 2020/02/01 10:09:50 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#ifndef FT_CONTAINERS_HPP +# define FT_CONTAINERS_HPP + +# include + +# include "List.hpp" + +void test_list_base(); + +#endif -- cgit