Pastebin is 300% more awesome when you are logged in. Sign Up, it's FREE!
Guest

List Example

By: Volatile_Pulse on Dec 14th, 2012  |  syntax: C++  |  size: 15.01 KB  |  hits: 29  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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. vp::list<T>& vp::list<T>::operator = (const list<T>& l) {
  269.    clear();
  270.  
  271.    for (T val : l)
  272.       push_back(val);
  273.  
  274.    return *this;
  275. }
  276.  
  277. template<class T>
  278. void vp::list<T>::assign(iterator first, iterator last) {
  279.    clear();
  280.  
  281.    for (; first != last; first ++)
  282.       push_back(*first);
  283. }
  284.  
  285. template<class T>
  286. void vp::list<T>::assign(unsigned n, const_reference value) {
  287.    clear();
  288.  
  289.    for (unsigned i = 0; i < n; i ++)
  290.       push_back(value);
  291. }
  292.  
  293. template<class T>
  294. typename vp::list<T>::reference vp::list<T>::back() {
  295.    if (empty())
  296.       throw std::logic_error("list: Invoked back() on empty list") ;
  297.  
  298.    return lastNode->value;
  299. }
  300.  
  301. template<class T>
  302. typename vp::list<T>::const_reference vp::list<T>::back() const {
  303.    if (empty())
  304.       throw std::logic_error("list: Invoked back() on empty list") ;
  305.  
  306.    return lastNode->value;
  307. }
  308.  
  309. template<class T>
  310. typename vp::list<T>::iterator vp::list<T>::begin() {
  311.    return iterator(firstNode);
  312. }
  313.  
  314. template<class T>
  315. typename vp::list<T>::const_iterator vp::list<T>::begin() const {
  316.    return iterator(firstNode);
  317. }
  318.  
  319. template<class T>
  320. void vp::list<T>::clear() {
  321.    while (firstNode != NULL) {
  322.       node *n = firstNode->next;
  323.       delete firstNode;
  324.       firstNode = n;
  325.    }
  326.  
  327.    lastNode = firstNode;
  328.    mSize = 0;
  329. }
  330.  
  331. template<class T>
  332. bool vp::list<T>::empty() const {
  333.    return !mSize;
  334. }
  335.  
  336. template<class T>
  337. typename vp::list<T>::iterator vp::list<T>::erase(iterator it) {
  338.    if (it != end()) {
  339.       if (firstNode == it.current)
  340.          firstNode = it.current->next;
  341.  
  342.       if (lastNode == it.current)
  343.          lastNode = it.current->prev;
  344.  
  345.       mSize --;
  346.       delete(it++).current;
  347.    }
  348.  
  349.    return it;
  350. }
  351.  
  352. template<class T>
  353. typename vp::list<T>::iterator vp::list<T>::erase(iterator first, iterator last) {
  354.    for (; first != last; first ++)
  355.       erase(first);
  356.  
  357.    return (++ last);
  358. }
  359.  
  360. template<class T>
  361. typename vp::list<T>::iterator vp::list<T>::end() {
  362.    return iterator();
  363. }
  364.  
  365. template<class T>
  366. typename vp::list<T>::const_iterator vp::list<T>::end() const {
  367.    return iterator();
  368. }
  369.  
  370. template<class T>
  371. typename vp::list<T>::reference vp::list<T>::front() {
  372.    if (empty())
  373.       throw std::logic_error("list: Invoked front() on empty list") ;
  374.  
  375.    return firstNode->value;
  376. }
  377.  
  378. template<class T>
  379. typename vp::list<T>::const_reference vp::list<T>::front() const {
  380.    if (empty())
  381.       throw std::logic_error("list: Invoked front() on empty list") ;
  382.  
  383.    return firstNode->value;
  384. }
  385.  
  386. template<class T>
  387. typename vp::list<T>::iterator vp::list<T>::insert(iterator it, const_reference value) {
  388.    iterator result(new node(value, it.current->prev, it.current->next));
  389.    mSize ++;
  390.    return result;
  391. }
  392.  
  393. template<class T>
  394. void vp::list<T>::insert(iterator it, unsigned n, const_reference value) {
  395.    for (unsigned i = 0; i < n; i ++)
  396.       it = insert(it, value);
  397. }
  398.  
  399. template<class T>
  400. void vp::list<T>::insert(iterator it, iterator first, iterator last) {
  401.    for (; first != last; first ++)
  402.       it = insert(it, *first);
  403. }
  404.  
  405. template<class T>
  406. unsigned vp::list<T>::max_size() const {
  407.    return mSize;
  408. }
  409.  
  410. template<class T>
  411. void vp::list<T>::merge(list<T> l) {
  412.    node *p = firstNode;
  413.  
  414.    while (l.size()) {
  415.       node *q = l.firstNode;
  416.  
  417.       if (q->value < p->value) {
  418.          l.firstNode = l.firstNode->next;
  419.          q->insert_before(p);
  420.  
  421.          if (p == firstNode)
  422.             firstNode = q;
  423.  
  424.          mSize ++;
  425.          l.mSize --;
  426.       }
  427.       else if (p == lastNode) {
  428.          l.firstNode = l.firstNode->next;
  429.          q->insert_after(p);
  430.          p = lastNode = q;
  431.          mSize ++;
  432.          l.mSize --;
  433.       }
  434.       else
  435.          p = p->next;
  436.    }
  437. }
  438.  
  439. template<class T>
  440. void vp::list<T>::pop_back() {
  441.    if (empty())
  442.       return;
  443.  
  444.    node *n = lastNode->prev;
  445.    n->next = NULL;
  446.    delete lastNode;
  447.    lastNode = n;
  448.    mSize --;
  449.  
  450.    if (empty())
  451.       firstNode = lastNode;
  452. }
  453.  
  454. template<class T>
  455. void vp::list<T>::pop_front() {
  456.    if (empty())
  457.       return;
  458.  
  459.    node *n = firstNode->next;
  460.    n->prev = NULL;
  461.    delete firstNode;
  462.    firstNode = n;
  463.    mSize --;
  464.  
  465.    if (empty())
  466.       lastNode = firstNode;
  467. }
  468.  
  469. template<class T>
  470. void vp::list<T>::push_back(T x) {
  471.    lastNode = new node(x, lastNode, NULL);
  472.  
  473.    if (firstNode == NULL)
  474.       firstNode = lastNode;
  475.  
  476.    mSize ++;
  477. }
  478.  
  479. template<class T>
  480. void vp::list<T>::push_front(T x) {
  481.    firstNode = new node(x, NULL, firstNode);
  482.  
  483.    if (lastNode == NULL)
  484.       lastNode = firstNode;
  485.  
  486.    mSize ++;
  487. }
  488.  
  489. /** Need to add and change to reverse_iterator **/
  490. template<class T>
  491. typename vp::list<T>::iterator vp::list<T>::rbegin() {
  492.    return iterator(lastNode);
  493. }
  494.  
  495. template<class T>
  496. void vp::list<T>::remove(const_reference value) {
  497.    for (iterator it(firstNode); it != end(); it ++)
  498.       if (*it == value)
  499.          erase(it);
  500. }
  501.  
  502. template<class T>
  503. typename vp::list<T>::iterator vp::list<T>::rend() {
  504.    return iterator();
  505. }
  506.  
  507. template<class T>
  508. void vp::list<T>::resize(unsigned n, T value) {
  509.    if (n < mSize)
  510.       while (mSize > n)
  511.          pop_back();
  512.    else
  513.       for (unsigned i = 0; i < n; i ++)
  514.          push_back(value);
  515. }
  516.  
  517. template<class T>
  518. void vp::list<T>::reverse() {
  519.    node* temp = lastNode;
  520.    lastNode = firstNode;
  521.    firstNode = temp;
  522.  
  523.    for (node* tempNode = temp; temp;  temp = temp->next) {
  524.       tempNode = temp->prev;
  525.       temp->prev = temp->next;
  526.       temp->next = tempNode;
  527.    }
  528. }
  529.  
  530. template<class T>
  531. unsigned int vp::list<T>::size() const {
  532.    return mSize;
  533. }
  534.  
  535. template<class T>
  536. void vp::list<T>::sort() {
  537.    if (size() <= 1)
  538.       return;
  539.  
  540.    for (int merges = 0, k = 1; merges != 1; k *= 2) {
  541.       node *p = firstNode, *q = p;
  542.  
  543.       for (int qsize = merges = 0; p; merges ++, p = q) {
  544.          for (qsize = 0; qsize < k && q; qsize ++, q = q->next);
  545.  
  546.          while (qsize && q) {
  547.             if (q->value <= p->value) {
  548.                if (q->next) {
  549.                   q = q->next;
  550.                   q->prev->insert_before(p);
  551.                }
  552.                else {
  553.                   q->insert_before(p);
  554.                   q = NULL;
  555.                   lastNode = lastNode->prev;
  556.                }
  557.  
  558.                if (p == firstNode)
  559.                   firstNode = firstNode->prev;
  560.  
  561.                qsize --;
  562.             }
  563.             else
  564.                p = p->next;
  565.          }
  566.       }
  567.    }
  568. }
  569.  
  570. //void splice(iterator it, list<T>& l);
  571. //void splice(iterator it, list<T>& l, iterator i);
  572. //void splice(iterator it, list<T>& l, iterator first, iterator last);
  573.  
  574. template<class T>
  575. void vp::list<T>::swap(list<T> l) {
  576.    list<T> temp = l;
  577.    l = *this;
  578.    this = temp;
  579. }
  580.  
  581. template<class T>
  582. void vp::list<T>::unique() {
  583.    for (iterator it = begin(); it != end(); it ++)
  584.       if ((it != begin()) && (*it == it.current->prev->value))
  585.          erase(it --);
  586. }
  587.  
  588. // void unique(BinaryPredicate binary_pred);
  589.  
  590. int main() {
  591.    using std::chrono::duration_cast;
  592.    using std::chrono::milliseconds;
  593.    std::chrono::high_resolution_clock clock;
  594.    srand(time(0));
  595.    // Default Ctor
  596.    vp::list<int> myList1;
  597.    auto start = clock.now();
  598.  
  599.    for (int i = 0; i < 1000000; i ++)
  600.       myList1.push_back(rand());
  601.  
  602.    auto end = clock.now();
  603.    
  604.    std::cout << "myList1 - It took "
  605.              << duration_cast<milliseconds>(end - start).count()
  606.              << "ms to add " << myList1.size() << " items.\n\n";
  607.              
  608.    start = clock.now();
  609.    myList1.sort();
  610.    end = clock.now();
  611.    
  612.    std::cout << "myList1 - It took "
  613.              << duration_cast<milliseconds>(end - start).count()
  614.              << "ms to sort " << myList1.size() << " items.\n\n";
  615.              
  616.    start = clock.now();
  617.    myList1.unique();
  618.    end = clock.now();
  619.    
  620.    std::cout << "myList1 - It took "
  621.              << duration_cast<milliseconds>(end - start).count()
  622.              << "ms to unique " << myList1.size() << " items.\n\n";
  623.              
  624.    start = clock.now();
  625.    myList1.reverse();
  626.    end = clock.now();
  627.    
  628.    std::cout << "myList1 - It took "
  629.              << duration_cast<milliseconds>(end - start).count()
  630.              << "ms to reverse " << myList1.size() << " items.\n\n";
  631.              
  632.    return 0;
  633. }