API tools faq
paste
Advertisement
Kirixh

Untitled

Kirixh
May 21st, 2022
1,861
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 14.24 KB | None | 0 0
raw download clone embed print report
  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
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!