You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
372 lines
11 KiB
372 lines
11 KiB
#pragma once
|
|
#include "iterator.hpp"
|
|
#include "reverse_iterator.hpp"
|
|
#include "utils.hpp"
|
|
|
|
#include <iostream>
|
|
#include <memory>
|
|
#include <stdexcept>
|
|
|
|
#define OVER_ALLOC 3
|
|
|
|
namespace ft {
|
|
|
|
template < class T, class Alloc = std::allocator< T > > class vector {
|
|
public:
|
|
typedef T value_type;
|
|
typedef Alloc allocator_type;
|
|
typedef typename Alloc::pointer pointer;
|
|
typedef typename Alloc::const_pointer const_pointer;
|
|
typedef value_type &reference;
|
|
typedef const value_type &const_reference;
|
|
typedef ft::random_access_iterator< T > iterator;
|
|
typedef ft::random_access_iterator< const T > const_iterator;
|
|
typedef ft::reverse_iterator< iterator > reverse_iterator;
|
|
typedef ft::reverse_iterator< const_iterator > const_reverse_iterator;
|
|
typedef std::ptrdiff_t difference_type;
|
|
typedef std::size_t size_type;
|
|
|
|
private:
|
|
Alloc _alloc;
|
|
pointer _begin;
|
|
size_type _size;
|
|
size_type _capacity;
|
|
|
|
public:
|
|
explicit vector(const Alloc &alloc = allocator_type())
|
|
: _alloc(alloc), _begin(NULL), _size(0), _capacity(0){};
|
|
|
|
explicit vector(size_type count, const_reference value = T(),
|
|
const Alloc &alloc = allocator_type())
|
|
: _alloc(alloc), _size(count), _capacity(0) {
|
|
if (count > _alloc.max_size())
|
|
throw std::length_error("vector: too high size.");
|
|
else if (count == 0)
|
|
return;
|
|
else
|
|
_capacity = std::min(OVER_ALLOC * count, _alloc.max_size() - 1);
|
|
_begin = _alloc.allocate(_capacity);
|
|
for (size_type i = 0; i < count; i++)
|
|
_alloc.construct(_begin + i, value);
|
|
}
|
|
|
|
template < class It >
|
|
vector(It first, It last, const Alloc &alloc = allocator_type(),
|
|
typename ft::enable_if< !is_integral< It >::value, bool >::type = 0)
|
|
: _alloc(alloc), _size(0), _capacity(0) {
|
|
assign(first, last);
|
|
}
|
|
|
|
vector(const vector &other)
|
|
: _alloc(other._alloc), _size(other._size), _capacity(other._capacity) {
|
|
if (_capacity == 0)
|
|
return;
|
|
_begin = _alloc.allocate(_capacity);
|
|
for (size_type i = 0; i < _size; i++)
|
|
_alloc.construct(_begin + i, other._begin[i]);
|
|
}
|
|
|
|
~vector(void) {
|
|
clear();
|
|
if (_capacity > 0)
|
|
_alloc.deallocate(_begin, _capacity);
|
|
}
|
|
|
|
vector &operator=(const vector &other) {
|
|
clear();
|
|
if (_capacity > 0)
|
|
_alloc.deallocate(_begin, _capacity);
|
|
_alloc = other._alloc;
|
|
_capacity = other._capacity;
|
|
_size = other._size;
|
|
if (_capacity > 0)
|
|
_begin = _alloc.allocate(_capacity);
|
|
for (size_type i = 0; i < _size; i++)
|
|
_alloc.construct(_begin + i, other._begin[i]);
|
|
return (*this);
|
|
}
|
|
|
|
void assign(size_type count, const_reference value) {
|
|
resize(count);
|
|
iterator it = begin();
|
|
while (it != end())
|
|
*it++ = value;
|
|
}
|
|
template < class It >
|
|
void
|
|
assign(It first, It last,
|
|
typename ft::enable_if< !is_integral< It >::value, bool >::type = 0) {
|
|
typename ft::iterator_traits< It >::iterator_category category;
|
|
range_assign(first, last, category);
|
|
}
|
|
|
|
template < class It >
|
|
void range_assign(It first, It last, std::input_iterator_tag) {
|
|
clear();
|
|
while (first != last)
|
|
push_back(*first++);
|
|
}
|
|
|
|
template < class It >
|
|
void range_assign(It first, It last, std::forward_iterator_tag) {
|
|
size_type count = ft::distance(first, last);
|
|
if (count == 0)
|
|
return clear();
|
|
vector< T, Alloc > ret(count);
|
|
iterator it = ret.begin();
|
|
for (size_type i = 0; first != last; i++)
|
|
*(it + i) = *(first++);
|
|
*this = ret;
|
|
}
|
|
allocator_type get_allocator(void) const { return _alloc; }
|
|
|
|
// ACCESS:
|
|
reference at(size_type pos) {
|
|
if (pos >= _size)
|
|
throw(std::out_of_range("vector: Out of range access"));
|
|
return *(_begin + pos);
|
|
}
|
|
const_reference at(size_type pos) const {
|
|
if (pos >= _size)
|
|
throw(std::out_of_range("vector: Out of range access"));
|
|
return *(_begin + pos);
|
|
}
|
|
|
|
reference operator[](size_type pos) { return _begin[pos]; }
|
|
const_reference operator[](size_type pos) const { return _begin[pos]; }
|
|
|
|
reference front(void) { return _begin[0]; }
|
|
const_reference front(void) const { return _begin[0]; }
|
|
|
|
reference back(void) { return _begin[_size - 1]; }
|
|
const_reference back(void) const { return _begin[_size - 1]; }
|
|
|
|
pointer data(void) { return _begin; }
|
|
const_pointer data(void) const { return _begin; }
|
|
|
|
// ITERATORS:
|
|
iterator begin(void) { return iterator(_begin); }
|
|
const_iterator begin(void) const { return const_iterator(_begin); }
|
|
|
|
iterator end(void) { return iterator(_begin + _size); }
|
|
const_iterator end(void) const { return const_iterator(_begin + _size); }
|
|
|
|
reverse_iterator rbegin(void) { return reverse_iterator(end()); }
|
|
const_reverse_iterator rbegin(void) const {
|
|
return const_reverse_iterator(end());
|
|
}
|
|
|
|
reverse_iterator rend(void) { return reverse_iterator(begin()); }
|
|
const_reverse_iterator rend(void) const {
|
|
return const_reverse_iterator(begin());
|
|
}
|
|
|
|
// CAPACITY:
|
|
bool empty(void) const { return _size == 0; }
|
|
size_type size(void) const { return _size; }
|
|
size_type max_size(void) const { return _alloc.max_size(); }
|
|
size_type capacity(void) const { return _capacity; }
|
|
|
|
void reserve(size_type new_cap) {
|
|
if (new_cap > max_size())
|
|
throw(std::length_error("vector::reserve: new_cap > max_size"));
|
|
if (new_cap <= _capacity)
|
|
return;
|
|
else
|
|
new_cap = std::min(OVER_ALLOC * new_cap, _alloc.max_size() - 1);
|
|
Alloc new_alloc;
|
|
pointer new_begin;
|
|
size_type new_size = _size;
|
|
new_begin = new_alloc.allocate(new_cap);
|
|
for (size_type i = 0; i < _size; i++)
|
|
new_alloc.construct(new_begin + i, *(_begin + i));
|
|
clear();
|
|
if (_capacity > 0)
|
|
_alloc.deallocate(_begin, _capacity);
|
|
_alloc = new_alloc;
|
|
_begin = new_begin;
|
|
_size = new_size;
|
|
_capacity = new_cap;
|
|
}
|
|
|
|
// MODIFIERS:
|
|
void clear(void) {
|
|
if (_size == 0)
|
|
return;
|
|
for (size_type i = 0; i < _size; i++)
|
|
_alloc.destroy(_begin + i);
|
|
_size = 0;
|
|
}
|
|
|
|
iterator insert(iterator pos, const_reference value) {
|
|
difference_type pos_i = pos - begin();
|
|
resize(_size + 1);
|
|
iterator new_pos = begin() + pos_i;
|
|
iterator it = end();
|
|
while (--it > new_pos)
|
|
*it = *(it - 1);
|
|
*it = value;
|
|
return new_pos;
|
|
}
|
|
|
|
iterator insert(iterator pos, size_type count, const_reference value) {
|
|
if (count == 0)
|
|
return pos;
|
|
iterator new_pos = begin();
|
|
resize(_size + count);
|
|
new_pos = begin() + (pos - new_pos);
|
|
iterator it = end();
|
|
while (--it >= (new_pos + count))
|
|
*it = *(it - count);
|
|
while (it >= new_pos) {
|
|
*(it--) = value;
|
|
}
|
|
return new_pos;
|
|
}
|
|
|
|
template < class It >
|
|
iterator
|
|
insert(iterator pos, It first, It last,
|
|
typename ft::enable_if< !is_integral< It >::value, bool >::type = 0) {
|
|
typename std::iterator_traits< It >::iterator_category cat;
|
|
return range_insert(pos, first, last, cat);
|
|
}
|
|
|
|
template < class It >
|
|
iterator range_insert(iterator pos, It first, It last,
|
|
std::input_iterator_tag) {
|
|
size_type count = 0;
|
|
do {
|
|
pos = insert(pos, *first);
|
|
++pos;
|
|
++count;
|
|
} while (++first != last);
|
|
return pos - count;
|
|
}
|
|
|
|
template < class It >
|
|
iterator range_insert(iterator pos, It first, It last,
|
|
std::forward_iterator_tag) {
|
|
size_type count = ft::distance(first, last);
|
|
if (count == 0)
|
|
return pos;
|
|
iterator new_pos = begin();
|
|
resize(_size + count);
|
|
new_pos = begin() + (pos - new_pos);
|
|
iterator it = end();
|
|
while (--it >= (new_pos + count))
|
|
*it = *(it - count);
|
|
size_type i = 0;
|
|
while (i < count) {
|
|
*(new_pos + i++) = *(first++);
|
|
}
|
|
return new_pos;
|
|
}
|
|
|
|
iterator erase(iterator pos) {
|
|
iterator ret = pos;
|
|
while ((pos + 1) < end()) {
|
|
*pos = *(pos + 1);
|
|
pos++;
|
|
}
|
|
_alloc.destroy(pos.base());
|
|
_size--;
|
|
return ret;
|
|
}
|
|
iterator erase(iterator first, iterator last) {
|
|
if (first == last)
|
|
return last;
|
|
iterator pos = first;
|
|
size_type diff_size = ft::distance(first, last);
|
|
while (last < end())
|
|
*pos++ = *last++;
|
|
while (pos < end())
|
|
_alloc.destroy((pos++).base());
|
|
_size -= diff_size;
|
|
return first;
|
|
}
|
|
|
|
void push_back(const_reference value) {
|
|
reserve(_size + 1);
|
|
_alloc.construct(_begin + _size++, value);
|
|
}
|
|
void pop_back(void) { _alloc.destroy(_begin + --_size); }
|
|
|
|
void resize(size_type count, T value = T()) {
|
|
if (count == _size)
|
|
return;
|
|
if (count < _size) { // 0 < 5
|
|
while (count < _size) // 0 <= 4 ; 0 <= 3; 0 <=2; 0 <=1; 0<= 0;
|
|
_alloc.destroy(_begin + --_size); // --5; --4; --3; --2; --1;
|
|
} else {
|
|
reserve(count);
|
|
while (_size < count)
|
|
_alloc.construct(_begin + _size++, value);
|
|
}
|
|
}
|
|
|
|
void swap(vector &other) {
|
|
pointer ptr = other._begin;
|
|
size_type size = other._size;
|
|
size_type capacity = other._capacity;
|
|
allocator_type alloc = other._alloc;
|
|
other._begin = _begin;
|
|
other._size = _size;
|
|
other._capacity = _capacity;
|
|
other._alloc = _alloc;
|
|
_begin = ptr;
|
|
_size = size;
|
|
_capacity = capacity;
|
|
_alloc = alloc;
|
|
}
|
|
|
|
void print(void) {
|
|
ft::random_access_iterator< T > i = begin();
|
|
while (i < end()) {
|
|
std::cout << *i << " ";
|
|
i++;
|
|
}
|
|
std::cout << "\n";
|
|
}
|
|
};
|
|
|
|
template < class T2, class Alloc2 >
|
|
bool operator==(const vector< T2, Alloc2 > &lhs,
|
|
const vector< T2, Alloc2 > &rhs) {
|
|
if (lhs.size() != rhs.size())
|
|
return false;
|
|
return ft::equal(lhs.begin(), lhs.end(), rhs.begin());
|
|
}
|
|
template < class T2, class Alloc2 >
|
|
bool operator!=(const vector< T2, Alloc2 > &lhs,
|
|
const vector< T2, Alloc2 > &rhs) {
|
|
return !(lhs == rhs);
|
|
}
|
|
template < class T2, class Alloc2 >
|
|
bool operator<(const vector< T2, Alloc2 > &lhs,
|
|
const vector< T2, Alloc2 > &rhs) {
|
|
return ft::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(),
|
|
rhs.end());
|
|
}
|
|
template < class T2, class Alloc2 >
|
|
bool operator>(const vector< T2, Alloc2 > &lhs,
|
|
const vector< T2, Alloc2 > &rhs) {
|
|
return rhs < lhs;
|
|
}
|
|
template < class T2, class Alloc2 >
|
|
bool operator<=(const vector< T2, Alloc2 > &lhs,
|
|
const vector< T2, Alloc2 > &rhs) {
|
|
return !(lhs > rhs);
|
|
}
|
|
template < class T2, class Alloc2 >
|
|
bool operator>=(const vector< T2, Alloc2 > &lhs,
|
|
const vector< T2, Alloc2 > &rhs) {
|
|
return !(lhs < rhs);
|
|
}
|
|
|
|
template < class T, class Alloc >
|
|
void swap(ft::vector< T, Alloc > &lhs, ft::vector< T, Alloc > &rhs) {
|
|
lhs.swap(rhs);
|
|
}
|
|
|
|
} // namespace ft
|
|
|