jaekpark / ft_containers Goto Github PK

View Code? Open in Web Editor NEW

0.0 1.0 0.0 26.21 MB

42 ft_containers : Implementation C++ STL containers

C++ 97.62% Makefile 2.38%

cpp 42born2code 42cursus 42projects 42seoul re-implementation stl-containers

ft_containers's Introduction

Summary

This is a project to re-implement some C++ STL Containers to understand them.

Some requirements for this project are as follow:

Re-implement (The documents below are written in Korean.)

Mandatory

Bonus

std::set

What is STL? ^[1]

The Standard Template Library (STL) is a set of C++ template classes to provide common programming data structures and functions such as list, stack, vector, etc ^[1]

STL has four components

Algorithms

Containers

Functions(Functor)

Iterators

This project is designed to implement a few containers, functions, and iterators in the C++98.

Algorithms

The header algorithm defines a collection of functions especially designed to be used on ranges of elements. They act on containers and provide means for various operations for the contents of the containers. ^[1]

Algorithms

Sorting

Searching

partition

etc.

Containers

Containers or container classes store objects and data. There are in total 7 standard "first-class" container classes and 3 container adaptor classes and only seven header files that provide access to these containers or container adaptors. ^[1]

sequence containers	container adaptors	associative containers	unordered associative containers`(c++11)`
implement data structures which can be accessed in a sequential manner.	provide a different interface for sequential containers.	implement sorted data structures that can be quickly searched(O(long n) complexity).	implement unordered data structures that can be quickly searched
vector	queue	set	unordered_set `(c++11)`
list	priority queue	multiset	unordered_multiset `(c++11)`
deque	stack	map	unordered_map `(c++11)`
arrays`(c++11)`	multimap		unordered_multimap `(c++11)`
forward lists`(c++11)`

Flowchart of Adaptive containers and Unordered Containers ^[1]

Flowchart of Sequence containers and Ordered Containers ^[1]

Functions(Functor)

The STL includes classes that overload the function call operator. Instances of such classes are called function objects or functors. Functors allow the working of the associated function to be customized with the help of parameters to be passed. ^[1]

Iterators

As the name suggests, iterators are used for working upon a sequence of values. They are the major feature that allow generality in STL. ^[1]

Reference

index	title	author	last modified	accessed	url status
1	The C++ Standard Template Library (STL)	GeeksforGeeks	19 Nov, 2021	15 May, 2022	ok

ft_containers's People

Contributors

Watchers

ft_containers's Issues

[Feature] Implement `map` Container

[Docs] Write documents for project

[Feature] Implement `equal` or `lexicographical_compare`

[Feature] Implement OCF for 'vector' container

  // 생성자/소멸자
  explicit vector(const Allocator& alloc = Allocator());
  explicit vector(size_type n, const T& value = T(),
                  const Allocator& allocator = Allocator());
  template <class InputIterator>
  vector(InputIterator first, InputIterator last,
         const Allocator& allocator = Allocator());
  explicit vector(const vector<T, Allocator>& x);
  ~vector(void);
  // 대입 연산자
  vector<T, Allocator>& operator=(const vector<T, Allocator>& x);

[Feature] Implement non-member functions of 'vector' container

template <class T, class Alloc>
  void swap (vector<T,Alloc>& x, vector<T,Alloc>& y);

[Feature] Implement member functions of 'vector' container

  // iterator
  iterator begin(void);
  const_iterator begin(void) const;
  iterator end(void);
  const_iterator end(void) const;
  reverse_iterator rbegin(void);
  const_reverse_iterator rbegin(void);
  reverse_iterator rend(void);
  const_reverse_iterator rend(void);

  // capacity
  size_type size(void) const;
  size_type max_size(void) const;
  void resize(size_type n, value_type val = value_type());
  size_type capacity(void) const;
  bool empty(void) const;
  void reserve(size_type n);

  // element access
  reference operator[](size_type n);
  const_reference operator[](size_type n) const;
  reference at(size_type n);
  const_reference at(size_type n) const;
  reference front(void);
  const_reference front(void) const;
  reference back(void);
  const_reference back(void) const;

  // modifiers
  template <class InputIterator>
  void assign(InputIterator first, InputIterator last
  void assign(size_type n, const T& u);
  void push_back(const T& x);
  void pop_back(void);
  iterator insert(iterator position, const T& x);
  void insert(iterator position, size_type n, const T& x);
  template <class InputIterator>
  void insert(iterator position, InputIterator first, InputIterator last);
  iterator erase(iterator position);
  iterator erase(iterator first, iterator last);
  void swap(vector<T, Allocator>&);
  void clear(void);
  
  // allocator
  allocator_type get_allocator(void) const;

[Feature] Implement `type_traits`

is_integral
enable_if

[Feature] Implement relation operators overriding of 'vector' container

template <class T, class Allocator>
	bool operator==(const vector<T, Allocator>& x, const vector<T, Allocator>& y);
template <class T, class Allocator>
	bool operator!=(const vector<T, Allocator>& x, const vector<T, Allocator>& y);
template <class T, class Allocator>
	bool operator<(const vector<T, Allocator>& x, const vector<T, Allocator>& y);
template <class T, class Allocator>
	bool operator>(const vector<T, Allocator>& x, const vector<T, Allocator>& y);
template <class T, class Allocator>
	bool operator<=(const vector<T, Allocator>& x, const vector<T, Allocator>& y);
template <class T, class Allocator>
	bool operator>=(const vector<T, Allocator>& x, const vector<T, Allocator>& y);