ulfben

Container 2020 day 3

Nov 24th, 2020
638
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×