SHARE
TWEET

Untitled

a guest Dec 11th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma once
  2. #include <iostream>
  3.  
  4. template<class T>
  5. class Vector
  6. {
  7. public:
  8.     Vector() : data_(nullptr), size_(0), allocated_(0) {}
  9.  
  10.     Vector(const Vector<T>& copy) : data_(new T[allocated_]), size_(copy.size_), allocated_(2 * copy.size_)
  11.     {
  12.         for (unsigned i = 0; i < size_; ++i)
  13.         {
  14.             data_[i] = copy.data_[i];
  15.         }
  16.     }
  17.  
  18.     Vector(const unsigned& count, const T& elem = {}) : data_(new T[allocated_]), size_(count), allocated_(2 * size_)
  19.     {
  20.         for (unsigned i = 0; i < size_; ++i)
  21.         {
  22.             data_[i] = elem;
  23.         }
  24.     }
  25.  
  26.     const unsigned& size() const
  27.     {
  28.         return size_;
  29.     }
  30.  
  31.     const unsigned& allocated() const
  32.     {
  33.         return allocated_;
  34.     }
  35.  
  36.     bool empty() const
  37.     {
  38.         return (!size_);
  39.     }
  40.  
  41.     void resize(const unsigned& count, const T& elem = {})
  42.     {
  43.         if (count > allocated_)
  44.         {
  45.             allocated_ = 2 * count;
  46.             T* newData = new T[allocated_];
  47.             unsigned length = std::min(size_, count);
  48.             for (unsigned i = 0; i < length; ++i)
  49.             {
  50.                 newData[i] = data_[i];
  51.             }
  52.             delete[] data_;
  53.             data_ = newData;
  54.         }
  55.         int length = count - size_;
  56.         for (unsigned i = 0; i < length; ++i)
  57.         {
  58.             data_[size_ + i] = elem;
  59.         }
  60.         size_ = count;
  61.     }
  62.  
  63.     void clear()
  64.     {
  65.         resize(0);
  66.     }
  67.  
  68.     void reserve(const unsigned& allocated)
  69.     {
  70.         if (allocated > allocated_)
  71.         {
  72.             allocated_ = allocated;
  73.             T* newData = new T[allocated_];
  74.             for (unsigned i = 0; i < size_; ++i)
  75.             {
  76.                 newData[i] = data_[i];
  77.             }
  78.             delete[] data_;
  79.             data_ = newData;
  80.         }
  81.     }
  82.  
  83.     void shrink_to_fit()
  84.     {
  85.         if (allocated_ != size_)
  86.         {
  87.             allocated_ = size_;
  88.             T* newData = new T[allocated_];
  89.             for (unsigned i = 0; i < size_; ++i)
  90.             {
  91.                 newData[i] = data_[i];
  92.             }
  93.             delete[] data_;
  94.             data_ = newData;
  95.         }
  96.     }
  97.  
  98.     Vector<T> subsegment(const unsigned& l, const unsigned& r) const
  99.     {
  100.         assert(l < r && 0 <= l && r <= size_);
  101.         Vector<T> res;
  102.         res.size_ = r - l;
  103.         res.allocated_ = res.size_;
  104.         res.data_ = new T[res.allocated_];
  105.         for (unsigned i = 0; i < res.size_; ++i)
  106.         {
  107.             res[i] = data_[i + l];
  108.         }
  109.         return res;
  110.     }
  111.  
  112.     Vector<T> subsegment(const unsigned& l) const
  113.     {
  114.         return subsegment(l, size_);
  115.     }
  116.  
  117.     int find(const T& elem, unsigned l, unsigned r)
  118.     {
  119.         assert(l < r && 0 <= l && r <= size_);
  120.         for (unsigned i = l; i < r; ++i)
  121.         {
  122.             if (data_[i] == elem)
  123.             {
  124.                 return i;
  125.             }
  126.         }
  127.         return -1;
  128.     }
  129.  
  130.     int rfind(const T& elem, unsigned l, unsigned r)
  131.     {
  132.         assert(l < r && 0 <= l && r <= size_);
  133.         for (unsigned i = r - 1; i >= l; --i)
  134.         {
  135.             if (data_[i] == elem)
  136.             {
  137.                 return i;
  138.             }
  139.         }
  140.         return -1;
  141.     }
  142.  
  143.     int find(const T& elem)
  144.     {
  145.         return find(elem, 0, size_);
  146.     }
  147.  
  148.     int rfind(const T& elem)
  149.     {
  150.         return rfind(elem, 0, size_);
  151.     }
  152.  
  153.     int findSubsegment(const Vector<T>& elem, unsigned l, unsigned r)
  154.     {
  155.         assert(l < r && 0 <= l && r <= size_);
  156.         unsigned* pi = new unsigned[elem.size_];
  157.         pi[0] = 0;
  158.         unsigned j = 0;
  159.         for (unsigned i = 1; i < elem.size_; ++i)
  160.         {
  161.             while (j > 0 && elem.data_[i] != elem.data_[j])
  162.             {
  163.                 j = pi[j - 1];
  164.             }
  165.             pi[i] = (j += (elem.data_[i] == elem.data_[j]));
  166.         }
  167.         j = 0;
  168.         for (unsigned i = 0; i < r; ++i)
  169.         {
  170.             while (j > 0 && elem.data_[j] != data_[i])
  171.             {
  172.                 j = pi[j - 1];
  173.             }
  174.             j += (data_[i] == elem.data_[j]);
  175.             if (l <= i - elem.size_ + 1 && i < r && j == elem.size_)
  176.             {
  177.                 return i - elem.size_ + 1;
  178.             }
  179.         }
  180.         delete[] pi;
  181.         return -1;
  182.     }
  183.  
  184.     int rfindSubsegment(const Vector<T>& elem, unsigned l, unsigned r)
  185.     {
  186.         int res = -1;
  187.         assert(l < r && 0 <= l && r <= size_);
  188.         unsigned* pi = new unsigned[elem.size_];
  189.         pi[0] = 0;
  190.         unsigned j = 0;
  191.         for (unsigned i = 1; i < elem.size_; ++i)
  192.         {
  193.             while (j > 0 && elem.data_[i] != elem.data_[j])
  194.             {
  195.                 j = pi[j - 1];
  196.             }
  197.             pi[i] = (j += (elem.data_[i] == elem.data_[j]));
  198.         }
  199.         j = 0;
  200.         for (unsigned i = 0; i < r; ++i)
  201.         {
  202.             while (j > 0 && elem.data_[j] != data_[i])
  203.             {
  204.                 j = pi[j - 1];
  205.             }
  206.             j += (data_[i] == elem.data_[j]);
  207.             if (l <= i - elem.size_ + 1 && i < r && j == elem.size_)
  208.             {
  209.                 res = i - elem.size_ + 1;
  210.             }
  211.         }
  212.         delete[] pi;
  213.         return res;
  214.     }
  215.  
  216.     int findSubsegment(const Vector<T>& elem)
  217.     {
  218.         return findSubsegment(elem, 0, size_);
  219.     }
  220.  
  221.     int rfindSubsegment(const Vector<T>& elem)
  222.     {
  223.         return rfindSubsegment(elem, 0, size_);
  224.     }
  225.  
  226.     std::istream& getline(std::istream& in)
  227.     {
  228.         T elem;
  229.         while (in.peek() != '\n')
  230.         {
  231.             in >> elem;
  232.             *this += elem;
  233.         }
  234.         in.get();
  235.         return in;
  236.     }
  237.  
  238.     T& operator[](int id) const
  239.     {
  240.         id += (id < 0 ? size_ : 0);
  241.         assert(0 <= id && id < (int)size_);
  242.         return data_[id];
  243.     }
  244.  
  245.     Vector<T>& operator=(const Vector<T>& right)
  246.     {
  247.         if (this == &right)
  248.         {
  249.             return *this;
  250.         }
  251.         delete[] data_;
  252.         size_ = right.size_;
  253.         allocated_ = 2 * size_;
  254.         data_ = new T[allocated_];
  255.         for (unsigned i = 0; i < size_; ++i)
  256.         {
  257.             data_[i] = right.data_[i];
  258.         }
  259.         return *this;
  260.     }
  261.  
  262.     Vector<T>& operator=(const T& right)
  263.     {
  264.         delete[] data_;
  265.         size_ = 1;
  266.         allocated_ = 2;
  267.         data_ = new T[allocated_];
  268.         data_[0] = right;
  269.         return *this;
  270.     }
  271.  
  272.     Vector<T>& operator+=(const Vector<T>& right)
  273.     {
  274.         if (allocated_ - size_ < right.size_)
  275.         {
  276.             allocated_ = 2 * (size_ + right.size_);
  277.             T* newData = new T[allocated_];
  278.             for (unsigned i = 0; i < size_; ++i)
  279.             {
  280.                 newData[i] = data_[i];
  281.             }
  282.             delete[] data_;
  283.             data_ = newData;
  284.         }
  285.         for (unsigned i = size_; i < size_ + right.size_; ++i)
  286.         {
  287.             data_[i] = right.data_[i - size_];
  288.         }
  289.         size_ += right.size_;
  290.         return *this;
  291.     }
  292.  
  293.     Vector<T>& operator+=(const T& right)
  294.     {
  295.         if (allocated_ == size_)
  296.         {
  297.             allocated_ = 2 * (size_ + 1);
  298.             T* newData = new T[allocated_];
  299.             for (unsigned i = 0; i < size_; ++i)
  300.             {
  301.                 newData[i] = data_[i];
  302.             }
  303.             delete[] data_;
  304.             data_ = newData;
  305.         }
  306.         data_[size_] = right;
  307.         size_++;
  308.         return *this;
  309.     }
  310.  
  311.     Vector<T> operator+(const Vector<T>& right) const
  312.     {
  313.         Vector<T> res;
  314.         res.size_ = size_ + right.size_;
  315.         res.allocated_ = 2 * res.size_;
  316.         res.data_ = new T[res.allocated_];
  317.         for (unsigned i = 0; i < size_; ++i)
  318.         {
  319.             res.data_[i] = data_[i];
  320.         }
  321.         for (unsigned i = 0; i < right.size_; ++i)
  322.         {
  323.             res.data_[i + size_] = right.data_[i];
  324.         }
  325.         return res;
  326.     }
  327.  
  328.     Vector<T> operator+(const T& right) const
  329.     {
  330.         Vector<T> res;
  331.         res.size_ = size_ + 1;
  332.         res.allocated_ = 2 * res.size_;
  333.         res.data_ = new T[res.allocated_];
  334.         for (unsigned i = 0; i < size_; ++i)
  335.         {
  336.             res.data_[i] = data_[i];
  337.         }
  338.         res.data_[size_] = right;
  339.         return res;
  340.     }
  341.  
  342.     bool operator==(const Vector<T>& right) const
  343.     {
  344.         bool res = (size_ == right.size_);
  345.         for (unsigned i = 0; res && i < right.size_; ++i)
  346.         {
  347.             res = (data_[i] == right.data_[i]);
  348.         }
  349.         return res;
  350.     }
  351.  
  352.     bool operator==(const T& right) const
  353.     {
  354.         return (size_ == 1 && data_[0] == right);
  355.     }
  356.  
  357.     bool operator!=(const Vector<T>& right) const
  358.     {
  359.         return !(*this == right);
  360.     }
  361.  
  362.     bool operator!=(const T& right) const
  363.     {
  364.         return !(*this == right);
  365.     }
  366.  
  367.     bool operator<(const Vector<T>& right) const
  368.     {
  369.         unsigned length = std::min(size_, right.size_);
  370.         for (unsigned i = 0; i < length; ++i)
  371.         {
  372.             if (data_[i] < right.data_[i])
  373.             {
  374.                 return true;
  375.             }
  376.         }
  377.         return (size_ < right.size_);
  378.     }
  379.  
  380.     bool operator<(const T& right) const
  381.     {
  382.         return (!size_ || data_[0] < right);
  383.     }
  384.  
  385.     bool operator<=(const Vector<T>& right) const
  386.     {
  387.         return (*this < right || *this == right);
  388.     }
  389.  
  390.     bool operator<=(const T& right) const
  391.     {
  392.         return (*this < right || *this == right);
  393.     }
  394.  
  395.     bool operator>(const Vector<T>& right) const
  396.     {
  397.         unsigned length = std::min(size_, right.size_);
  398.         for (unsigned i = 0; i < length; ++i)
  399.         {
  400.             if (data_[i] > right.data_[i])
  401.             {
  402.                 return true;
  403.             }
  404.         }
  405.         return (size_ > right.size_);
  406.     }
  407.  
  408.     bool operator>(const T& right) const
  409.     {
  410.         return (data_[0] > right || data_[0] == right && size_ > 1);
  411.     }
  412.  
  413.     bool operator>=(const Vector<T>& right) const
  414.     {
  415.         return (*this > right || *this == right);
  416.     }
  417.  
  418.     bool operator>=(const T& right) const
  419.     {
  420.         return (*this > right || *this == right);
  421.     }
  422.  
  423.     friend std::istream& operator>>(std::istream& in, Vector<T>& v)
  424.     {
  425.         for (unsigned i = 0; i < v.size_; ++i)
  426.         {
  427.             in >> v[i];
  428.         }
  429.         return in;
  430.     }
  431.  
  432.     friend std::ostream& operator<<(std::ostream& out, const Vector<T>& v)
  433.     {
  434.         for (unsigned i = 0; i < v.size_; ++i)
  435.         {
  436.             out << v.data_[i] << ' ';
  437.         }
  438.         return out;
  439.     }
  440.  
  441.     class reverse_iterator;
  442.  
  443.     class iterator
  444.     {
  445.     public:
  446.  
  447.         iterator(T* ptr, T* left, T* right) : current_(ptr), left_(left), right_(right) {}
  448.  
  449.         iterator(const iterator& copy) : current_(copy.current_), left_(copy.left_), right_(copy.right_) {}
  450.  
  451.         reverse_iterator getReversible() const
  452.         {
  453.             return reverse_iterator(current_, left_, right_);
  454.         }
  455.  
  456.         iterator& operator=(const iterator& right)
  457.         {
  458.             current_ = right.current_;
  459.             return *this;
  460.         }
  461.  
  462.         T operator[](int id)
  463.         {
  464.             return *(current_ + id);
  465.         }
  466.  
  467.         T* operator->() const
  468.         {
  469.             return current_;
  470.         }
  471.  
  472.         iterator operator+(int right) const
  473.         {
  474.             return iterator(current_ + right, left_, right_);
  475.         }
  476.  
  477.         iterator operator-(int right) const
  478.         {
  479.             return iterator(current_ - right, left_, right_);
  480.         }
  481.  
  482.         iterator operator++(int)
  483.         {
  484.             iterator res(current_, left_, right_);
  485.             current_++;
  486.             return res;
  487.         }
  488.  
  489.         iterator operator--(int)
  490.         {
  491.             iterator res(current_, left_, right_);
  492.             current_--;
  493.             return res;
  494.         }
  495.  
  496.         iterator& operator++()
  497.         {
  498.             ++current_;
  499.             return *this;
  500.         }
  501.  
  502.         iterator& operator--()
  503.         {
  504.             --current_;
  505.             return *this;
  506.         }
  507.  
  508.         iterator& operator+=(int right)
  509.         {
  510.             current_ += right;
  511.             return *this;
  512.         }
  513.  
  514.         iterator& operator-=(int right)
  515.         {
  516.             current_ -= right;
  517.             return *this;
  518.         }
  519.  
  520.         T& operator*()
  521.         {
  522.             assert(left_ <= current_ && current_ < right_);
  523.             return *current_;
  524.         }
  525.  
  526.         const T& operator*() const
  527.         {
  528.             assert(left_ <= current_ && current_ < right_);
  529.             return *current_;
  530.         }
  531.  
  532.         bool operator==(const iterator& right)
  533.         {
  534.             return current_ == right.current_;
  535.         }
  536.  
  537.         bool operator!=(const iterator& right)
  538.         {
  539.             return current_ != right.current_;
  540.         }
  541.  
  542.         bool operator<(const iterator& right)
  543.         {
  544.             return current_ < right.current_;
  545.         }
  546.  
  547.         bool operator>(const iterator& right)
  548.         {
  549.             return current_ > right.current_;
  550.         }
  551.  
  552.         bool operator<=(const iterator& right)
  553.         {
  554.             return current_ <= right.current_;
  555.         }
  556.  
  557.         bool operator>=(const iterator& right)
  558.         {
  559.             return current_ >= right.current_;
  560.         }
  561.  
  562.     private:
  563.         T* left_;
  564.         T* current_;
  565.         T* right_;
  566.     };
  567.  
  568.     class reverse_iterator
  569.     {
  570.     public:
  571.  
  572.         reverse_iterator(T* ptr, T* left, T* right) : current_(ptr), left_(left), right_(right) {}
  573.  
  574.         reverse_iterator(const reverse_iterator& copy) : current_(copy.current_), left_(copy.left_), right_(copy.right_) {}
  575.  
  576.         iterator getStraight() const
  577.         {
  578.             return iterator(current_, left_, right_);
  579.         }
  580.  
  581.         reverse_iterator& operator=(const reverse_iterator& right)
  582.         {
  583.             current_ = right.current_;
  584.             return *this;
  585.         }
  586.  
  587.         T operator[](int id)
  588.         {
  589.             return *(current_ - id);
  590.         }
  591.  
  592.         T* operator->() const
  593.         {
  594.             return current_;
  595.         }
  596.  
  597.         reverse_iterator operator+(int right) const
  598.         {
  599.             return reverse_iterator(current_ - right, left_, right_);
  600.         }
  601.  
  602.         reverse_iterator operator-(int right) const
  603.         {
  604.             return reverse_iterator(current_ + right, left_, right_);
  605.         }
  606.  
  607.         reverse_iterator operator++(int)
  608.         {
  609.             reverse_iterator res(current_, left_, right_);
  610.             current_--;
  611.             return res;
  612.         }
  613.  
  614.         reverse_iterator operator--(int)
  615.         {
  616.             reverse_iterator res(current_, left_, right_);
  617.             current_++;
  618.             return res;
  619.         }
  620.  
  621.         reverse_iterator& operator++()
  622.         {
  623.             --current_;
  624.             return *this;
  625.         }
  626.  
  627.         reverse_iterator& operator--()
  628.         {
  629.             ++current_;
  630.             return *this;
  631.         }
  632.  
  633.         reverse_iterator& operator+=(int right)
  634.         {
  635.             current_ += right;
  636.             return *this;
  637.         }
  638.  
  639.         reverse_iterator& operator-=(int right)
  640.         {
  641.             current_ -= right;
  642.             return *this;
  643.         }
  644.  
  645.         T& operator*()
  646.         {
  647.             assert(left_ <= current_ && current_ < right_);
  648.             return *current_;
  649.         }
  650.  
  651.         const T& operator*() const
  652.         {
  653.             assert(left_ <= current_ && current_ < right_);
  654.             return *current_;
  655.         }
  656.  
  657.         bool operator==(const reverse_iterator& right)
  658.         {
  659.             return current_ == right.current_;
  660.         }
  661.  
  662.         bool operator!=(const reverse_iterator& right)
  663.         {
  664.             return current_ != right.current_;
  665.         }
  666.  
  667.         bool operator<(const reverse_iterator& right)
  668.         {
  669.             return current_ > right.current_;
  670.         }
  671.  
  672.         bool operator>(const reverse_iterator& right)
  673.         {
  674.             return current_ < right.current_;
  675.         }
  676.  
  677.         bool operator<=(const reverse_iterator& right)
  678.         {
  679.             return current_ >= right.current_;
  680.         }
  681.  
  682.         bool operator>=(const reverse_iterator& right)
  683.         {
  684.             return current_ <= right.current_;
  685.         }
  686.  
  687.     private:
  688.         T* left_;
  689.         T* current_;
  690.         T* right_;
  691.     };
  692.  
  693.     iterator begin() const
  694.     {
  695.         return iterator(data_, data_, data_ + size_);
  696.     }
  697.  
  698.     iterator end() const
  699.     {
  700.         return iterator(data_ + size_, data_, data_ + size_);
  701.     }
  702.  
  703.     reverse_iterator rbegin() const
  704.     {
  705.         return reverse_iterator(data_ + size_ - 1, data_, data_ + size_);
  706.     }
  707.  
  708.     reverse_iterator rend() const
  709.     {
  710.         return reverse_iterator(data_ - 1, data_, data_ + size_);
  711.     }
  712.  
  713.     ~Vector()
  714.     {
  715.         delete[] data_;
  716.     }
  717.  
  718. private:
  719.     unsigned size_;
  720.     unsigned allocated_;
  721.     T* data_;
  722. };
RAW Paste Data
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!
 
Top