Advertisement
Kirixh

Untitled

May 21st, 2022
1,441
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. template <typename T>
  4. class ListIterator;
  5.  
  6. template <typename T, typename Allocator = std::allocator<T>>
  7. class List {
  8.   friend class ListIterator<T>;
  9.   public:
  10.  
  11.   using value_type = T;
  12.   using allocator_type = Allocator;
  13.   using iterator = ListIterator<T>;
  14.   using const_iterator = ListIterator<const T>;
  15.  
  16.   List();
  17.  
  18.   explicit List(size_t count, const T& value,
  19.                 const Allocator& alloc = Allocator());
  20.  
  21.   explicit List(size_t count, const Allocator& alloc = Allocator());
  22.  
  23.   List(const List& other);
  24.  
  25.   List(List&& other) noexcept;
  26.  
  27.   List(std::initializer_list<value_type> init,
  28.        const Allocator& alloc = Allocator());
  29.  
  30.   ~List();
  31.  
  32.   List& operator=(const List& other);
  33.   List& operator=(List&& other) noexcept;
  34.  
  35.   [[nodiscard]] size_t size() const {
  36.     return size_;
  37.   };
  38.  
  39.   [[nodiscard]] bool empty() const {
  40.     return size_ == 0;
  41.   }
  42.  
  43.   [[nodiscard]] iterator begin() const;
  44.   [[nodiscard]] const_iterator cbegin() const;
  45.   [[nodiscard]] iterator end() const;
  46.   [[nodiscard]] const_iterator cend() const;
  47.  
  48.   value_type& front();
  49.   [[nodiscard]] const value_type& front() const;
  50.   value_type& back();
  51.   [[nodiscard]] const value_type& back() const;
  52.  
  53.   template<typename... Args>
  54.   void emplace_back(Args&&... args);
  55.  
  56.   template<typename... Args>
  57.   void emplace_front(Args&&... args);
  58.  
  59.  
  60.  
  61.   private:
  62.   struct Node;
  63.   Node* head_;
  64.   Node* tail_;
  65.   Node* x_;
  66.   size_t size_ = 0;
  67.  
  68.   using alloc_traits = typename std::allocator_traits<
  69.       allocator_type>::template rebind_traits<Node>;
  70.   using alloc_type = typename std::allocator_traits<
  71.       allocator_type>::template rebind_alloc<Node>;
  72.   alloc_type alloc_;
  73.  
  74.   void set_ends();
  75.  
  76.  
  77.   Node* make_node();
  78.  
  79.   Node* make_node(value_type value);
  80.  
  81.   Node* make_node(const Node& other);
  82.  
  83.   template <typename ...Args>
  84.   Node* make_node(Args&&... args);
  85.  
  86.   void fill_list(size_t count);
  87.  
  88.   void fill_list(size_t count, T value);
  89.  
  90.   void fill_list(const List<T, Allocator>& other);
  91.  
  92.   void fill_list(std::initializer_list<T> init_list);
  93.  
  94.   void clean_list(Node* current, Node* next_node, bool dealloc = true);
  95. };
  96.  
  97. template<typename T>
  98.   class ListIterator : public std::iterator<std::bidirectional_iterator_tag, T> {
  99.     using node = typename List<T>::Node;
  100.     public:
  101.     explicit ListIterator(node* node_p_) : node_p_(node_p_) {};
  102.     ListIterator(const ListIterator<T>& it) : node_p_(it.node_p_) {}
  103.  
  104.     T operator*() const;
  105.     T* operator->() const;
  106.     ListIterator& operator++();
  107.     ListIterator& operator--();
  108.     bool operator==(const ListIterator& other);
  109.     bool operator!=(const ListIterator& other);
  110.  
  111.     private:
  112.  
  113.     node* node_p_;
  114. };
  115.  
  116.  
  117. ////////////////////////////////////////////////////////////////////////////////
  118.  
  119. template <typename T, typename Allocator>
  120. struct List<T, Allocator>::Node {
  121.   Node() = default;
  122.   explicit Node(T value) : value(value){};
  123.   Node(const Node& other)
  124.       : next(other.next), prev(other.prev), value(other.value) {
  125.   }
  126.  
  127.   explicit Node(T&& value) : value(std::move(value)) {
  128.   }
  129.  
  130.   Node(Node&& other) noexcept
  131.       : next(other.next), prev(other.prev), value(std::move(other.value)) {
  132.     next = nullptr;
  133.     prev = nullptr;
  134.   }
  135.   template <typename... Args>
  136.   Node(Args&&... args)
  137.       : value(std::forward<Args>(args)...) {
  138.   }
  139.  
  140.  
  141.   ~Node() = default;
  142.  
  143.   Node* next = nullptr;
  144.   Node* prev = nullptr;
  145.   T value {};
  146. };
  147.  
  148. template <typename T, typename Allocator>
  149. void List<T, Allocator>::set_ends() {
  150.   head_->prev = x_;
  151.   tail_->next = x_;
  152.   x_->next = head_;
  153.   x_->prev = tail_;
  154. }
  155.  
  156.  
  157. template <typename T, typename Allocator>
  158. typename List<T, Allocator>::Node* List<T, Allocator>::make_node(
  159.     const List::Node& other) {
  160.   Node* new_node = alloc_traits::allocate(alloc_, 1);
  161.   try {
  162.     alloc_traits::construct(alloc_, new_node, other);
  163.   } catch (...) {
  164.     alloc_traits::deallocate(alloc_, new_node, 1);
  165.     throw;
  166.   }
  167.   return new_node;
  168. }
  169.  
  170. template <typename T, typename Allocator>
  171. typename List<T, Allocator>::Node* List<T, Allocator>::make_node(
  172.     value_type value) {
  173.   Node* new_node = alloc_traits::allocate(alloc_, 1);
  174.   try {
  175.     alloc_traits::construct(alloc_, new_node, value);
  176.   } catch (...) {
  177.     alloc_traits::deallocate(alloc_, new_node, 1);
  178.     throw;
  179.   }
  180.   return new_node;
  181. }
  182.  
  183. template <typename T, typename Allocator>
  184. typename List<T, Allocator>::Node* List<T, Allocator>::make_node() {
  185.   Node* new_node = alloc_traits::allocate(alloc_, 1);
  186.   try {
  187.     alloc_traits::construct(alloc_, new_node);
  188.   } catch (...) {
  189.     alloc_traits::deallocate(alloc_, new_node, 1);
  190.     throw;
  191.   }
  192.   return new_node;
  193. }
  194.  
  195. template <typename T, typename Allocator>
  196. template <typename... Args>
  197. typename List<T, Allocator>::Node* List<T, Allocator>::make_node(Args&&... args) {
  198.   Node* new_node = alloc_traits::allocate(alloc_, 1);
  199.   try {
  200.     alloc_traits::construct(alloc_, new_node, std::forward<Args>(args)...);
  201.   } catch (...) {
  202.     alloc_traits::deallocate(alloc_, new_node, 1);
  203.     throw;
  204.   }
  205.   return new_node;
  206. }
  207.  
  208. template <typename T, typename Allocator>
  209. void List<T, Allocator>::clean_list(List::Node* current,
  210.                                     List::Node* next_node, bool dealloc) {
  211.   if (empty()) {
  212.     return;
  213.   }
  214.   while (next_node != x_) {
  215.     alloc_traits::destroy(alloc_, next_node);
  216.     if (dealloc) {
  217.       alloc_traits::deallocate(alloc_, next_node, 1);
  218.     }
  219.     next_node = current;
  220.     current = current->prev;
  221.   }
  222. }
  223.  
  224. template <typename T, typename Allocator>
  225. void List<T, Allocator>::fill_list(size_t count, value_type value) {
  226.   Node* current = x_;
  227.   Node* next_node;
  228.   try {
  229.     for (size_t i = 0; i < count; ++i) {
  230.       next_node = make_node(value);
  231.       current->next = next_node;
  232.       next_node->prev = current;
  233.       current = next_node;
  234.     }
  235.   } catch (...) {
  236.     clean_list(current, next_node);
  237.     alloc_traits::deallocate(alloc_, x_, 1);
  238.     throw;
  239.   }
  240.   head_ = x_->next;
  241.   tail_ = next_node;
  242.   set_ends();
  243. }
  244.  
  245. template <typename T, typename Allocator>
  246. void List<T, Allocator>::fill_list(size_t count) {
  247.   Node* current = x_;
  248.   Node* next_node;
  249.   try {
  250.     for (size_t i = 0; i < count; ++i) {
  251.       next_node = make_node();
  252.       current->next = next_node;
  253.       next_node->prev = current;
  254.       current = next_node;
  255.     }
  256.   } catch (...) {
  257.     clean_list(current, next_node);
  258.     alloc_traits::deallocate(alloc_, x_, 1);
  259.     throw;
  260.   }
  261.   head_ = x_->next;
  262.   tail_ = next_node;
  263.   set_ends();
  264. }
  265.  
  266. template <typename T, typename Allocator>
  267. void List<T, Allocator>::fill_list(const List<T, Allocator>& other) {
  268.   Node* current = x_;
  269.   Node* next_node;
  270.   Node* other_current = other.x_;
  271.   try {
  272.     while (other_current != other.tail_) {
  273.       other_current = other_current->next;
  274.       next_node = make_node(*other_current);
  275.       current->next = next_node;
  276.       next_node->prev = current;
  277.       current = next_node;
  278.     }
  279.   } catch (...) {
  280.     clean_list(current, next_node);
  281.     alloc_traits::deallocate(alloc_, x_, 1);
  282.     throw;
  283.   }
  284.   head_ = x_->next;
  285.   tail_ = next_node;
  286.   set_ends();
  287. }
  288.  
  289. template <typename T, typename Allocator>
  290. void List<T, Allocator>::fill_list(std::initializer_list<T> init_list) {
  291.   Node* current = x_;
  292.   Node* next_node;
  293.   try {
  294.     for (auto iter = init_list.cbegin(); iter != init_list.cend(); ++iter) {
  295.       next_node = make_node(iter);
  296.       current->next = next_node;
  297.       next_node->prev = current;
  298.       current = next_node;
  299.     }
  300.   } catch (...) {
  301.     clean_list(current, next_node);
  302.     alloc_traits::deallocate(alloc_, x_, 1);
  303.     throw;
  304.   }
  305.   head_ = x_->next;
  306.   tail_ = next_node;
  307.   set_ends();
  308. }
  309.  
  310. /// -------------------------------Constructors---------------------------------
  311.  
  312. template <typename T, typename Allocator>
  313. List<T, Allocator>::List() {
  314.   x_ = alloc_traits::allocate(alloc_, 1);
  315.   x_->next = head_;
  316.   x_->prev = tail_;
  317. }
  318.  
  319. template <typename T, typename Allocator>
  320. List<T, Allocator>::List(size_t count, const T& value, const Allocator& alloc) {
  321.   size_ = count;
  322.   alloc_ = alloc;
  323.   x_ = alloc_traits::allocate(alloc_, 1);
  324.   x_->next = head_;
  325.   x_->prev = tail_;
  326.   fill_list(count, value);
  327. }
  328.  
  329. template <typename T, typename Allocator>
  330. List<T, Allocator>::List(size_t count, const Allocator& alloc) {
  331.   size_ = count;
  332.   alloc_ = alloc;
  333.   x_ = alloc_traits::allocate(alloc_, 1);
  334.   x_->next = head_;
  335.   x_->prev = tail_;
  336.   fill_list(count);
  337. }
  338. template <typename T, typename Allocator>
  339. List<T, Allocator>::List(const List& other) {
  340.   size_ = other.size_;
  341.   alloc_ = alloc_traits::select_on_container_copy_construction(other.alloc_);
  342.   x_ = alloc_traits::allocate(alloc_, 1);
  343.   x_->next = head_;
  344.   x_->prev = tail_;
  345.   fill_list(other);
  346. }
  347.  
  348. template <typename T, typename Allocator>
  349. List<T, Allocator>::List(List&& other) noexcept
  350.     : head_(std::move(other.head_))
  351.     , tail_(std::move(other.tail_))
  352.     , x_(std::move(other.x_))
  353.     , size_(other.size_)
  354.     , alloc_(std::move(other.alloc_)) {
  355.  
  356.   x_->next = head_;
  357.   x_->prev = tail_;
  358.   other.head_ = nullptr;
  359.   other.tail_ = nullptr;
  360.   other.size_ = 0;
  361. }
  362.  
  363. template <typename T, typename Allocator>
  364. List<T, Allocator>::List(std::initializer_list<value_type> init,
  365.                          const Allocator& alloc) {
  366.   size_ = init.size();
  367.   alloc_ = alloc;
  368.   x_ = alloc_traits::allocate(alloc_, 1);
  369.   x_->next = head_;
  370.   x_->prev = tail_;
  371.   fill_list(init);
  372. }
  373.  
  374. template <typename T, typename Allocator>
  375. List<T, Allocator>::~List() {
  376.   if (empty()) {
  377.     return;
  378.   }
  379.   clean_list(tail_->prev, tail_);
  380.   size_ = 0;
  381.   head_ = nullptr;
  382.   tail_ = nullptr;
  383.   x_->next = nullptr;
  384.   x_->prev = nullptr;
  385.   alloc_traits::deallocate(alloc_, x_, 1);
  386. }
  387.  
  388. /// -------------------------------Operators------------------------------------
  389.  
  390. template <typename T, typename Allocator>
  391. List<T, Allocator>& List<T, Allocator>::operator=(const List<T, Allocator>& other) {
  392.   if (this == &other) {
  393.     return *this;
  394.   }
  395.   clean_list(tail_->prev, tail_);
  396.   alloc_traits::destroy(alloc_, x_);
  397.   x_ = other.x_;
  398.   size_ = other.size_;
  399.   if (alloc_traits::propagate_on_container_copy_assignment::value && alloc_ != other.alloc_) {
  400.     alloc_ = other.alloc_;
  401.   }
  402.   fill_list(other);
  403.   return *this;
  404. }
  405.  
  406. template <typename T, typename Allocator>
  407. List<T, Allocator>& List<T, Allocator>::operator=(List<T, Allocator>&& other) noexcept {
  408.   List<T, Allocator> tmp = std::move(other);
  409.   std::swap(size_, tmp.size_);
  410.   std::swap(head_, tmp.head_);
  411.   std::swap(tail_, tmp.tail_);
  412.   std::swap(x_ , tmp.x_);
  413.   if (alloc_traits::propagate_on_container_move_assignment::value && alloc_ != tmp.alloc_) {
  414.     std::swap(alloc_, tmp.alloc_);
  415.   }
  416.   return *this;
  417. }
  418.  
  419.  
  420. /// -------------------------------Iterators------------------------------------
  421.  
  422. template <typename T>
  423. T ListIterator<T>::operator*() const {
  424.   return node_p_->value;
  425. }
  426.  
  427. template <typename T>
  428. T* ListIterator<T>::operator->() const {
  429.   return &(node_p_->value);
  430. }
  431.  
  432. template <typename T>
  433. ListIterator<T>& ListIterator<T>::operator++() {
  434.   node_p_ = node_p_->next;
  435.   return *this;
  436. }
  437.  
  438. template <typename T>
  439. ListIterator<T>& ListIterator<T>::operator--() {
  440.   node_p_ = node_p_->prev;
  441.   return *this;
  442. }
  443.  
  444. template <typename T>
  445. bool ListIterator<T>::operator==(const ListIterator& other) {
  446.   return node_p_ == other.node_p_;
  447. }
  448.  
  449. template <typename T>
  450. bool ListIterator<T>::operator!=(const ListIterator& other) {
  451.   return node_p_ != other.node_p_;
  452. }
  453.  
  454. template <typename T, typename Allocator>
  455. typename List<T, Allocator>::iterator List<T, Allocator>::begin() const {
  456.   if (head_ == nullptr) {
  457.     return List::iterator(x_);
  458.   }
  459.   return List::iterator(head_);
  460. }
  461.  
  462. template <typename T, typename Allocator>
  463. typename List<T, Allocator>::const_iterator List<T, Allocator>::cbegin() const {
  464.   if (head_ == nullptr) {
  465.     return List::const_iterator(x_);
  466.   }
  467.   return List::const_iterator(head_);
  468. }
  469.  
  470. template <typename T, typename Allocator>
  471. typename List<T, Allocator>::iterator List<T, Allocator>::end() const{
  472.   return List::iterator(x_);
  473. }
  474.  
  475. template <typename T, typename Allocator>
  476. typename List<T, Allocator>::const_iterator List<T, Allocator>::cend() const{
  477.   return List::const_iterator(x_);
  478. }
  479.  
  480. /// -----------------------Element access methods-------------------------------
  481.  
  482. template <typename T, typename Allocator>
  483. T& List<T, Allocator>::front() {
  484.   return head_->value;
  485. }
  486.  
  487. template <typename T, typename Allocator>
  488. const T& List<T, Allocator>::front() const{
  489.   return head_->value;
  490. }
  491.  
  492. template <typename T, typename Allocator>
  493. T& List<T, Allocator>::back() {
  494.   return tail_->value;
  495. }
  496.  
  497. template <typename T, typename Allocator>
  498. const T& List<T, Allocator>::back() const{
  499.   return tail_->value;
  500. }
  501.  
  502. /// ------------------------------Modifiers-------------------------------------
  503.  
  504. template <typename T, typename Allocator>
  505. template <typename... Args>
  506. void List<T, Allocator>::emplace_back(Args&& ...args) {
  507.   Node* next_node = nullptr;
  508.   try {
  509.     next_node = make_node(alloc_, std::forward<Args>(args)...);
  510.   } catch (...) {
  511.     alloc_traits::destroy(alloc_, next_node);
  512.     alloc_traits::deallocate(alloc_, next_node, 1);
  513.     alloc_traits::deallocate(alloc_, x_, 1);
  514.     throw;
  515.   }
  516.   if (empty()) {
  517.     head_ = next_node;
  518.     tail_ = next_node;
  519.     set_ends();
  520.     return;
  521.   }
  522.   Node* x_prev = x_->prev;
  523.   x_prev->next = next_node;
  524.   tail_ = next_node;
  525.   x_->prev = next_node;
  526.   next_node->prev = x_prev;
  527.   next_node->next = x_;
  528. }
  529.  
  530. template <typename T, typename Allocator>
  531. template <typename ...Args>
  532. void List<T, Allocator>::emplace_front(Args&& ...args) {
  533.   Node* next_node;
  534.   try {
  535.     next_node = make_node(alloc_, std::forward(args)...);
  536.   } catch (...) {
  537.     alloc_traits::destroy(alloc_, next_node);
  538.     alloc_traits::deallocate(alloc_, next_node, 1);
  539.     alloc_traits::deallocate(alloc_, x_, 1);
  540.     throw;
  541.   }
  542.   if (empty()) {
  543.     head_ = next_node;
  544.     tail_ = next_node;
  545.     set_ends();
  546.     return;
  547.   }
  548.   Node* head_prev = head_;
  549.   x_->next = next_node;
  550.   head_ = next_node;
  551.   head_prev->prev = next_node;
  552.   next_node->prev = x_;
  553.   next_node->next = head_prev;
  554. }
  555.  
  556.  
  557. int main() {
  558.   List<int> list1(5, 1);
  559.   List<int> list2(3);
  560.   list1.emplace_back(5);
  561.   for (auto i : list1) {
  562.     std::cout << i << ' ';
  563.   }
  564. }
Advertisement
RAW Paste Data Copied
Advertisement