fork download 
  1. #ifndef LITB_VECTOR_H
  2. #define LITB_VECTOR_H
  3.  
  4. namespace litb {
  5.    template<typename T>
  6.    T min(const T& a, const T& b) {
  7.       return a < b ? a : b;
  8.    }
  9.  
  10.    template<typename T>
  11.    T max(const T& a, const T& b) {
  12.       return a > b ? a : b;
  13.    }
  14. }
  15.  
  16. #include <new>
  17. #include <type_traits>
  18.  
  19. namespace litb {
  20.  
  21. // The functionality of Vector that does not depend on the "SmallSize"
  22. // template parameter.
  23. template<typename T>
  24. class VectorBase {
  25. public:
  26.    typedef T *iterator;
  27.    typedef const T *const_iterator;
  28.    typedef T value_type;
  29.  
  30. public:
  31.    VectorBase(T *data, T *endData)
  32.       :_data(data), _endData(data), _endReserve(endData)
  33.    { }
  34.  
  35.    ~VectorBase() {
  36.       clear();
  37.       if(usesHeap()) {
  38.          operator delete(_data);
  39.       }
  40.    }
  41.  
  42. public:
  43.    iterator begin() { return _data; }
  44.    iterator end() { return _endData; }
  45.    const_iterator begin() const { return _data; }
  46.    const_iterator end() const { return _endData; }
  47.  
  48. public:
  49.    // appends a new item to the back of the vector
  50.    void append(const T& t) {
  51.       insert(end(), t);
  52.    }
  53.  
  54.    void prepend(const T& t) {
  55.       insert(begin(), t);
  56.    }
  57.  
  58.    // inserts a new item before the given iterator, and return
  59.    // an iterator to the new item
  60.    iterator insert(iterator it, const T& t) {
  61.       it = grow(it, 1);
  62.       new ((void*)it) T(t);
  63.       _endData++;
  64.       return it;
  65.    }
  66.  
  67.    // assigns the given range to this vector
  68.    template<typename Iterator>
  69.    void assign(Iterator b, Iterator e) {
  70.       clear();
  71.       insert(end(), b, e);
  72.    }
  73.  
  74.    // inserts the range [b, e) before iterator position "it", and return
  75.    // a pointer to the first item inserted
  76.    template<typename Iterator>
  77.    iterator insert(iterator it, Iterator b, Iterator e) {
  78.       it = grow(it, e - b);
  79.       for(; b != e; b++, it++) {
  80.          new ((void*)it) T(*b);
  81.          _endData++;
  82.       }
  83.       return it;
  84.    }
  85.  
  86.    // makes the vector have size() 0, without changing the capacity
  87.    void clear() {
  88.       for(; _endData != _data; _endData--) {
  89.          _endData[-1].~T();
  90.       }
  91.       _endData = _data;
  92.    }
  93.  
  94.    // erases the portion [b, e) of the vector, without changing the capacity
  95.    void erase(iterator b, iterator e) {
  96.       if(b == e) {
  97.          clear();
  98.          return;
  99.       }
  100.  
  101.       for(; e != _endData; e++, b++) {
  102.          *b = *e;
  103.       }
  104.       T *dptr = _endData;
  105.       for(T *edptr = dptr - (e - b); dptr != edptr; dptr--)
  106.          dptr->~T();
  107.       _endData = dptr;
  108.    }
  109.  
  110.    // returns the actual size of the vector
  111.    int size() const { return _endData - _data; }
  112.  
  113.    // returns the reserved capacity of the vector that it can insert without
  114.    // reallocating
  115.    int capacity() const { return _endReserve - _data; }
  116.  
  117.    // returns true if we use the heap memory currently.
  118.    bool usesHeap() const {
  119.       return (const void*)_data != (this + 1);
  120.    }
  121.  
  122.    // reserves space for at least "space" items
  123.    void reserve(int space) {
  124.       if(space <= capacity())
  125.          return;
  126.  
  127.       grow(end(), space - capacity());
  128.    }
  129.  
  130. private:
  131.    // copying this class would slice away the builtin array - so we forbid that
  132.    VectorBase(const VectorBase &other);
  133.  
  134. private:
  135.    // reserves space for "elements" items before iterator "it".
  136.    // returns an iterator pointing at the first free slot.
  137.    iterator grow(iterator it, int elements) {
  138.       if(elements == 0)
  139.          return it;
  140.  
  141.       int index = it - begin();
  142.       if((_endReserve - _endData) < elements) {
  143.          // reallocate, leaving "elements" free slots at "index"
  144.          int newCapacity = max(capacity() * 2, capacity() + elements);
  145.          T *data1 = (T*)operator new(sizeof(T) * newCapacity);
  146.          T *endData1 = data1;
  147.          T *endReserve1 = data1 + newCapacity;
  148.          for(T *data = _data; data != _endData; data++, endData1++) {
  149.             if(data - _data == index) {
  150.                endData1 += elements;
  151.             }
  152.             new ((void*)endData1) T(*data);
  153.          }
  154.  
  155.          for(; _endData != _data; _endData--)
  156.             _endData[-1].~T();
  157.          if(usesHeap()) {
  158.             operator delete(_data);
  159.          }
  160.          _data = data1;
  161.          _endData= endData1;
  162.          _endReserve = endReserve1;
  163.       } else if(it != end()) {
  164.          T *endData1 = _endData, *endDataNew1 = _endData + elements;
  165.          int newlyAllocated = min(elements, end() - it);
  166.          for(; newlyAllocated > 0; newlyAllocated--, endDataNew1--, endData1--) {
  167.             new ((void*)&endDataNew1[-1]) T(endData1[-1]); 
  168.          }
  169.          for(; endData1 != it; endData1--, endDataNew1--) {
  170.             endDataNew1[-1] = endData1[-1];
  171.          }
  172.  
  173.          // the hole should contain unconstructed items that the caller can placement-new into
  174.          int dtorsInHole = min(elements, (end() - it));
  175.          for(iterator itHole = it; dtorsInHole > 0; dtorsInHole--, itHole++)
  176.             itHole->~T();
  177.       }
  178.       return begin() + index;
  179.    }
  180.  
  181. private:
  182.    T *_data;
  183.    T *_endData;
  184.    T *_endReserve;
  185. };
  186.  
  187. // A vector that allocates "SmallSize" elements in its own memory and
  188. // only if more elements are needed, reverts to heap memory.
  189. template<typename T, int SmallSize>
  190. class Vector : public VectorBase<T> {
  191.    union {
  192.       typename std::aligned_storage<sizeof(T), alignof(T)>::type
  193.          _aligner;
  194.       unsigned char _buffer[sizeof(T) * SmallSize];
  195.    };
  196.  
  197. public:
  198.    Vector():VectorBase<T>((T*)_buffer, (T*)_buffer + SmallSize) {}
  199.    Vector(const Vector& other):Vector() {
  200.       this->insert(this->end(), other.begin(), other.end());
  201.    }
  202.    template<int SmallSize1>
  203.    Vector(const Vector<T, SmallSize1>& other):Vector() {
  204.       this->insert(this->end(), other.begin(), other.end());
  205.    }
  206. };
  207.  
  208.  
  209. }
  210.  
  211. #endif
  212.  
  213. #include <iostream>
  214.  
  215. struct A {
  216.    A(int x):x(x) {
  217.       std::cout << "A(" << x << ")" << std::endl;
  218.    }
  219.  
  220.    ~A() {
  221.       std::cout << "~A(" << x << ")" << std::endl;
  222.    }
  223.  
  224.    A(A const& other):x(other.x) {
  225.       std::cout << "A(A const&)(" << other.x << ")" << std::endl;
  226.    }
  227.  
  228.    int x;
  229. };
  230.  
  231. int main() {
  232.    litb::Vector<A, 5> v;
  233.    v.append(A(1));
  234.    v.append(A(2));
  235.    v.append(A(3));
  236.    v.append(A(4));
  237.    v.append(A(5));
  238.    v.append(A(6));
  239.  
  240.    std::cout << "\n";
  241.    for(const A& a : v)
  242.       std::cout << "> " << a.x << std::endl;
  243.  
  244.    litb::Vector<A, 6> v1(v);
  245.    std::cout << "\n";
  246.    for(const A& a : v1)
  247.       std::cout << "> " << a.x << std::endl;
  248. }
Success #stdin #stdout 0s 3032KB
comments (?)
stdin 
Standard input is empty
stdout 
A(1)
A(A const&)(1)
~A(1)
A(2)
A(A const&)(2)
~A(2)
A(3)
A(A const&)(3)
~A(3)
A(4)
A(A const&)(4)
~A(4)
A(5)
A(A const&)(5)
~A(5)
A(6)
A(A const&)(1)
A(A const&)(2)
A(A const&)(3)
A(A const&)(4)
A(A const&)(5)
~A(5)
~A(4)
~A(3)
~A(2)
~A(1)
A(A const&)(6)
~A(6)

> 1
> 2
> 3
> 4
> 5
> 6
A(A const&)(1)
A(A const&)(2)
A(A const&)(3)
A(A const&)(4)
A(A const&)(5)
A(A const&)(6)

> 1
> 2
> 3
> 4
> 5
> 6
~A(6)
~A(5)
~A(4)
~A(3)
~A(2)
~A(1)
~A(6)
~A(5)
~A(4)
~A(3)
~A(2)
~A(1)
https://ideone.com/2aYhFK
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!