Advertisement
ulfben

Container 2020 day 3

Nov 24th, 2020
924
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.69 KB | None | 0 0
  1. /*
  2. K. Iglberger: Calling Functions: A Tutorial, CppCon 2020
  3. Scott Meyers, Effective C++ 3rd Edition, Item 23
  4. Scott Meyers: How Non-Member Functions Improve Encapsulation
  5. Herb Sutter: GotW #70: Encapsulation
  6. Herb Sutter, Exceptional C++ Style, Item 37 to Item 40
  7. Online: GoTW#84: Monoliths "Unstrung"
  8. Herb Sutter: What's In a Class? - The Interface Principle
  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(*this);
  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 expection in order 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(*this), 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(*this)); // 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.     void pop_back() noexcept
  97.     {
  98.         assert(!empty(*this) && "pop_back() on empty container is undefined!");
  99.         back(*this).~value_type();
  100.         --_count;
  101.     }
  102.  
  103.     void reserve(size_type newCapacity){
  104.         if (newCapacity <= _capacity) {
  105.             return;  //never decrease the allocation
  106.         }
  107.         pointer newBuffer = static_cast<pointer>(::operator new(sizeof(value_type) * newCapacity));
  108.         std::uninitialized_move(begin(*this), end(*this), newBuffer);
  109.         destruct_all(); //run all destructors on the moved-from objects.
  110.         ::operator delete(_data);
  111.         _data = newBuffer;
  112.         _capacity = newCapacity;
  113.     }
  114.    
  115.     template <typename... Args>
  116.     void emplace_back(Args&&... args){
  117.         resizeIfNeeded();
  118.         new (&_data[_count]) value_type(std::forward<Args>(args)...); // construct value in memory of aligned storage using inplace operator new
  119.         ++_count;
  120.     }
  121.        
  122.     reference operator[](size_type index) noexcept {
  123.         assert(index < size() && "Container operator[] index is out of range!");
  124.         return _data[index];
  125.     }
  126.     const_reference operator[](size_type index) const noexcept{
  127.         assert(index < size() && "Container operator[] index is out of range!");
  128.         return _data[index];
  129.     }
  130.  
  131.     pointer data() noexcept {
  132.         return _data;
  133.     }
  134.     const_pointer data() const noexcept {
  135.         return _data;
  136.     }    
  137.     size_type capacity() const noexcept {
  138.         return _capacity;
  139.     }
  140.     size_type size() const noexcept {
  141.         return _count;
  142.     }    
  143.  
  144. private:
  145.     pointer _data = nullptr;
  146.     size_type _count = 0;
  147.     size_type _capacity = 0;
  148.     constexpr static size_type INITIAL_CAPACITY = 2;
  149.     constexpr static double GROWTH_FACTOR = 2.0f;
  150.  
  151.     void resizeIfNeeded()
  152.     {
  153.         if (_capacity == 0) {
  154.             reserve(INITIAL_CAPACITY);
  155.         } else if (_count == _capacity) {
  156.             reserve(static_cast<size_type>(GROWTH_FACTOR * _capacity));
  157.         }
  158.     }
  159.  
  160.     void destruct_all() noexcept {
  161.         for (reference item : *this) {
  162.             item.~value_type();
  163.         }
  164.     }
  165. };
  166.  
  167. template <typename T>
  168. void push_back(Container<T>& c, const T& value) {
  169.     c.emplace_back(std::forward<const T&>(value));
  170. }
  171.  
  172. template <typename T>
  173. void clear(Container<T>& c) noexcept {
  174.     //TODO: could be erase(begin(), end()).
  175.     while (!empty(c)) {
  176.         c.pop_back();
  177.     }
  178. }
  179.  
  180. //ADL overload. See Arthur O'Dwyer: https://youtu.be/7Qgd9B1KuMQ?t=2597
  181. template <typename T>
  182. void swap(Container<T>& a, Container<T>& b) noexcept{
  183.     a.swap(b);
  184. }
  185.  
  186. template <typename T>
  187. typename Container<T>::reference at(Container<T>& c, typename Container<T>::size_type index)
  188. {
  189.     if (index >= c.size()) {
  190.         throw std::out_of_range("Container at() index is out of range!");
  191.     }
  192.     return c.data()[index];
  193. }
  194. template <typename T>
  195. typename Container<T>::const_reference at(const Container<T>& c, typename Container<T>::size_type index)
  196. {
  197.     if (index >= c.size()) {
  198.         throw std::out_of_range("Container at() index is out of range!");
  199.     }
  200.     return c.data()[index];
  201. }
  202.  
  203. template <typename T>
  204. typename Container<T>::reference front(Container<T>& c) noexcept {
  205.     assert(!empty(c) && "front() on empty container is UB");
  206.     return c.data()[0];
  207. }
  208. template <typename T>
  209. typename Container<T>::const_reference front(const Container<T>& c) noexcept {
  210.     assert(!empty(c) && "front() on empty container is UB");
  211.     return c.data()[0];
  212. }
  213. template <typename T>
  214. typename Container<T>::const_reference back(const Container<T>& c) noexcept {
  215.     assert(!empty(c) && "back() on empty container is UB");
  216.     return c.data()[c.size() - 1];
  217. }
  218. template <typename T>
  219. typename Container<T>::reference back(Container<T>& c) noexcept {
  220.     assert(!empty(c) && "back() on empty container is UB");
  221.     return c.data()[c.size() - 1];
  222. }
  223. template <typename T>
  224. bool empty(const Container<T>& c) noexcept{
  225.     return c.size() == 0;
  226. }
  227.  
  228. template <typename T>
  229. typename Container<T>::iterator begin(Container<T>& c) noexcept { return c.data(); }
  230.  
  231. template <typename T>
  232. typename Container<T>::const_iterator begin(const Container<T>& c) noexcept { return c.data(); }
  233.  
  234. template <typename T>
  235. typename Container<T>::const_iterator cbegin(const Container<T>& c) noexcept { return c.data(); }
  236.  
  237. template <typename T>
  238. typename Container<T>::const_iterator end(const Container<T>& c) noexcept { return c.data() + c.size(); }
  239.  
  240. template <typename T>
  241. typename Container<T>::const_iterator cend(const Container<T>& c) noexcept { return c.data() + c.size(); }
  242.  
  243. template <typename T>
  244. typename Container<T>::iterator end(Container<T>& c) noexcept { return c.data() + c.size(); }
  245.  
  246. template <typename T>
  247. bool operator==(const Container<T>& lhs, const Container<T>& rhs) noexcept
  248. {
  249.     if (std::size(lhs) != std::size(rhs)) {
  250.         return false;
  251.     }
  252.     return std::equal(std::begin(lhs), std::end(lhs), std::begin(rhs));
  253. }
  254. template <typename T>
  255. bool operator<(const Container<T>& lhs, const Container<T>& rhs) noexcept
  256. {
  257.     return std::lexicographical_compare(lhs.begin(), lhs.end(),
  258.                                         rhs.begin(), rhs.end());
  259. }
  260.  
  261. template <typename T>
  262. bool operator!=(const Container<T>& lhs, const Container<T>& rhs) noexcept
  263. {
  264.     return !(lhs == rhs);
  265. }
  266. template <typename T>
  267. bool operator>(const Container<T>& lhs, const Container<T>& rhs) noexcept
  268. {
  269.     return rhs < lhs;
  270. }
  271. template <typename T>
  272. bool operator<=(const Container<T>& lhs, const Container<T>& rhs) noexcept
  273. {
  274.     !(lhs > rhs);
  275. }
  276. template <typename T>
  277. bool operator>=(const Container<T>& lhs, const Container<T>& rhs) noexcept
  278. {
  279.     !(lhs < rhs);
  280. }
  281. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement