SHARE
TWEET

List Example

Volatile_Pulse Dec 14th, 2012 (edited) 42 Never
  1. #include <iostream>
  2. #include <stdexcept>
  3. #include <cstdlib>
  4. #include <ctime>
  5. #include <chrono>
  6.  
  7. namespace vp {
  8.    template<class T>
  9.    class list {
  10.       private:
  11.          struct node {
  12.             node();
  13.             node(T Value, node *pnode);
  14.             node(T Value, node *Prev, node *Next);
  15.             ~node();
  16.             void insert_after(node *pnode);
  17.             void insert_before(node *pnode);
  18.             void remove();
  19.             T value;
  20.             node *prev;
  21.             node *next;
  22.          };
  23.          node *firstNode;
  24.          node *lastNode;
  25.          unsigned int mSize;
  26.          typedef T& reference;
  27.          typedef const T& const_reference;
  28.       public:
  29.          class iterator {
  30.             private:
  31.                node *current;
  32.             public:
  33.                friend class list<T>;
  34.                iterator();
  35.                iterator(node* node);
  36.                reference operator ->();
  37.                reference operator *();
  38.                bool operator ==(const iterator it) const;
  39.                bool operator !=(const iterator it) const;
  40.                iterator& operator ++();
  41.                iterator operator ++(int);
  42.                iterator& operator --();
  43.                iterator operator --(int);
  44.          };
  45.       private:
  46.          typedef const typename vp::list<T>::iterator const_iterator;
  47.       public:
  48.          list();
  49.          list(unsigned n, const_reference value = T());
  50.          list(list<T>& x);
  51.          ~list();
  52.          bool operator == (const list<T>& l);
  53.          bool operator < (const list<T>& l);
  54.          bool operator > (const list<T>& l);
  55.          bool operator != (const list<T>& l);
  56.          bool operator >= (const list<T>& l);
  57.          bool operator <= (const list<T>& l);
  58.          list<T>& operator =(const list<T>& l);
  59.          void assign(iterator first, iterator last);
  60.          void assign(unsigned n, const_reference value);
  61.          reference back();
  62.          const_reference back() const;
  63.          iterator begin();
  64.          const_iterator begin() const;
  65.          void clear();
  66.          bool empty() const;
  67.          iterator end();
  68.          const_iterator end() const;
  69.          iterator erase(iterator it);
  70.          iterator erase(iterator first, iterator last);
  71.          reference front();
  72.          const_reference front() const;
  73.          iterator insert(iterator it, const_reference value);
  74.          void insert(iterator it, unsigned n, const_reference value);
  75.          void insert(iterator it, iterator first, iterator last);
  76.          unsigned max_size() const;
  77.          void merge(list<T> l);
  78.          // void merge (list<T>& l, Compare comp);
  79.          void pop_back();
  80.          void pop_front();
  81.          void push_back(T x);
  82.          void push_front(T x);
  83.          iterator rbegin();
  84.          // reverse_iterator rbegin();
  85.          // const_reverse_iterator rbegin() const;
  86.          void remove(const_reference value);
  87.          // void remove_if(Predicate pred);
  88.          iterator rend();
  89.          // reverse_iterator rend();
  90.          // const_reverse_iterator rend() const;
  91.          void resize(unsigned n, T value = T());
  92.          void reverse();
  93.          unsigned int size() const;
  94.          void sort();
  95.          // void sort(Compare comp);
  96.          // void splice(iterator it, list<T>& l);
  97.          // void splice(iterator it, list<T>& l, iterator i);
  98.          // void splice(iterator it, list<T>& l, iterator first, iterator last);
  99.          void swap(list<T> l);
  100.          void unique();
  101.          void unique(BinaryPredicate binary_pred);
  102.    };
  103. }
  104.  
  105. /** Node definitions **/
  106. template<class T>
  107. vp::list<T>::node::node() : value(T()), prev(NULL), next(NULL) {}
  108.  
  109. template<class T>
  110. vp::list<T>::node::node(T Value, node *pnode) :
  111.    value(Value), prev(pnode->prev), next(pnode) {
  112.    pnode->prev = this;
  113.  
  114.    if (prev)
  115.       prev->next = this;
  116. }
  117.  
  118. template<class T>
  119. vp::list<T>::node::node(T Value, node *Prev, node *Next) :
  120.    value(Value), prev(Prev), next(Next) {
  121.    if (prev)
  122.       prev->next = this;
  123.  
  124.    if (next)
  125.       next->prev = this;
  126. }
  127.  
  128. template<class T>
  129. vp::list<T>::node::~node() {
  130.    remove();
  131. }
  132.  
  133. template<class T>
  134. void vp::list<T>::node::insert_after(node *pnode) {
  135.    if (!pnode || pnode == this)
  136.       return;
  137.  
  138.    remove();
  139.    prev = pnode;
  140.    next = pnode->next;
  141.  
  142.    if (pnode->next)
  143.       pnode->next->prev = this;
  144.  
  145.    pnode->next = this;
  146. }
  147.  
  148. template<class T>
  149. void vp::list<T>::node::insert_before(node *pnode) {
  150.    if (!pnode || pnode == this)
  151.       return;
  152.  
  153.    remove();
  154.    next = pnode;
  155.    prev = pnode->prev;
  156.  
  157.    if (pnode->prev)
  158.       pnode->prev->next = this;
  159.  
  160.    pnode->prev = this;
  161. }
  162.  
  163. template<class T>
  164. void vp::list<T>::node::remove() {
  165.    if (prev)
  166.       prev->next = next;
  167.  
  168.    if (next)
  169.       next->prev = prev;
  170.  
  171.    next = prev = NULL;
  172. }
  173.  
  174. /** Iterator definitions **/
  175. template<class T>
  176. vp::list<T>::iterator::iterator() :
  177.    current(NULL) {}
  178.  
  179. template<class T>
  180. vp::list<T>::iterator::iterator(node *n) :
  181.    current(n) {}
  182.  
  183. template<class T>
  184. typename vp::list<T>::reference vp::list<T>::iterator::operator ->() {
  185.    return current->value;
  186. }
  187.  
  188. template<class T>
  189. typename vp::list<T>::reference vp::list<T>::iterator::operator *() {
  190.    return current->value;
  191. }
  192.  
  193. template<class T>
  194. bool vp::list<T>::iterator::operator ==(const iterator it) const {
  195.    return (current == it.current);
  196. }
  197.  
  198. template<class T>
  199. bool vp::list<T>::iterator::operator !=(const iterator it) const {
  200.    return !operator == (it);
  201. }
  202.  
  203. template<class T>
  204. typename vp::list<T>::iterator& vp::list<T>::iterator::operator ++() {
  205.    if (current)
  206.       current = current->next;
  207.  
  208.    return *this;
  209. }
  210.  
  211. template<class T>
  212. typename vp::list<T>::iterator vp::list<T>::iterator::operator ++(int) {
  213.    iterator result = *this;
  214.  
  215.    if (current)
  216.       current = current->next;
  217.  
  218.    return result;
  219. }
  220.  
  221. template<class T>
  222. typename vp::list<T>::iterator& vp::list<T>::iterator::operator --() {
  223.    if (current)
  224.       current = current->prev;
  225.  
  226.    return *this;
  227. }
  228.  
  229. template<class T>
  230. typename vp::list<T>::iterator vp::list<T>::iterator::operator --(int) {
  231.    iterator result = *this;
  232.  
  233.    if (current)
  234.       current = current->prev;
  235.  
  236.    return result;
  237. }
  238.  
  239. /** List definitions **/
  240. template<class T>
  241. vp::list<T>::list() :
  242.    firstNode(NULL), lastNode(NULL), mSize(0) {}
  243.  
  244. template<class T>
  245. vp::list<T>::list(unsigned n, const_reference value) :
  246.    firstNode(NULL), lastNode(NULL), mSize(0) {
  247.    for (unsigned i = 0; i < n; i ++)
  248.       push_back(value);
  249. }
  250.  
  251. template<class T>
  252. vp::list<T>::list(list<T>& x) :
  253.    firstNode(NULL), lastNode(NULL), mSize(0) {
  254.    for (auto it : x)
  255.       push_back(it);
  256. }
  257.  
  258. template<class T>
  259. vp::list<T>::~list() {
  260.    while (firstNode != NULL) {
  261.       node *n = firstNode->next;
  262.       delete firstNode;
  263.       firstNode = n;
  264.    }
  265. }
  266.  
  267. template<class T>
  268. bool vp::list<T>::operator == (const list<T>& l) {
  269.    if (mSize != l.mSize)
  270.       return false;
  271.    for(vp::list<T>::iterator lhsIt = firstNode, rhsIt = l.firstNode; lhsIt != NULL; lhsIt ++, rhsIt ++)
  272.       if (*lhsIt != *rhsIt)
  273.          return false;
  274.    return true;
  275. }
  276.  
  277. template<class T>
  278. bool vp::list<T>::operator < (const list<T>& l) {
  279.    if (mSize < l.mSize)
  280.       return true;
  281.    else if (mSize > l.mSize)
  282.       return false;
  283.    for(vp::list<T>::iterator lhsIt = firstNode, rhsIt = l.firstNode; lhsIt != NULL; lhsIt ++, rhsIt ++)
  284.       if (*lhsIt < *rhsIt)
  285.          return true;
  286.       else if (*lhsIt > *rhsIt)
  287.          return false;
  288.    return false;
  289. }
  290.  
  291. template<class T>
  292. bool vp::list<T>::operator > (const list<T>& l) {
  293.    if (mSize > l.mSize)
  294.       return true;
  295.    else if (mSize < l.mSize)
  296.       return false;
  297.    for(vp::list<T>::iterator lhsIt = firstNode, rhsIt = l.firstNode; lhsIt != NULL; lhsIt ++, rhsIt ++)
  298.       if (*lhsIt > *rhsIt)
  299.          return true;
  300.       else if (*lhsIt < *rhsIt)
  301.          return false;
  302.    return false;
  303. }
  304.  
  305. template<class T>
  306. bool vp::list<T>::operator != (const list<T>& l) {
  307.    return !(*this == l);
  308. }
  309.  
  310. template<class T>
  311. bool vp::list<T>::operator >= (const list<T>& l) {
  312.    return !(*this < l);
  313. }
  314.  
  315. template<class T>
  316. bool vp::list<T>::operator <= (const list<T>& l) {
  317.    return !(*this > l);
  318. }
  319.  
  320. template<class T>
  321. vp::list<T>& vp::list<T>::operator = (const list<T>& l) {
  322.    clear();
  323.  
  324.    for (T val : l)
  325.       push_back(val);
  326.  
  327.    return *this;
  328. }
  329.  
  330. template<class T>
  331. void vp::list<T>::assign(iterator first, iterator last) {
  332.    clear();
  333.  
  334.    for (; first != last; first ++)
  335.       push_back(*first);
  336. }
  337.  
  338. template<class T>
  339. void vp::list<T>::assign(unsigned n, const_reference value) {
  340.    clear();
  341.  
  342.    for (unsigned i = 0; i < n; i ++)
  343.       push_back(value);
  344. }
  345.  
  346. template<class T>
  347. typename vp::list<T>::reference vp::list<T>::back() {
  348.    if (empty())
  349.       throw std::logic_error("list: Invoked back() on empty list") ;
  350.  
  351.    return lastNode->value;
  352. }
  353.  
  354. template<class T>
  355. typename vp::list<T>::const_reference vp::list<T>::back() const {
  356.    if (empty())
  357.       throw std::logic_error("list: Invoked back() on empty list") ;
  358.  
  359.    return lastNode->value;
  360. }
  361.  
  362. template<class T>
  363. typename vp::list<T>::iterator vp::list<T>::begin() {
  364.    return iterator(firstNode);
  365. }
  366.  
  367. template<class T>
  368. typename vp::list<T>::const_iterator vp::list<T>::begin() const {
  369.    return iterator(firstNode);
  370. }
  371.  
  372. template<class T>
  373. void vp::list<T>::clear() {
  374.    while (firstNode != NULL) {
  375.       node *n = firstNode->next;
  376.       delete firstNode;
  377.       firstNode = n;
  378.    }
  379.  
  380.    lastNode = firstNode;
  381.    mSize = 0;
  382. }
  383.  
  384. template<class T>
  385. bool vp::list<T>::empty() const {
  386.    return !mSize;
  387. }
  388.  
  389. template<class T>
  390. typename vp::list<T>::iterator vp::list<T>::erase(iterator it) {
  391.    if (it != end()) {
  392.       if (firstNode == it.current)
  393.          firstNode = it.current->next;
  394.  
  395.       if (lastNode == it.current)
  396.          lastNode = it.current->prev;
  397.  
  398.       mSize --;
  399.       delete(it++).current;
  400.    }
  401.  
  402.    return it;
  403. }
  404.  
  405. template<class T>
  406. typename vp::list<T>::iterator vp::list<T>::erase(iterator first, iterator last) {
  407.    for (; first != last; first ++)
  408.       erase(first);
  409.  
  410.    return (++ last);
  411. }
  412.  
  413. template<class T>
  414. typename vp::list<T>::iterator vp::list<T>::end() {
  415.    return iterator();
  416. }
  417.  
  418. template<class T>
  419. typename vp::list<T>::const_iterator vp::list<T>::end() const {
  420.    return iterator();
  421. }
  422.  
  423. template<class T>
  424. typename vp::list<T>::reference vp::list<T>::front() {
  425.    if (empty())
  426.       throw std::logic_error("list: Invoked front() on empty list") ;
  427.  
  428.    return firstNode->value;
  429. }
  430.  
  431. template<class T>
  432. typename vp::list<T>::const_reference vp::list<T>::front() const {
  433.    if (empty())
  434.       throw std::logic_error("list: Invoked front() on empty list") ;
  435.  
  436.    return firstNode->value;
  437. }
  438.  
  439. template<class T>
  440. typename vp::list<T>::iterator vp::list<T>::insert(iterator it, const_reference value) {
  441.    iterator result(new node(value, it.current->prev, it.current->next));
  442.    mSize ++;
  443.    return result;
  444. }
  445.  
  446. template<class T>
  447. void vp::list<T>::insert(iterator it, unsigned n, const_reference value) {
  448.    for (unsigned i = 0; i < n; i ++)
  449.       it = insert(it, value);
  450. }
  451.  
  452. template<class T>
  453. void vp::list<T>::insert(iterator it, iterator first, iterator last) {
  454.    for (; first != last; first ++)
  455.       it = insert(it, *first);
  456. }
  457.  
  458. template<class T>
  459. unsigned vp::list<T>::max_size() const {
  460.    return mSize;
  461. }
  462.  
  463. template<class T>
  464. void vp::list<T>::merge(list<T> l) {
  465.    node *p = firstNode;
  466.  
  467.    while (l.size()) {
  468.       node *q = l.firstNode;
  469.  
  470.       if (q->value < p->value) {
  471.          l.firstNode = l.firstNode->next;
  472.          q->insert_before(p);
  473.  
  474.          if (p == firstNode)
  475.             firstNode = q;
  476.  
  477.          mSize ++;
  478.          l.mSize --;
  479.       }
  480.       else if (p == lastNode) {
  481.          l.firstNode = l.firstNode->next;
  482.          q->insert_after(p);
  483.          p = lastNode = q;
  484.          mSize ++;
  485.          l.mSize --;
  486.       }
  487.       else
  488.          p = p->next;
  489.    }
  490. }
  491.  
  492. template<class T>
  493. void vp::list<T>::pop_back() {
  494.    if (empty())
  495.       return;
  496.  
  497.    node *n = lastNode->prev;
  498.    n->next = NULL;
  499.    delete lastNode;
  500.    lastNode = n;
  501.    mSize --;
  502.  
  503.    if (empty())
  504.       firstNode = lastNode;
  505. }
  506.  
  507. template<class T>
  508. void vp::list<T>::pop_front() {
  509.    if (empty())
  510.       return;
  511.  
  512.    node *n = firstNode->next;
  513.    n->prev = NULL;
  514.    delete firstNode;
  515.    firstNode = n;
  516.    mSize --;
  517.  
  518.    if (empty())
  519.       lastNode = firstNode;
  520. }
  521.  
  522. template<class T>
  523. void vp::list<T>::push_back(T x) {
  524.    lastNode = new node(x, lastNode, NULL);
  525.  
  526.    if (firstNode == NULL)
  527.       firstNode = lastNode;
  528.  
  529.    mSize ++;
  530. }
  531.  
  532. template<class T>
  533. void vp::list<T>::push_front(T x) {
  534.    firstNode = new node(x, NULL, firstNode);
  535.  
  536.    if (lastNode == NULL)
  537.       lastNode = firstNode;
  538.  
  539.    mSize ++;
  540. }
  541.  
  542. /** Need to add and change to reverse_iterator **/
  543. template<class T>
  544. typename vp::list<T>::iterator vp::list<T>::rbegin() {
  545.    return iterator(lastNode);
  546. }
  547.  
  548. template<class T>
  549. void vp::list<T>::remove(const_reference value) {
  550.    for (iterator it(firstNode); it != end(); it ++)
  551.       if (*it == value)
  552.          erase(it);
  553. }
  554.  
  555. template<class T>
  556. typename vp::list<T>::iterator vp::list<T>::rend() {
  557.    return iterator();
  558. }
  559.  
  560. template<class T>
  561. void vp::list<T>::resize(unsigned n, T value) {
  562.    if (n < mSize)
  563.       while (mSize > n)
  564.          pop_back();
  565.    else
  566.       for (unsigned i = 0; i < n; i ++)
  567.          push_back(value);
  568. }
  569.  
  570. template<class T>
  571. void vp::list<T>::reverse() {
  572.    node* temp = lastNode;
  573.    lastNode = firstNode;
  574.    firstNode = temp;
  575.  
  576.    for (node* tempNode = temp; temp;  temp = temp->next) {
  577.       tempNode = temp->prev;
  578.       temp->prev = temp->next;
  579.       temp->next = tempNode;
  580.    }
  581. }
  582.  
  583. template<class T>
  584. unsigned int vp::list<T>::size() const {
  585.    return mSize;
  586. }
  587.  
  588. template<class T>
  589. void vp::list<T>::sort() {
  590.    if (size() <= 1)
  591.       return;
  592.  
  593.    for (int merges = 0, k = 1; merges != 1; k *= 2) {
  594.       node *p = firstNode, *q = p;
  595.  
  596.       for (int qsize = merges = 0; p; merges ++, p = q) {
  597.          for (qsize = 0; qsize < k && q; qsize ++, q = q->next);
  598.  
  599.          while (qsize && q) {
  600.             if (q->value <= p->value) {
  601.                if (q->next) {
  602.                   q = q->next;
  603.                   q->prev->insert_before(p);
  604.                }
  605.                else {
  606.                   q->insert_before(p);
  607.                   q = NULL;
  608.                   lastNode = lastNode->prev;
  609.                }
  610.  
  611.                if (p == firstNode)
  612.                   firstNode = firstNode->prev;
  613.  
  614.                qsize --;
  615.             }
  616.             else
  617.                p = p->next;
  618.          }
  619.       }
  620.    }
  621. }
  622.  
  623. //void splice(iterator it, list<T>& l);
  624. //void splice(iterator it, list<T>& l, iterator i);
  625. //void splice(iterator it, list<T>& l, iterator first, iterator last);
  626.  
  627. template<class T>
  628. void vp::list<T>::swap(list<T> l) {
  629.    list<T> temp = l;
  630.    l = *this;
  631.    this = temp;
  632. }
  633.  
  634. template<class T>
  635. void vp::list<T>::unique() {
  636.    for (iterator it = begin(); it != end(); it ++)
  637.       if ((it != begin()) && (*it == it.current->prev->value))
  638.          erase(it --);
  639. }
  640.  
  641. template<class T>
  642. void vp::list<T>::unique(BinaryPredicate binary_pred) {
  643.    for (iterator it = begin(); it != end(); it ++)
  644.       if ((it != begin()) && (binary_pred(*it, it.current->prev->value)))
  645.          erase(it --);
  646. }
  647.  
  648. bool isSame(int a, int b) {
  649.    return a == b;
  650. }
  651.  
  652. int main() {
  653.    vp::list<int> list1, list2;
  654.    for (int i = 0; i < 10; i ++) {
  655.       list1.push_back(i);
  656.       list2.push_back(i);
  657.    }
  658.  
  659.    list1.pop_back();
  660.    list1.push_back(7);
  661.  
  662.    list1.sort();
  663.    list1.unique(isSame);
  664.  
  665.    for (auto it : list1)
  666.       std::cout << *it << "\n";
  667.  
  668.    return 0;
  669. }
RAW Paste Data
Top