title: STL List Implementation
body: <p>I've implemented a C++ STL list for practice purpose (obviously all constructors &amp; methods aren't there). Most of the functions are working properly. </p>
  
  <pre><code>#ifndef list_H
  #define list_H
  
  #include &lt;iostream&gt;
  #include &lt;stdexcept&gt;
  
  template &lt;typename T&gt;
  class list {
  public:
      list &lt;T&gt; &amp; operator = (const list&lt;T&gt; &amp;);
      ~list();
      /* Modifiers */
      void push_back(T&amp;&amp; data);
      void push_back(T const&amp; data);
      void push_front(T&amp;&amp; data);
      void push_front(T const&amp; data);
      void pop_back();
      void pop_front();
      void swap(list &amp;x);
      void clear();
  
      /* Iterators */
      typedef T* iterator;
      typedef T* const const_iterator;
  
      const_iterator begin() const; // cbegin
      iterator begin();
  
      const_iterator end() const; //cend()
      iterator end();
  
      const_iterator rbegin() const;
      iterator rbegin();
  
      const_iterator rend() const;
      iterator rend();
  
      /* Capacity */
      size_t size() const;
      bool empty() const;
  
      /* Element Access */
      T&amp; front();
      T const&amp; front() const;
  
      T&amp; back();
      T const&amp; back() const;
  
      T&amp; at(T const indx);
      T const&amp; at(T const indx) const;
  
      T&amp; operator[] (T const indx);
      T const&amp; operator[] (T const indx) const;
  
  private:
      struct node {
          int data;
          node *next, *prev;
          node(T const&amp; data, node* next, node* prev)
              : data(data)
              , next(next)
              , prev(prev) {
          }
          node(T&amp;&amp; data, node* next, node* prev)
              : data(std::move(data))
              , next(next)
              , prev(prev) {
          }
      };
      int elements = 0;
      node *head = nullptr;
      node *tail = nullptr;
  };
  
  template &lt;typename T&gt;
  list &lt;T&gt; &amp; list&lt;T&gt;::operator = (const list&lt;T&gt; &amp; that) {
      node* tmp = head;
      while(head) {
          tmp = head;
          head = head-&gt;next;
          delete tmp;
      }
      elements = that.elements;
      head = that.head;
      tail = that.tail;
  }
  
  template &lt;typename T&gt;
  list &lt;T&gt;::~list() {
      node* tmp;
      while(head) {
          tmp = head;
          head = head-&gt;next;
          delete tmp;
      }
  }
  
  
  template &lt;typename T&gt;
  T&amp; list&lt;T&gt;:: front() {
      if(head == nullptr)
          throw std::runtime_error("Invalid Action!");
      return head-&gt;data;
  }
  
  template &lt;typename T&gt;
  T const&amp; list&lt;T&gt;:: front() const {
      if(head == nullptr)
          throw std::runtime_error("Invalid Action!");
      return head-&gt;data;
  }
  
  template &lt;typename T&gt;
  T&amp; list&lt;T&gt;:: back() {
      if(tail == nullptr)
          throw std::runtime_error("Invalid Action!");
      return tail-&gt;data;
  }
  
  template &lt;typename T&gt;
  T const&amp; list&lt;T&gt;:: back() const {
      if(tail == nullptr)
          throw std::runtime_error("Invalid Action!");
      return tail-&gt;data;
  }
  
  template &lt;typename T&gt;
  void list&lt;T&gt;::push_back(T const&amp; data) {
      node* newNode = new node(data, nullptr, tail);
      if(head == nullptr)
          head = newNode;
      if(tail != nullptr)
          tail-&gt;next = newNode;
      tail = newNode;
      ++elements;
  }
  
  template &lt;typename T&gt;
  void list&lt;T&gt;::push_back(T&amp;&amp; data) {
      node* newNode = new node(std::move(data), nullptr, tail);
      if(head == nullptr)
          head = newNode;
      if(tail != nullptr)
          tail-&gt;next = newNode;
      tail = newNode;
      ++elements;
  }
  
  template &lt;typename T&gt;
  void list&lt;T&gt;::push_front(T const&amp; data) {
      node* newNode = new node(data, head, nullptr);
      if(tail == nullptr)
          tail = newNode;
      if(head != nullptr)
          head-&gt;prev = newNode;
      head = newNode;
      ++elements;
  }
  
  template &lt;typename T&gt;
  void list&lt;T&gt;::push_front(T&amp;&amp; data) {
      node* newNode = new node(data, head, nullptr);
      if(tail == nullptr)
          tail = newNode;
      if(head != nullptr)
          head-&gt;prev = newNode;
      head = newNode;
      ++elements;
  }
  
  template &lt;typename T&gt;
  void list&lt;T&gt;::pop_front() {
      if(head == nullptr)
          throw std::runtime_error("Invalid Action");
      node *tmp = head;
      head = head-&gt;next;
      if(head != nullptr)
          head-&gt;prev = nullptr;
      --elements;
      delete tmp;
  }
  
  template &lt;typename T&gt;
  void list&lt;T&gt;::pop_back() {
      if(tail == nullptr)
          throw std::runtime_error("Invalid Action");
      node *tmp = tail;
      tail = tail-&gt;prev;
      if(tail != nullptr)
          tail-&gt;next = nullptr;
      --elements;
      delete tmp;
  }
  
  template &lt;typename T&gt;
  bool list&lt;T&gt;::empty() const {
      return head == nullptr;
  }
  
  template &lt;typename T&gt;
  size_t list&lt;T&gt;::size() const {
      return elements;
  }
  
  template &lt;typename T&gt;
  T&amp; list&lt;T&gt;::operator[] (T const indx) {
      int cont = 0;
      node *curr = head;
      while(curr) {
          if(cont == indx)
              return curr-&gt;data;
          curr = curr-&gt;next;
          ++cont;
      }
      return nullptr;
  }
  
  template &lt;typename T&gt;
  T const&amp; list&lt;T&gt;::operator[] (T const indx) const {
      int cont = 0;
      node *curr = head;
      while(curr) {
          if(cont == indx)
              return curr-&gt;data;
          curr = curr-&gt;next;
          ++cont;
      }
      return nullptr;
  }
  
  template &lt;typename T&gt;
  T&amp; list&lt;T&gt;::at(T const indx) {
      int cont = 0;
      node *curr = head;
      while(curr) {
          if(cont == indx)
              return curr-&gt;data;
          curr = curr-&gt;next;
      }
      return nullptr;
  }
  
  template &lt;typename T&gt;
  T const&amp; list&lt;T&gt;::at(T const indx) const {
      int cont = 0;
      node *curr = head;
      while(curr) {
          if(cont == indx)
              return curr-&gt;data;
          curr = curr-&gt;next;
      }
      return nullptr;
  }
  
  template &lt;typename T&gt;
  typename list&lt;T&gt;::const_iterator list&lt;T&gt;::begin() const {
      return head;
  }
  
  template &lt;typename T&gt;
  typename list&lt;T&gt;::iterator list&lt;T&gt;::begin() {
      return head;
  }
  
  
  template &lt;typename T&gt;
  typename list&lt;T&gt;::const_iterator list&lt;T&gt;::end() const {
      return tail;
  }
  
  template &lt;typename T&gt;
  typename list&lt;T&gt;::const_iterator list&lt;T&gt;::rbegin() const {
      return tail;
  }
  template &lt;typename T&gt;
  typename list&lt;T&gt;::iterator list&lt;T&gt;::rbegin() {
      return tail;
  }
  template &lt;typename T&gt;
  typename list&lt;T&gt;::const_iterator list&lt;T&gt;::rend() const {
      return head;
  }
  
  template &lt;typename T&gt;
  typename list&lt;T&gt;::iterator list&lt;T&gt;::rend() {
      return head;
  }
  
  template &lt;typename T&gt;
  typename list&lt;T&gt;::iterator list&lt;T&gt;::end() {
      return tail;
  }
  
  template &lt;typename T&gt;
  void list&lt;T&gt;::swap(list &amp;that) {
      std::swap(head, that.head);
      std::swap(tail, that.tail);
      std::swap(elements, that.elements);
  }
  
  template &lt;typename T&gt;
  void list&lt;T&gt;::clear() {
      node* curr = head;
      while(head) {
          curr = head;
          head = head-&gt;next;
          delete curr;
      }
      head = tail = nullptr;
      elements = 0;
  }
  
  #endif // list_H
  </code></pre>
  
  <p>Then I tested this program by:</p>
  
  <pre><code>int main(void) {
      deque&lt;int&gt; dq;
      dq.push_back(1);
      dq.push_back(2);
      dq.push_back(3);
      while(!dq.empty()) {
          int value = dq.back();
          std::cout &lt;&lt; value &lt;&lt; std::endl;
          dq.pop_back();
      }
      return 0;
  }
  </code></pre>
  
  <p>Well, output is:</p>
  
  <pre><code>3
  2 
  1
  </code></pre>
  
  <p><strong><em>But the program isn't terminating in my code::blocks</em></strong>. </p>
  
  <p>Then I compiled it with Ideone and the output is:</p>
  
  <pre><code>3
  2
  1
      *** Error in `./prog': double free or corruption (fasttop): 0x08923008 ***
      ======= Backtrace: =========
      /lib/i386-linux-gnu/i686/cmov/libc.so.6(+0x75e72)[0xb75f8e72]
      /lib/i386-linux-gnu/i686/cmov/libc.so.6(+0x76bb0)[0xb75f9bb0]
      /usr/lib/i386-linux-gnu/libstdc++.so.6(_ZdlPv+0x1f)[0xb77db82f]
      ./prog[0x8048a17]
      /lib/i386-linux-gnu/i686/cmov/libc.so.6(__libc_start_main+0xf5)[0xb759c8f5]
      ./prog[0x8048b41]
      ======= Memory map: ========
      08048000-08049000 r-xp 00000000 09:03 16269491   /home/TKjJyD/prog
      08049000-0804a000 rw-p 00001000 09:03 16269491   /home/TKjJyD/prog
      08923000-08944000 rw-p 00000000 00:00 0          [heap]
      b7581000-b7583000 rw-p 00000000 00:00 0 
      b7583000-b772c000 r-xp 00000000 09:03 16394299   /lib/i386-linux-gnu/i686/cmov/libc-2.17.so
      b772c000-b772d000 ---p 001a9000 09:03 16394299   /lib/i386-linux-gnu/i686/cmov/libc-2.17.so
      b772d000-b772f000 r--p 001a9000 09:03 16394299   /lib/i386-linux-gnu/i686/cmov/libc-2.17.so
      b772f000-b7730000 rw-p 001ab000 09:03 16394299   /lib/i386-linux-gnu/i686/cmov/libc-2.17.so
      b7730000-b7733000 rw-p 00000000 00:00 0 
      b7733000-b774e000 r-xp 00000000 09:03 16394343   /lib/i386-linux-gnu/libgcc_s.so.1
      b774e000-b774f000 rw-p 0001a000 09:03 16394343   /lib/i386-linux-gnu/libgcc_s.so.1
      b774f000-b7750000 rw-p 00000000 00:00 0 
      b7750000-b7791000 r-xp 00000000 09:03 16394296   /lib/i386-linux-gnu/i686/cmov/libm-2.17.so
      b7791000-b7792000 r--p 00040000 09:03 16394296   /lib/i386-linux-gnu/i686/cmov/libm-2.17.so
      b7792000-b7793000 rw-p 00041000 09:03 16394296   /lib/i386-linux-gnu/i686/cmov/libm-2.17.so
      b7793000-b786f000 r-xp 00000000 09:03 16679929   /usr/lib/i386-linux-gnu/libstdc++.so.6.0.18
      b786f000-b7870000 ---p 000dc000 09:03 16679929   /usr/lib/i386-linux-gnu/libstdc++.so.6.0.18
      b7870000-b7874000 r--p 000dc000 09:03 16679929   /usr/lib/i386-linux-gnu/libstdc++.so.6.0.18
      b7874000-b7875000 rw-p 000e0000 09:03 16679929   /usr/lib/i386-linux-gnu/libstdc++.so.6.0.18
      b7875000-b787c000 rw-p 00000000 00:00 0 
      b787e000-b7882000 rw-p 00000000 00:00 0 
      b7882000-b7883000 r-xp 00000000 00:00 0          [vdso]
      b7883000-b78a2000 r-xp 00000000 09:03 16394256   /lib/i386-linux-gnu/ld-2.17.so
      b78a2000-b78a3000 r--p 0001f000 09:03 16394256   /lib/i386-linux-gnu/ld-2.17.so
      b78a3000-b78a4000 rw-p 00020000 09:03 16394256   /lib/i386-linux-gnu/ld-2.17.so
      bfa1b000-bfa3c000 rw-p 00000000 00:00 0          [stack]
  </code></pre>
  
  <p>I think the problem is in <code>pop_back()</code> function. Can anyone know what happened?
  Thanks in advance!</p>