API tools faq
paste
shushus

Спринт 14. Реализация методов Insert, Emplace и Erase.

shushus
May 5th, 2023
808
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 30.55 KB | None | 0 0
raw download clone embed print report
  1. -----------------------------------------------------------------------
  2. vector.h
  3. -----------------------------------------------------------------------
  4. #pragma once
  5. #include <cassert>
  6. #include <memory>
  7. #include <algorithm>
  8. #include <cstdlib>
  9. #include <new>
  10. #include <utility>
  11. #include <iterator>
  12.  
  13. template <typename T>
  14. class RawMemory {
  15. public:
  16.     RawMemory() = default;
  17.  
  18.     explicit RawMemory(size_t capacity) : buffer_(Allocate(capacity))
  19.                                         , capacity_(capacity) {}
  20.  
  21.     ~RawMemory() {Deallocate(buffer_);}
  22.    
  23.     RawMemory(const RawMemory&) = delete;
  24.     RawMemory& operator=(const RawMemory& rhs) = delete;
  25.    
  26.     RawMemory(RawMemory&& other) noexcept : buffer_(std::exchange(other.buffer_, nullptr))
  27.                                           , capacity_(std::exchange(other.capacity_, 0)) {}
  28.  
  29.     RawMemory& operator=(RawMemory&& rhs) noexcept {
  30.        
  31.         if (this != &rhs) {
  32.             buffer_ = std::move(rhs.buffer_);
  33.             capacity_ = std::move(rhs.capacity_);
  34.             rhs.buffer_ = nullptr;
  35.             rhs.capacity_ = 0;
  36.         }
  37.        
  38.         return *this;
  39.     }
  40.  
  41.     T* operator+(size_t offset) noexcept {assert(offset <= capacity_); return buffer_ + offset;}
  42.     const T* operator+(size_t offset) const noexcept {return const_cast<RawMemory&>(*this) + offset;}
  43.  
  44.     const T& operator[](size_t index) const noexcept {return const_cast<RawMemory&>(*this)[index];}
  45.     T& operator[](size_t index) noexcept {assert(index < capacity_); return buffer_[index];}
  46.  
  47.     void Swap(RawMemory& other) noexcept {std::swap(buffer_, other.buffer_); std::swap(capacity_, other.capacity_);}
  48.  
  49.     const T* GetAddress() const noexcept {return buffer_;}
  50.     T* GetAddress() noexcept {return buffer_;}
  51.     size_t Capacity() const {return capacity_;}
  52.  
  53. private:
  54.     T* buffer_ = nullptr;
  55.     size_t capacity_ = 0;
  56.    
  57.     static T* Allocate(size_t n) {return n != 0 ? static_cast<T*>(operator new(n * sizeof(T))) : nullptr;}
  58.     static void Deallocate(T* buf) noexcept {operator delete(buf);}
  59. };
  60.  
  61. template <typename T>
  62. class Vector {
  63. public:
  64.    
  65.     using iterator = T*;
  66.     using const_iterator = const T*;
  67.    
  68.     Vector() = default;
  69.  
  70.     explicit Vector(size_t size) : data_(size)
  71.                                  , size_(size) {std::uninitialized_value_construct_n(data_.GetAddress(), size);}
  72.    
  73.     Vector(const Vector& other) : data_(other.size_)
  74.                                 , size_(other.size_) {std::uninitialized_copy_n(other.data_.GetAddress(), size_, data_.GetAddress());}
  75.    
  76.     Vector(Vector&& other) noexcept : data_(std::move(other.data_))
  77.                                     , size_(std::exchange(other.size_, 0)) {}
  78.    
  79.     ~Vector() {std::destroy_n(data_.GetAddress(), size_);}
  80.    
  81.     iterator begin() noexcept {return data_.GetAddress();}
  82.     iterator end() noexcept {return size_ + data_.GetAddress();}
  83.     const_iterator cbegin() const noexcept {return data_.GetAddress();}
  84.     const_iterator cend() const noexcept {return size_ + data_.GetAddress();}
  85.     const_iterator begin() const noexcept {return cbegin();}
  86.     const_iterator end() const noexcept {return cend();}
  87.    
  88.     size_t Size() const noexcept {return size_;}
  89.     size_t Capacity() const noexcept {return data_.Capacity();}
  90.     void Swap(Vector& other) noexcept {data_.Swap(other.data_), std::swap(size_, other.size_);}
  91.    
  92.     void Reserve(size_t new_capacity) {
  93.        
  94.         if (new_capacity <= data_.Capacity()) {
  95.             return;
  96.         }
  97.        
  98.         RawMemory<T> new_data(new_capacity);
  99.        
  100.         if constexpr (std::is_nothrow_move_constructible_v<T> || !std::is_copy_constructible_v<T>) {
  101.             std::uninitialized_move_n(data_.GetAddress(), size_, new_data.GetAddress());
  102.         } else {
  103.             std::uninitialized_copy_n(data_.GetAddress(), size_, new_data.GetAddress());
  104.         }
  105.        
  106.         std::destroy_n(data_.GetAddress(), size_);
  107.         data_.Swap(new_data);
  108.     }
  109.  
  110.     void Resize(size_t new_size) {
  111.        
  112.         if (new_size < size_) {
  113.             std::destroy_n(data_.GetAddress() + new_size, size_ - new_size);
  114.            
  115.         } else {
  116.            
  117.             if (new_size > data_.Capacity()) {
  118.                 const size_t new_capacity = std::max(data_.Capacity() * 2, new_size);
  119.                
  120.                 Reserve(new_capacity);
  121.             }
  122.            
  123.             std::uninitialized_value_construct_n(data_.GetAddress() + size_, new_size - size_);
  124.         }
  125.        
  126.         size_ = new_size;
  127.     }
  128.    
  129.     template <typename... Args>
  130.     T& EmplaceBack(Args&&... args);
  131.    
  132.     template <typename... Args>
  133.     iterator Emplace(const_iterator pos, Args&&... args);
  134.  
  135.     iterator Insert(const_iterator pos, const T& item) {return Emplace(pos, item);}
  136.     iterator Insert(const_iterator pos, T&& item) {return Emplace(pos, std::move(item));}
  137.    
  138.     iterator Erase(const_iterator pos) {
  139.        
  140.         assert(pos >= begin() && pos <= end());          
  141.         int position = pos - begin();
  142.  
  143.         std::move(begin() + position + 1, end(), begin() + position);
  144.         std::destroy_at(end() - 1);
  145.         size_-=1;
  146.  
  147.         return (begin() + position);
  148.     }
  149.    
  150.     template <typename Type>
  151.     void PushBack(Type&& value);
  152.  
  153.     void PopBack() {
  154.         assert(size_);
  155.         std::destroy_at(data_.GetAddress() + size_ - 1);
  156.         --size_;
  157.     }
  158.    
  159.     Vector& operator=(const Vector& other) {
  160.        
  161.         if (this != &other) {
  162.            
  163.             if (other.size_ <= data_.Capacity()) {
  164.                
  165.                 if (size_ <= other.size_) {
  166.                    
  167.                     std::copy(other.data_.GetAddress(),
  168.                               other.data_.GetAddress() + size_,
  169.                               data_.GetAddress());
  170.                    
  171.                     std::uninitialized_copy_n(other.data_.GetAddress() + size_,
  172.                                               other.size_ - size_,
  173.                                               data_.GetAddress() + size_);
  174.                 } else {
  175.                    
  176.                     std::copy(other.data_.GetAddress(),
  177.                               other.data_.GetAddress() + other.size_,
  178.                               data_.GetAddress());
  179.                    
  180.                     std::destroy_n(data_.GetAddress() + other.size_,
  181.                                    size_ - other.size_);
  182.                 }
  183.                
  184.                 size_ = other.size_;
  185.                
  186.             } else {              
  187.                 Vector other_copy(other);
  188.                 Swap(other_copy);
  189.             }
  190.         }
  191.        
  192.         return *this;
  193.     }
  194.  
  195.     Vector& operator=(Vector&& other) noexcept {Swap(other); return *this;}
  196.    
  197.     const T& operator[](size_t index) const noexcept {return const_cast<Vector&>(*this)[index];}
  198.     T& operator[](size_t index) noexcept {assert(index < size_); return data_[index];}
  199.  
  200. private:
  201.     RawMemory<T> data_;
  202.     size_t size_ = 0;
  203. };
  204.  
  205. template <typename T>
  206. template <typename Type>
  207. void Vector<T>::PushBack(Type&& value) {
  208.  
  209.     if (data_.Capacity() <= size_) {
  210.    
  211.         RawMemory<T> new_data(size_ == 0 ? 1 : size_ * 2);
  212.        
  213.         new (new_data.GetAddress() + size_) T(std::forward<Type>(value));
  214.        
  215.         if constexpr (std::is_nothrow_move_constructible_v<T> || !std::is_copy_constructible_v<T>) {
  216.             std::uninitialized_move_n(data_.GetAddress(), size_, new_data.GetAddress());
  217.         } else {
  218.             std::uninitialized_copy_n(data_.GetAddress(), size_, new_data.GetAddress());
  219.         }
  220.        
  221.         std::destroy_n(data_.GetAddress(), size_);
  222.         data_.Swap(new_data);
  223.        
  224.     } else {
  225.         new (data_.GetAddress() + size_) T(std::forward<Type>(value));
  226.     }
  227.    
  228.     size_++;
  229. }
  230.  
  231. template <typename T>
  232. template <typename... Args>
  233. T& Vector<T>::EmplaceBack(Args&&... args) {
  234.  
  235.     if (data_.Capacity() <= size_) {
  236.  
  237.         RawMemory<T> new_data(size_ == 0 ? 1 : size_ * 2);
  238.  
  239.         new (new_data.GetAddress() + size_) T(std::forward<Args>(args)...);
  240.  
  241.         if constexpr (std::is_nothrow_move_constructible_v<T> || !std::is_copy_constructible_v<T>) {
  242.             std::uninitialized_move_n(data_.GetAddress(), size_, new_data.GetAddress());
  243.         } else {
  244.             std::uninitialized_copy_n(data_.GetAddress(), size_, new_data.GetAddress());
  245.         }
  246.  
  247.         std::destroy_n(data_.GetAddress(), size_);
  248.         data_.Swap(new_data);
  249.  
  250.     } else {
  251.         new (data_.GetAddress() + size_) T(std::forward<Args>(args)...);
  252.     }
  253.  
  254.     return data_[size_++];
  255. }
  256.  
  257. template <typename T>
  258. template <typename... Args>
  259. typename Vector<T>::iterator Vector<T>::Emplace(const_iterator pos, Args&&... args) {
  260.     assert(pos >= begin() && pos <= end());    
  261.     int position = pos - begin();
  262.  
  263.     if (data_.Capacity() <= size_) {
  264.            
  265.         RawMemory<T> new_data(size_ == 0 ? 1 : size_ * 2);
  266.            
  267.         new (new_data.GetAddress() + position) T(std::forward<Args>(args)...);
  268.  
  269.         if constexpr (std::is_nothrow_move_constructible_v<T> || !std::is_copy_constructible_v<T>) {
  270.             std::uninitialized_move_n(data_.GetAddress(), position, new_data.GetAddress());
  271.             std::uninitialized_move_n(data_.GetAddress() + position, size_ - position, new_data.GetAddress() + position + 1);
  272.            
  273.         } else {
  274.             std::uninitialized_copy_n(data_.GetAddress(), position, new_data.GetAddress());
  275.             std::uninitialized_copy_n(data_.GetAddress() + position, size_ - position, new_data.GetAddress() + position + 1);
  276.         }
  277.  
  278.         std::destroy_n(data_.GetAddress(), size_);
  279.         data_.Swap(new_data);
  280.            
  281.     } else {
  282.            
  283.         try {
  284.                
  285.             if (pos != end()) {
  286.                    
  287.                 T new_s(std::forward<Args>(args)...);                  
  288.                 new (end()) T(std::forward<T>(data_[size_ - 1]));
  289.                    
  290.                 std::move_backward(begin() + position, end() - 1, end());                  
  291.                 *(begin() + position) = std::forward<T>(new_s);
  292.                    
  293.             } else {
  294.                 new (end()) T(std::forward<Args>(args)...);
  295.             }
  296.                
  297.         } catch (...) {
  298.             operator delete (end());
  299.             throw;
  300.         }
  301.     }
  302.        
  303.     size_++;
  304.     return begin() + position;
  305. }
  306. -----------------------------------------------------------------------
  307. main.cpp
  308. -----------------------------------------------------------------------
  309. #include "vector.h"
  310.  
  311. #include <iostream>
  312. #include <stdexcept>
  313. #include <string>
  314.  
  315. namespace {
  316.  
  317. inline const uint32_t DEFAULT_COOKIE = 0xdeadbeef;
  318.  
  319. struct TestObj {
  320.    
  321.     TestObj() = default;
  322.     TestObj(const TestObj& other) = default;
  323.     TestObj& operator=(const TestObj& other) = default;
  324.     TestObj(TestObj&& other) = default;
  325.     TestObj& operator=(TestObj&& other) = default;
  326.    
  327.     ~TestObj() {cookie = 0;}
  328.    
  329.     [[nodiscard]] bool IsAlive() const noexcept {return cookie == DEFAULT_COOKIE;}
  330.    
  331.     uint32_t cookie = DEFAULT_COOKIE;
  332. };
  333.  
  334. struct Obj {
  335.    
  336.     Obj() {
  337.        
  338.         if (default_construction_throw_countdown > 0) {
  339.            
  340.             if (--default_construction_throw_countdown == 0) {
  341.                 throw std::runtime_error("Oops");
  342.             }
  343.         }
  344.        
  345.         ++num_default_constructed;
  346.     }
  347.  
  348.     explicit Obj(int id) : id(id) {++num_constructed_with_id;}
  349.  
  350.     Obj(int id, std::string name) : id(id)
  351.                                   , name(std::move(name)) {++num_constructed_with_id_and_name;}
  352.  
  353.     Obj(const Obj& other) : id(other.id) {
  354.        
  355.         if (other.throw_on_copy) {
  356.             throw std::runtime_error("Oops");
  357.         }
  358.        
  359.         ++num_copied;
  360.     }
  361.  
  362.     Obj(Obj&& other) noexcept : id(other.id) {++num_moved;}
  363.  
  364.     Obj& operator=(const Obj& other) {
  365.        
  366.         if (this != &other) {
  367.             id = other.id;
  368.             name = other.name;
  369.             ++num_assigned;
  370.         }
  371.        
  372.         return *this;
  373.     }
  374.  
  375.     Obj& operator=(Obj&& other) noexcept {
  376.         id = other.id;
  377.         name = std::move(other.name);
  378.         ++num_move_assigned;
  379.        
  380.         return *this;
  381.     }
  382.  
  383.     ~Obj() {++num_destroyed; id = 0;}
  384.  
  385.     static int GetAliveObjectCount() {
  386.        
  387.         return num_default_constructed
  388.                + num_copied
  389.                + num_moved
  390.                + num_constructed_with_id
  391.                + num_constructed_with_id_and_name
  392.                - num_destroyed;
  393.     }
  394.  
  395.     static void ResetCounters() {
  396.         default_construction_throw_countdown = 0;
  397.         num_default_constructed = 0;
  398.         num_copied = 0;
  399.         num_moved = 0;
  400.         num_destroyed = 0;
  401.         num_constructed_with_id = 0;
  402.         num_constructed_with_id_and_name = 0;
  403.         num_assigned = 0;
  404.         num_move_assigned = 0;
  405.     }
  406.  
  407.     bool throw_on_copy = false;
  408.     int id = 0;
  409.     std::string name;
  410.  
  411.     static inline int default_construction_throw_countdown = 0;
  412.     static inline int num_default_constructed = 0;
  413.     static inline int num_constructed_with_id = 0;
  414.     static inline int num_constructed_with_id_and_name = 0;
  415.     static inline int num_copied = 0;
  416.     static inline int num_moved = 0;
  417.     static inline int num_destroyed = 0;
  418.     static inline int num_assigned = 0;
  419.     static inline int num_move_assigned = 0;
  420. };
  421.  
  422. }//end namespace
  423.  
  424. void Test1() {
  425.    
  426.     Obj::ResetCounters();
  427.    
  428.     const size_t SIZE = 100500;
  429.     const size_t INDEX = 10;
  430.     const int MAGIC = 42;
  431.    
  432.     {
  433.         Vector<int> v;
  434.        
  435.         assert(v.Capacity() == 0);
  436.         assert(v.Size() == 0);
  437.  
  438.         v.Reserve(SIZE);
  439.        
  440.         assert(v.Capacity() == SIZE);
  441.         assert(v.Size() == 0);
  442.     }
  443.    
  444.     {
  445.         Vector<int> v(SIZE);
  446.        
  447.         const auto& cv(v);
  448.         assert(v.Capacity() == SIZE);
  449.         assert(v.Size() == SIZE);
  450.         assert(v[0] == 0);
  451.         assert(&v[0] == &cv[0]);
  452.        
  453.         v[INDEX] = MAGIC;
  454.        
  455.         assert(v[INDEX] == MAGIC);
  456.         assert(&v[100] - &v[0] == 100);
  457.  
  458.         v.Reserve(SIZE * 2);
  459.        
  460.         assert(v.Size() == SIZE);
  461.         assert(v.Capacity() == SIZE * 2);
  462.         assert(v[INDEX] == MAGIC);
  463.     }
  464.    
  465.     {
  466.         Vector<int> v(SIZE);
  467.        
  468.         v[INDEX] = MAGIC;
  469.        
  470.         const auto v_copy(v);
  471.         assert(&v[INDEX] != &v_copy[INDEX]);
  472.         assert(v[INDEX] == v_copy[INDEX]);
  473.     }
  474.    
  475.     {
  476.         Vector<Obj> v;
  477.        
  478.         v.Reserve(SIZE);
  479.        
  480.         assert(Obj::GetAliveObjectCount() == 0);
  481.     }
  482.    
  483.     {
  484.         Vector<Obj> v(SIZE);
  485.        
  486.         assert(Obj::GetAliveObjectCount() == SIZE);
  487.        
  488.         const int old_copy_count = Obj::num_copied;
  489.         const int old_move_count = Obj::num_moved;
  490.        
  491.         v.Reserve(SIZE * 2);
  492.        
  493.         assert(Obj::GetAliveObjectCount() == SIZE);
  494.         assert(Obj::num_copied == old_copy_count);
  495.         assert(Obj::num_moved == old_move_count + static_cast<int>(SIZE));
  496.     }
  497.    
  498.     assert(Obj::GetAliveObjectCount() == 0);
  499. }
  500.  
  501. void Test2() {
  502.     const size_t SIZE = 100;
  503.    
  504.     Obj::ResetCounters();
  505.    
  506.     {
  507.         Obj::default_construction_throw_countdown = SIZE / 2;
  508.         try {
  509.             Vector<Obj> v(SIZE);
  510.             assert(false && "Exception is expected");
  511.            
  512.         } catch (const std::runtime_error&) {
  513.            
  514.         } catch (...) {
  515.             assert(false && "Unexpected exception");
  516.         }
  517.        
  518.         assert(Obj::num_default_constructed == SIZE / 2 - 1);
  519.         assert(Obj::GetAliveObjectCount() == 0);
  520.     }
  521.    
  522.     Obj::ResetCounters();
  523.    
  524.     {
  525.         Vector<Obj> v(SIZE);
  526.        
  527.         try {
  528.             v[SIZE / 2].throw_on_copy = true;
  529.             Vector<Obj> v_copy(v);
  530.             assert(false && "Exception is expected");
  531.            
  532.         } catch (const std::runtime_error&) {
  533.             assert(Obj::num_copied == SIZE / 2);
  534.            
  535.         } catch (...) {
  536.             assert(false && "Unexpected exception");
  537.         }
  538.        
  539.         assert(Obj::GetAliveObjectCount() == SIZE);
  540.     }
  541.    
  542.     Obj::ResetCounters();
  543.    
  544.     {
  545.         Vector<Obj> v(SIZE);
  546.        
  547.         try {
  548.             v[SIZE - 1].throw_on_copy = true;
  549.             v.Reserve(SIZE * 2);
  550.            
  551.         } catch (...) {
  552.             assert(false && "Unexpected exception");
  553.         }
  554.        
  555.         assert(v.Capacity() == SIZE * 2);
  556.         assert(v.Size() == SIZE);
  557.         assert(Obj::GetAliveObjectCount() == SIZE);
  558.     }
  559. }
  560.  
  561. void Test3() {
  562.     const size_t MEDIUM_SIZE = 100;
  563.     const size_t LARGE_SIZE = 250;
  564.     const int ID = 42;
  565.    
  566.     {
  567.         Obj::ResetCounters();
  568.        
  569.         Vector<int> v(MEDIUM_SIZE);
  570.        
  571.         {
  572.             auto v_copy(std::move(v));
  573.  
  574.             assert(v_copy.Size() == MEDIUM_SIZE);
  575.             assert(v_copy.Capacity() == MEDIUM_SIZE);
  576.         }
  577.        
  578.         assert(Obj::GetAliveObjectCount() == 0);
  579.     }
  580.    
  581.     {
  582.         Obj::ResetCounters();
  583.        
  584.         {
  585.             Vector<Obj> v(MEDIUM_SIZE);
  586.            
  587.             v[MEDIUM_SIZE / 2].id = ID;
  588.            
  589.             assert(Obj::num_default_constructed == MEDIUM_SIZE);
  590.            
  591.             Vector<Obj> moved_from_v(std::move(v));
  592.            
  593.             assert(moved_from_v.Size() == MEDIUM_SIZE);
  594.             assert(moved_from_v[MEDIUM_SIZE / 2].id == ID);
  595.         }
  596.        
  597.         assert(Obj::GetAliveObjectCount() == 0);
  598.  
  599.         assert(Obj::num_moved == 0);
  600.         assert(Obj::num_copied == 0);
  601.         assert(Obj::num_default_constructed == MEDIUM_SIZE);
  602.     }
  603.    
  604.     {
  605.         Obj::ResetCounters();
  606.        
  607.         Vector<Obj> v_medium(MEDIUM_SIZE);
  608.        
  609.         v_medium[MEDIUM_SIZE / 2].id = ID;
  610.        
  611.         Vector<Obj> v_large(LARGE_SIZE);
  612.        
  613.         v_large = v_medium;
  614.        
  615.         assert(v_large.Size() == MEDIUM_SIZE);
  616.         assert(v_large.Capacity() == LARGE_SIZE);
  617.         assert(v_large[MEDIUM_SIZE / 2].id == ID);
  618.         assert(Obj::GetAliveObjectCount() == MEDIUM_SIZE + MEDIUM_SIZE);
  619.     }
  620.    
  621.     {
  622.         Obj::ResetCounters();
  623.        
  624.         Vector<Obj> v(MEDIUM_SIZE);
  625.        
  626.         {
  627.             Vector<Obj> v_large(LARGE_SIZE);
  628.            
  629.             v_large[LARGE_SIZE - 1].id = ID;
  630.             v = v_large;
  631.            
  632.             assert(v.Size() == LARGE_SIZE);
  633.             assert(v_large.Capacity() == LARGE_SIZE);
  634.             assert(v_large[LARGE_SIZE - 1].id == ID);
  635.             assert(Obj::GetAliveObjectCount() == LARGE_SIZE + LARGE_SIZE);
  636.         }
  637.        
  638.         assert(Obj::GetAliveObjectCount() == LARGE_SIZE);
  639.     }
  640.    
  641.     assert(Obj::GetAliveObjectCount() == 0);
  642.    
  643.     {
  644.         Obj::ResetCounters();
  645.        
  646.         Vector<Obj> v(MEDIUM_SIZE);
  647.        
  648.         v[MEDIUM_SIZE - 1].id = ID;
  649.        
  650.         Vector<Obj> v_small(MEDIUM_SIZE / 2);
  651.         v_small.Reserve(MEDIUM_SIZE + 1);
  652.        
  653.         const size_t num_copies = Obj::num_copied;
  654.         v_small = v;
  655.        
  656.         assert(v_small.Size() == v.Size());
  657.         assert(v_small.Capacity() == MEDIUM_SIZE + 1);
  658.        
  659.         v_small[MEDIUM_SIZE - 1].id = ID;
  660.        
  661.         assert(Obj::num_copied - num_copies == MEDIUM_SIZE - (MEDIUM_SIZE / 2));
  662.     }
  663. }
  664.  
  665. void Test4() {
  666.     const size_t ID = 42;
  667.     const size_t SIZE = 100'500;
  668.    
  669.    {
  670.        Obj::ResetCounters();
  671.        
  672.        Vector<Obj> v;
  673.        
  674.        v.Resize(SIZE);
  675.        
  676.        assert(v.Size() == SIZE);
  677.        assert(v.Capacity() == SIZE);
  678.        assert(Obj::num_default_constructed == SIZE);
  679.    }
  680.    
  681.    assert(Obj::GetAliveObjectCount() == 0);
  682.  
  683.    {
  684.        const size_t NEW_SIZE = 10'000;
  685.        
  686.         Obj::ResetCounters();
  687.        
  688.         Vector<Obj> v(SIZE);
  689.        
  690.         v.Resize(NEW_SIZE);
  691.        
  692.         assert(v.Size() == NEW_SIZE);
  693.         assert(v.Capacity() == SIZE);
  694.         assert(Obj::num_destroyed == SIZE - NEW_SIZE);
  695.     }
  696.    
  697.     assert(Obj::GetAliveObjectCount() == 0);
  698.    
  699.     {
  700.         Obj::ResetCounters();
  701.        
  702.         Vector<Obj> v(SIZE);
  703.        
  704.         Obj o{ID};
  705.        
  706.         v.PushBack(o);
  707.        
  708.         assert(v.Size() == SIZE + 1);
  709.         assert(v.Capacity() == SIZE * 2);
  710.         assert(v[SIZE].id == ID);
  711.         assert(Obj::num_default_constructed == SIZE);
  712.         assert(Obj::num_copied == 1);
  713.         assert(Obj::num_constructed_with_id == 1);
  714.         assert(Obj::num_moved == SIZE);
  715.     }
  716.    
  717.     assert(Obj::GetAliveObjectCount() == 0);
  718.    
  719.     {
  720.         Obj::ResetCounters();
  721.        
  722.         Vector<Obj> v(SIZE);
  723.        
  724.         v.PushBack(Obj{ID});
  725.        
  726.         assert(v.Size() == SIZE + 1);
  727.         assert(v.Capacity() == SIZE * 2);
  728.         assert(v[SIZE].id == ID);
  729.         assert(Obj::num_default_constructed == SIZE);
  730.         assert(Obj::num_copied == 0);
  731.         assert(Obj::num_constructed_with_id == 1);
  732.         assert(Obj::num_moved == SIZE + 1);
  733.     }
  734.    
  735.     {
  736.         Obj::ResetCounters();
  737.        
  738.         Vector<Obj> v;
  739.        
  740.         v.PushBack(Obj{ID});
  741.        
  742.         v.PopBack();
  743.        
  744.         assert(v.Size() == 0);
  745.         assert(v.Capacity() == 1);
  746.         assert(Obj::GetAliveObjectCount() == 0);
  747.     }
  748.  
  749.     {
  750.         Vector<TestObj> v(1);
  751.        
  752.         assert(v.Size() == v.Capacity());
  753.  
  754.         v.PushBack(v[0]);
  755.         assert(v[0].IsAlive());
  756.         assert(v[1].IsAlive());
  757.     }
  758.     {
  759.         Vector<TestObj> v(1);
  760.        
  761.         assert(v.Size() == v.Capacity());
  762.  
  763.         v.PushBack(std::move(v[0]));
  764.         assert(v[0].IsAlive());
  765.         assert(v[1].IsAlive());
  766.     }
  767. }
  768.  
  769. void Test5() {
  770.     const int ID = 42;
  771.     using namespace std::literals;
  772.    
  773.     {
  774.         Obj::ResetCounters();
  775.        
  776.         Vector<Obj> v;
  777.        
  778.         auto& elem = v.EmplaceBack(ID, "Ivan"s);
  779.        
  780.         assert(v.Capacity() == 1);
  781.         assert(v.Size() == 1);
  782.         assert(&elem == &v[0]);
  783.         assert(v[0].id == ID);
  784.         assert(v[0].name == "Ivan"s);
  785.         assert(Obj::num_constructed_with_id_and_name == 1);
  786.         assert(Obj::GetAliveObjectCount() == 1);
  787.     }
  788.    
  789.     assert(Obj::GetAliveObjectCount() == 0);
  790.    
  791.     {
  792.         Vector<TestObj> v(1);
  793.        
  794.         assert(v.Size() == v.Capacity());
  795.  
  796.         v.EmplaceBack(v[0]);
  797.         assert(v[0].IsAlive());
  798.         assert(v[1].IsAlive());
  799.     }
  800. }
  801.  
  802. void Test6() {
  803.     using namespace std::literals;
  804.    
  805.     const size_t SIZE = 10;
  806.     const int ID = 42;
  807.    
  808.     {
  809.         Obj::ResetCounters();
  810.        
  811.         Vector<int> v(SIZE);
  812.        
  813.         const auto& cv(v);
  814.        
  815.         v.PushBack(1);
  816.        
  817.         assert(&*v.begin() == &v[0]);
  818.        
  819.         *v.begin() = 2;
  820.        
  821.         assert(v[0] == 2);
  822.         assert(v.end() - v.begin() == static_cast<std::ptrdiff_t>(v.Size()));
  823.         assert(v.begin() == cv.begin());
  824.         assert(v.end() == cv.end());
  825.         assert(v.cbegin() == cv.begin());
  826.         assert(v.cend() == cv.end());
  827.     }
  828.    
  829.     {
  830.         Obj::ResetCounters();
  831.        
  832.         Vector<Obj> v{SIZE};
  833.        
  834.         Obj obj{1};
  835.        
  836.         Vector<Obj>::iterator pos = v.Insert(v.cbegin() + 1, obj);
  837.        
  838.         assert(v.Size() == SIZE + 1);
  839.         assert(v.Capacity() == SIZE * 2);
  840.         assert(&*pos == &v[1]);
  841.         assert(v[1].id == obj.id);
  842.         assert(Obj::num_copied == 1);
  843.         assert(Obj::num_default_constructed == SIZE);
  844.         assert(Obj::GetAliveObjectCount() == SIZE + 2);
  845.     }
  846.    
  847.     {
  848.         Obj::ResetCounters();
  849.        
  850.         Vector<Obj> v;
  851.        
  852.         auto* pos = v.Emplace(v.end(), Obj{1});
  853.        
  854.         assert(v.Size() == 1);
  855.         assert(v.Capacity() >= v.Size());
  856.         assert(&*pos == &v[0]);
  857.         assert(Obj::num_moved == 1);
  858.         assert(Obj::num_constructed_with_id == 1);
  859.         assert(Obj::num_copied == 0);
  860.         assert(Obj::num_assigned == 0);
  861.         assert(Obj::num_move_assigned == 0);
  862.         assert(Obj::GetAliveObjectCount() == 1);
  863.     }
  864.    
  865.     {
  866.         Obj::ResetCounters();
  867.        
  868.         Vector<Obj> v;
  869.        
  870.         v.Reserve(SIZE);
  871.        
  872.         auto* pos = v.Emplace(v.end(), Obj{1});
  873.        
  874.         assert(v.Size() == 1);
  875.         assert(v.Capacity() >= v.Size());
  876.         assert(&*pos == &v[0]);
  877.         assert(Obj::num_moved == 1);
  878.         assert(Obj::num_constructed_with_id == 1);
  879.         assert(Obj::num_copied == 0);
  880.         assert(Obj::num_assigned == 0);
  881.         assert(Obj::num_move_assigned == 0);
  882.         assert(Obj::GetAliveObjectCount() == 1);
  883.     }
  884.    
  885.     {
  886.         Obj::ResetCounters();
  887.        
  888.         Vector<Obj> v{SIZE};
  889.        
  890.         Vector<Obj>::iterator pos = v.Insert(v.cbegin() + 1, Obj{1});
  891.        
  892.         assert(v.Size() == SIZE + 1);
  893.         assert(v.Capacity() == SIZE * 2);
  894.         assert(&*pos == &v[1]);
  895.         assert(v[1].id == 1);
  896.         assert(Obj::num_copied == 0);
  897.         assert(Obj::num_default_constructed == SIZE);
  898.         assert(Obj::GetAliveObjectCount() == SIZE + 1);
  899.     }
  900.     {
  901.         Vector<TestObj> v{SIZE};
  902.        
  903.         v.Insert(v.cbegin() + 2, v[0]);
  904.        
  905.         assert(std::all_of(v.begin(), v.end(), [](const TestObj& obj) {return obj.IsAlive();}));
  906.     }
  907.    
  908.     {
  909.         Vector<TestObj> v{SIZE};
  910.        
  911.         v.Insert(v.cbegin() + 2, std::move(v[0]));
  912.        
  913.         assert(std::all_of(v.begin(), v.end(), [](const TestObj& obj) {return obj.IsAlive();}));
  914.     }
  915.    
  916.     {
  917.         Vector<TestObj> v{SIZE};
  918.        
  919.         v.Emplace(v.cbegin() + 2, std::move(v[0]));
  920.        
  921.         assert(std::all_of(v.begin(), v.end(), [](const TestObj& obj) {return obj.IsAlive();}));
  922.     }
  923.    
  924.     {
  925.         Obj::ResetCounters();
  926.        
  927.         Vector<Obj> v{SIZE};
  928.        
  929.         auto* pos = v.Emplace(v.cbegin() + 1, ID, "Ivan"s);
  930.        
  931.         assert(v.Size() == SIZE + 1);
  932.         assert(v.Capacity() == SIZE * 2);
  933.         assert(&*pos == &v[1]);
  934.         assert(v[1].id == ID);
  935.         assert(v[1].name == "Ivan"s);
  936.         assert(Obj::num_copied == 0);
  937.         assert(Obj::num_default_constructed == SIZE);
  938.         assert(Obj::num_moved == SIZE);
  939.         assert(Obj::num_move_assigned == 0);
  940.         assert(Obj::num_assigned == 0);
  941.         assert(Obj::GetAliveObjectCount() == SIZE + 1);
  942.     }
  943.    
  944.     {
  945.         Obj::ResetCounters();
  946.        
  947.         Vector<Obj> v{SIZE};
  948.        
  949.         auto* pos = v.Emplace(v.cbegin() + v.Size(), ID, "Ivan"s);
  950.        
  951.         assert(v.Size() == SIZE + 1);
  952.         assert(v.Capacity() == SIZE * 2);
  953.         assert(&*pos == &v[SIZE]);
  954.         assert(v[SIZE].id == ID);
  955.         assert(v[SIZE].name == "Ivan"s);
  956.         assert(Obj::num_copied == 0);
  957.         assert(Obj::num_default_constructed == SIZE);
  958.         assert(Obj::num_moved == SIZE);
  959.         assert(Obj::num_move_assigned == 0);
  960.         assert(Obj::num_assigned == 0);
  961.         assert(Obj::GetAliveObjectCount() == SIZE + 1);
  962.     }
  963.    
  964.     {
  965.         Obj::ResetCounters();
  966.        
  967.         Vector<Obj> v{SIZE};
  968.        
  969.         v.Reserve(SIZE * 2);
  970.        
  971.         const int old_num_moved = Obj::num_moved;
  972.        
  973.         assert(v.Capacity() == SIZE * 2);
  974.        
  975.         auto* pos = v.Emplace(v.cbegin() + 3, ID, "Ivan"s);
  976.        
  977.         assert(v.Size() == SIZE + 1);
  978.         assert(&*pos == &v[3]);
  979.         assert(v[3].id == ID);
  980.         assert(v[3].name == "Ivan");
  981.         assert(Obj::num_copied == 0);
  982.         assert(Obj::num_default_constructed == SIZE);
  983.         assert(Obj::num_constructed_with_id_and_name == 1);
  984.         assert(Obj::num_moved == old_num_moved + 1);
  985.         assert(Obj::num_move_assigned == SIZE - 3);
  986.         assert(Obj::num_assigned == 0);
  987.     }
  988.    
  989.     {
  990.         Obj::ResetCounters();
  991.        
  992.         Vector<Obj> v{SIZE};
  993.        
  994.         v[2].id = ID;
  995.        
  996.         auto* pos = v.Erase(v.cbegin() + 1);
  997.        
  998.         assert((pos - v.begin()) == 1);
  999.         assert(v.Size() == SIZE - 1);
  1000.         assert(v.Capacity() == SIZE);
  1001.         assert(pos->id == ID);
  1002.         assert(Obj::num_copied == 0);
  1003.         assert(Obj::num_assigned == 0);
  1004.         assert(Obj::num_move_assigned == SIZE - 2);
  1005.         assert(Obj::num_moved == 0);
  1006.         assert(Obj::GetAliveObjectCount() == SIZE - 1);
  1007.     }
  1008. }
  1009.  
  1010. struct C {
  1011.     C() noexcept {++def_ctor;}
  1012.     C(const C& /*other*/) noexcept {++copy_ctor;}
  1013.     C(C&& /*other*/) noexcept {++move_ctor;}
  1014.    
  1015.     C& operator=(const C& other) noexcept {
  1016.        
  1017.         if (this != &other) {
  1018.             ++copy_assign;
  1019.         }
  1020.        
  1021.         return *this;
  1022.     }
  1023.    
  1024.     C& operator=(C&& /*other*/) noexcept {
  1025.         ++move_assign;
  1026.         return *this;
  1027.     }
  1028.    
  1029.     ~C() {++dtor;}
  1030.  
  1031.     static void Reset() {
  1032.         def_ctor = 0;
  1033.         copy_ctor = 0;
  1034.         move_ctor = 0;
  1035.         copy_assign = 0;
  1036.         move_assign = 0;
  1037.         dtor = 0;
  1038.     }
  1039.  
  1040.     inline static size_t def_ctor = 0;
  1041.     inline static size_t copy_ctor = 0;
  1042.     inline static size_t move_ctor = 0;
  1043.     inline static size_t copy_assign = 0;
  1044.     inline static size_t move_assign = 0;
  1045.     inline static size_t dtor = 0;
  1046. };
  1047.  
  1048. void Dump() {
  1049.     using namespace std;
  1050.    
  1051.     cerr << "Def ctors: "sv << C::def_ctor              
  1052.          << ", Copy ctors: "sv << C::copy_ctor          
  1053.          << ", Move ctors: "sv << C::move_ctor          
  1054.          << ", Copy assignments: "sv << C::copy_assign  
  1055.          << ", Move assignments: "sv << C::move_assign  
  1056.          << ", Dtors: "sv << C::dtor << endl;
  1057. }
  1058.  
  1059. void Benchmark() {
  1060.     using namespace std;
  1061.    
  1062.     try {
  1063.         const size_t NUM = 10;
  1064.         C c;
  1065.        
  1066.         {
  1067.             cerr << "std::vector:"sv << endl;
  1068.             C::Reset();
  1069.             vector<C> v(NUM);
  1070.             Dump();
  1071.             v.push_back(c);
  1072.         }
  1073.        
  1074.         Dump();
  1075.        
  1076.     } catch (...) {}
  1077.    
  1078.     try {
  1079.         const size_t NUM = 10;
  1080.         C c;
  1081.        
  1082.         {
  1083.             cerr << "Vector:"sv << endl;
  1084.             C::Reset();
  1085.             Vector<C> v(NUM);
  1086.             Dump();
  1087.             v.PushBack(c);
  1088.         }
  1089.        
  1090.         Dump();
  1091.        
  1092.     } catch (...) {}
  1093. }
  1094.  
  1095. int main() {
  1096.    
  1097.     try {
  1098.         Test1();
  1099.         Test2();
  1100.         Test3();
  1101.         Test4();
  1102.         Test5();
  1103.         Test6();
  1104.         Benchmark();
  1105.        
  1106.     } catch (const std::exception& e) {
  1107.         std::cerr << e.what() << std::endl;
  1108.     }
  1109. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
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!