ulfben

Container 2020 day 2 (refactoring II)

Nov 22nd, 2020 (edited)
795
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. Did some reading and tried to separate the lifetime of the data buffer from the lifetimes of the Ts *in* the buffer.
  3. Ergo: create an uninitialized block of memory and manually construct / destruct the Ts inside of it as needed.
  4.  
  5. Helpful resources:
  6. https://codereview.stackexchange.com/questions/211241/simple-re-implementation-of-stdvector
  7. https://lokiastari.com/blog/2016/02/27/vector/index.html
  8. https://lokiastari.com/blog/2016/02/29/vector-resource-management-ii-copy-assignment/index.html
  9. */
  10. #pragma once
  11. #include <algorithm>
  12. #include <memory>
  13. #include <cassert>
  14. #include <stdexcept>
  15. namespace API {
  16. template <typename T>
  17. class Container {
  18. public:
  19.     using pointer = T*;
  20.     using const_pointer = const T*;
  21.     using iterator = T*;
  22.     using const_iterator = const T*;
  23.     using value_type = T;
  24.     using size_type = std::size_t;
  25.     using reference = T&;
  26.     using const_reference = const T&;
  27.  
  28.     Container() = default;
  29.     ~Container()
  30.     {
  31.         clear();
  32.         ::operator delete(_data);
  33.     }
  34.     explicit Container(size_type capacity)
  35.         : _data(static_cast<pointer>(::operator new(sizeof(value_type) * capacity)))
  36.         , _count(0)
  37.         , _capacity(capacity)
  38.     {
  39.         //STL behavior is to fill with defaulted-Ts.
  40.         //I'm ignoring that tradition in ordet to delegate to this construction without paying for double-constructions.
  41.     }
  42.        
  43.     Container(size_type count, const T& val)
  44.         : Container(count)
  45.     {
  46.         std::uninitialized_fill_n(begin(), count, val); // copy construct each element w/ placement new
  47.         _count = count;
  48.     }
  49.  
  50.     //range construction
  51.     Container(const_iterator begin, const_iterator end)
  52.         : Container(static_cast<size_type>(std::distance(begin, end)))
  53.     {
  54.         assert(begin <= end && "Container(iter, iter): begin & end iterators are reversed");
  55.         std::uninitialized_copy(begin, end, begin()); // copy construct each element from range into buffer w/ placement new
  56.         _count = static_cast<size_type>(std::distance(begin, end));
  57.     }
  58.  
  59.     //copy ctor, delegating to range constructor
  60.     explicit Container(const Container& that)
  61.         : Container(that.begin(), that.end())
  62.     {
  63.     }
  64.  
  65.     //list construction, delegating to range constructor
  66.     Container(std::initializer_list<T> list)
  67.         : Container(std::begin(list), std::end(list))
  68.     {
  69.     }
  70.  
  71.     //move constructor
  72.     Container(Container&& that) noexcept
  73.     {
  74.         _count = std::exchange(that._count, 0);
  75.         _capacity = std::exchange(that._capacity, 0);
  76.         _data = std::exchange(that._data, nullptr);
  77.     }
  78.  
  79.     //by value assignment idiom. deals with both copy- and move assignment
  80.     //also known as: "unifying assignment operator"
  81.     //https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Copy-and-swap
  82.     Container& operator=(Container that) noexcept
  83.     {
  84.         swap(that);
  85.         return *this;
  86.     }
  87.  
  88.     void swap(Container& that) noexcept
  89.     {
  90.         using std::swap;
  91.         swap(_data, that._data);
  92.         swap(_count, that._count);
  93.         swap(_capacity, that._capacity);
  94.     }
  95.  
  96.     //ADL overload. See Arthur O'Dwyer: https://youtu.be/7Qgd9B1KuMQ?t=2597
  97.     friend void swap(Container<T>& a, Container<T>& b) noexcept
  98.     {
  99.         a.swap(b);
  100.     }
  101.  
  102.     void clear() noexcept
  103.     {
  104.         //TODO: could be erase(begin(), end()).
  105.         while (!empty()) {
  106.             pop_back();
  107.         }
  108.     }
  109.  
  110.     void pop_back() noexcept
  111.     {
  112.         assert(!empty() && "pop_back() on empty container is undefined!");
  113.         back().~value_type();
  114.         --_count;
  115.     }
  116.  
  117.     void reserve(size_type newCapacity)
  118.     {
  119.         if (newCapacity <= _capacity) {
  120.             return;  //never decrease the allocation
  121.         }
  122.         pointer newBuffer = static_cast<pointer>(::operator new(sizeof(value_type) * newCapacity));
  123.         std::uninitialized_move(begin(), end(), newBuffer);
  124.         destruct_all(); //run all destructors on the moved-from objects.
  125.         ::operator delete(_data);
  126.         _data = newBuffer;
  127.         _capacity = newCapacity;
  128.     }
  129.    
  130.     template <typename... Args>
  131.     void emplace_back(Args&&... args)
  132.     {
  133.         resizeIfNeeded();
  134.         new (&_data[_count]) value_type(std::forward<Args>(args)...); // construct value in memory of aligned storage using inplace operator new
  135.         ++_count;
  136.     }
  137.  
  138.     void push_back(const T& value)
  139.     {
  140.         emplace_back(std::forward<const T&>(value));
  141.     }
  142.  
  143.     reference at(size_type index)
  144.     {
  145.         if (index >= size()) {
  146.             throw std::out_of_range("Container at() index is out of range!");
  147.         }
  148.         return _data[index];
  149.     }
  150.     const_reference at(size_type index) const
  151.     {
  152.         if (index >= size()) {
  153.             throw std::out_of_range("Container at() index is out of range!");
  154.         }
  155.         return _data[index];
  156.     }
  157.  
  158.     reference operator[](size_type index) noexcept
  159.     {
  160.         assert(index < size() && "Container operator[] index is out of range!");
  161.         return _data[index];
  162.     }
  163.     const_reference operator[](size_type index) const noexcept
  164.     {
  165.         assert(index < size() && "Container operator[] index is out of range!");
  166.         return _data[index];
  167.     }
  168.  
  169.     pointer data() noexcept
  170.     {
  171.         return _data;
  172.     }
  173.     const_pointer data() const noexcept
  174.     {
  175.         return _data;
  176.     }
  177.     reference front() noexcept
  178.     {
  179.         assert(!empty() && "front() on empty container is UB");
  180.         return _data[0];
  181.     }
  182.     const_reference front() const noexcept
  183.     {
  184.         assert(!empty() && "front() on empty container is UB");
  185.         return _data[0];
  186.     }
  187.     const_reference back() const noexcept
  188.     {
  189.         assert(!empty() && "back() on empty container is UB");
  190.         return _data[size() - 1];
  191.     }
  192.     reference back() noexcept
  193.     {
  194.         assert(!empty() && "back() on empty container is UB");
  195.         return _data[size() - 1];
  196.     }
  197.     bool empty() const noexcept
  198.     {
  199.         return size() == 0;
  200.     }
  201.     size_type capacity() const noexcept
  202.     {
  203.         return _capacity;
  204.     }
  205.     size_type size() const noexcept
  206.     {
  207.         return _count;
  208.     }
  209.        
  210.     iterator begin() noexcept { return _data; }
  211.     const_iterator begin() const noexcept { return _data; }
  212.     const_iterator cbegin() const noexcept { return _data; }    
  213.     const_iterator end() const noexcept { return _data + _count; }
  214.     const_iterator cend() const noexcept { return _data + _count; }
  215.     iterator end() noexcept { return _data + _count; }
  216.  
  217. private:
  218.     pointer _data = nullptr;
  219.     size_type _count = 0;
  220.     size_type _capacity = 0;
  221.     constexpr static size_type INITIAL_CAPACITY = 2;
  222.     constexpr static double GROWTH_FACTOR = 2.0f;
  223.  
  224.     void resizeIfNeeded()
  225.     {
  226.         if (_capacity == 0) {
  227.             reserve(INITIAL_CAPACITY);
  228.         } else if (_count == _capacity) {
  229.             reserve(static_cast<size_type>(GROWTH_FACTOR * _capacity));
  230.         }
  231.     }
  232.  
  233.     void destruct_all() noexcept
  234.     {
  235.         for (reference item : *this) {
  236.             item.~value_type();
  237.         }
  238.     }
  239. };
  240.  
  241. template <typename T>
  242. bool operator==(const Container<T>& lhs, const Container<T>& rhs) noexcept
  243. {
  244.     if (std::size(lhs) != std::size(rhs)) {
  245.         return false;
  246.     }
  247.     return std::equal(std::begin(lhs), std::end(lhs), std::begin(rhs));
  248. }
  249. template <typename T>
  250. bool operator<(const Container<T>& lhs, const Container<T>& rhs) noexcept
  251. {
  252.     return std::lexicographical_compare(lhs.begin(), lhs.end(),
  253.                                         rhs.begin(), rhs.end());
  254. }
  255.  
  256. template <typename T>
  257. bool operator!=(const Container<T>& lhs, const Container<T>& rhs) noexcept
  258. {
  259.     return !(lhs == rhs);
  260. }
  261. template <typename T>
  262. bool operator>(const Container<T>& lhs, const Container<T>& rhs) noexcept
  263. {
  264.     return rhs < lhs;
  265. }
  266. template <typename T>
  267. bool operator<=(const Container<T>& lhs, const Container<T>& rhs) noexcept
  268. {
  269.     !(lhs > rhs);
  270. }
  271. template <typename T>
  272. bool operator>=(const Container<T>& lhs, const Container<T>& rhs) noexcept
  273. {
  274.     !(lhs < rhs);
  275. }
  276. }
RAW Paste Data