C++ Custom List Iterator Errors

Question

I have started writing my own library with common data structures, for educational purposes only (ie: personal practice). However, I encountered a few problems that I cannot seem to resolve myself even on the singly linked list. I am not a C++ expert and thus my code may have some problems, so please don't be harsh on me :)

I have tried to implement a list_node class which declares and defines a node for a list, a list_iterator class which acts as a forward iterator that the singly linked list requires, as well as the list class which is supposed to give make use of the previously mentioned classes and provide the functionality for the list.

I will attach now the code and the errors I get under Visual Studio.

list_node.h

/**
 *  list_node.h
 *
 *  @author Raul Butuc.
 *  @version 1.0.0 16/03/2015
 */

#pragma once

#include "list.h"
#include "list_iterator.h"

namespace my_library {

  template <class _Tp>
  class list_node {

    friend class list<_Tp>;
    friend class list_iterator<_Tp>;

    private:
      _Tp m_Node;
      list_node<_Tp> *m_pNext;

      list_node(const _Tp&, list_node<_Tp>*);
      ~list_node();
  };

  template <class _Tp>
  list_node<_Tp>::list_node(const _Tp& node, list_node<_Tp>* next) : m_Node(node), m_pNext(next) {}

  template <class _Tp>
  list_node<_Tp>::~list_node() {
    delete m_pNext;
  }

}

list_iterator.h

/**
 *  list_iterator.h
 *
 *  @author Raul Butuc.
 *  @version 1.0.0 16/03/2015
 */

#pragma once

#include <cassert>
#include <iterator>
#include "list.h"
#include "list_node.h"

namespace my_library {

  template <class _Tp> class list;
  template <class _Tp> class list_node;

  template <class _Tp>
  class list_iterator {

    public:
      // line below has error C2059: syntax error : '<'
      // as well as error C2238: unexpected token(s) preceding ';' 
      friend class list<_Tp>;
      typedef list_iterator<_Tp> iterator;
      typedef size_t size_type;
      typedef _Tp value_type;
      typedef _Tp& reference;
      typedef _Tp* pointer;
      typedef std::forward_iterator_tag iterator_category;
      typedef int difference_type;

      const iterator& operator++();
      const iterator& operator++(int);
      reference operator*();
      pointer operator->();
      bool operator==(const iterator&) const;
      bool operator!=(const iterator&) const;

    private:
      list_node<_Tp>* m_pNode;
      list_iterator(list_node<_Tp>*);

  };

  template <class _Tp>
  list_iterator<_Tp>::list_iterator(list_node<_Tp>* pNode) : m_pNode(pNode) {}

  template <class _Tp>
  const list_iterator<_Tp>::iterator& list_iterator<_Tp>::operator++() {
    assert(m_pNode != NULL);
    m_pNode = m_pNode->m_pNext;
    return *this;
  }

  template <class _Tp>
  const list_iterator<_Tp>::iterator& list_iterator<_Tp>::operator++(int) {
    list_iterator<_Tp>::iterator _tmp = *this;
    ++(*this);
    return _tmp;
  }

  template <class _Tp>
  list_iterator<_Tp>::reference list_iterator<_Tp>::operator*() {
    return m_pNode->m_Node;
  }

  template <class _Tp>
  list_iterator<_Tp>::pointer list_iterator<_Tp>::operator->() {
    return m_pNode;
  }

  template <class _Tp>
  bool list_iterator<_Tp>::operator==(const list_iterator<_Tp>::iterator& other) const {
    return m_pNode == other->m_pNode;
  }

  template <class _Tp>
  bool list_iterator<_Tp>::operator!=(const list_iterator<_Tp>::iterator& other) const {
    return m_pNode != other->m_pNode;
  }

}

list.h

/**
 *  list.h
 *
 *  @author Raul Butuc.
 *  @version 1.0.0 16/03/2015
 */

#pragma once

#include "list_node.h"
#include "list_iterator.h"

namespace my_library {

  template <class _Tp>
  class list {

    public:
      typedef list_iterator<_Tp> iterator;

      list();
      ~list();

      bool empty() const;
      void push_back(const _Tp&);

      iterator begin();
      iterator end();

    private:
      list_node<_Tp>* m_pHead;
      list_node<_Tp>* m_pTail;
  };

  template <class _Tp>
  list<_Tp>::list() : m_pHead(NULL), m_pTail(NULL) {}

  template <class _Tp>
  list<_Tp>::~list() {
    delete m_pHead;
  }

  template <class _Tp>
  bool list<_Tp>::empty() const {
    return m_pHead == NULL;
  }

  template <class _Tp>
  void list<_Tp>::push_back(const _Tp& node) {
    list_node<_Tp>* _node = new list_node<_Tp>(node, NULL);
    if (m_pHead == NULL) {
      m_pHead = _node;
    }
    else {
      m_pTail->m_pNext = _node;
    }
    m_pTail = _node;
  }

  template <class _Tp>
  list<_Tp>::iterator list<_Tp>::begin() {
    return list_iterator<_Tp>(m_pHead);
  }

  template <class _Tp>
  list<_Tp>::iterator list<_Tp>::end() {
    return list_iterator<_Tp>(NULL);
  }

}

test.cpp

/**
 *  Test.cpp
 *
 *  @author Raul Butuc.
 *  @version 1.0.0 16/03/2015
 */

#include <iostream>
#include "list.h"

using std::cout;
using namespace my_library;

int main(int argc, char* argv[]) {
  list<int> list;

  if (list.empty()) {
    std::cout << "List is empty" << "\n";
  }

  for (int i = 0; i < 100; i += 10) {
    list.push_back(i);
  }

  // Here it should allow me to write something like:
  // list<int>::iterator it = list.begin();
  // However, it does not. Could someone please explain
  // why that is so? Sorry if this is due to a naive mistake
  // but I am trying to learn. Thanks again :)
  list_iterator<int> it = list.begin();

  for (; it != list.end(); ++it) {
    std::cout << *it << " ";
  }
  std::cout << "\n";

  system("pause");
  return 0;
}

Errors I get at compilation

1>------ Build started: Project: List, Configuration: Debug Win32 ------
1> Test.cpp
1>d:...\list_iterator.h(23): error C2059: syntax error : '<'
1>\d:...\list_iterator.h(43) : see reference to class template instantiation 'my_library::list_iterator<_Tp>' being compiled
1>d:...\list_iterator.h(23): error C2238: unexpected token(s) preceding ';'
1>d:...\list_iterator.h(40): error C2143: syntax error : missing ';' before '<'
1>d:...\list_iterator.h(40): error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
1>d:...\list_iterator.h(40): error C2238: unexpected token(s) preceding ';'
1>d:...\list_iterator.h(41): error C2061: syntax error : identifier 'list_node'
1>d:...\list_iterator.h(46): error C2061: syntax error : identifier 'list_node'
1>d:...\list_iterator.h(49): warning C4346: 'my_library::list_iterator<_Tp>::iterator' : dependent name is not a type
1> prefix with 'typename' to indicate a type
1>d:...\list_iterator.h(49): error C2143: syntax error : missing ';' before '&'
1>d:...\list_iterator.h(49): error C2065: '_Tp' : undeclared identifier
1>d:...\list_iterator.h(49): error C2923: 'my_library::list_iterator' : '_Tp' is not a valid template type argument for parameter '_Tp'
1>d:...\list_iterator.h(53): error C2509: '++' : member function not declared in 'my_library::list_iterator'
1>
d:...\list_iterator.h(18) : see declaration of 'my_library::list_iterator'
1>d:...\list_iterator.h(53): fatal error C1903: unable to recover from previous error(s); stopping compilation
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

Thank you very much for taking your time!

EDIT:

Thanks mebob, that was indeed the main problem. However, after fixing that, I get some errors on line 52 and 56 in list_iterator.h:

1>d:\programming - data structures\list\list\list_iterator.h(52): warning C4346: 'my_library::list_iterator::iterator' : dependent name is not a type
1> prefix with 'typename' to indicate a type
1>d:\programming - data structures\list\list\list_iterator.h(52): error C2143: syntax error : missing ';' before '&'
1>d:\programming - data structures\list\list\list_iterator.h(52): error C2065: 'T' : undeclared identifier
1>d:\programming - data structures\list\list\list_iterator.h(52): error C2923: 'my_library::list_iterator' : 'T' is not a valid template type argument for parameter 'T'
1>d:\programming - data structures\list\list\list_iterator.h(56): error C2509: '++' : member function not declared in 'my_library::list_iterator'
1>
d:\programming - data structures\list\list\list_iterator.h(21) : see declaration of 'my_library::list_iterator'
1>d:\programming - data structures\list\list\list_iterator.h(56): fatal error C1903: unable to recover from previous error(s); stopping compilation

I also changed from _Tp to T in all the classes (in my code, didn't update this here)

EDIT 2:

Even after getting over those errors, it seems that it won't compile, this time because of the operators.

The code that is directly involved is:

  // other code...
  template <class _Tp>
  typename list_iterator<_Tp>::pointer list_iterator<_Tp>::operator->() {
    return m_pNode;
  }

  template <class _Tp>
  bool list_iterator<_Tp>::operator==(const typename list_iterator<_Tp>::iterator& other) const {
    /*  error C2678: binary '->' : no operator found which takes a left-hand operand
      of type 'const my_library::list_iterator<_Tp>' (or there is no acceptable conversion) */
    return m_pNode == other->m_pNode;
  }
  // other code...

From list_iterator.h

It would be nice if you highlighted the first line that causes the error. — Neil Kirk, Mar 17 '15 at 01:13
Sorry for that, I didn't realise that line numbers aren't on. Give me one minute. — , Mar 17 '15 at 01:17
You may be using a reserved identifier http://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore-in-a-c-identifier — Neil Kirk, Mar 17 '15 at 01:24
@NeilKirk I do think you're right but I don't think that's where the compilation error is arising from. — chbaker0, Mar 17 '15 at 01:25

chbaker0 · Accepted Answer · 2015-03-17T02:01:10.770

0

You must have forward declarations, like so:

template <class _Tp> class list;
template <class _Tp> class list_iterator;

before your friend declarations because otherwise, when the compiler sees friend class list it doesn't know to expect a template argument list.

As for your other error, you must use const typename list_iterator<_Tp>::iterator& for your type. Any time you refer to a type that's a member of a templated class (or struct) you must use the typename keyword beforehand to clarify to the compiler that you are expecting it to be a type.

Your last error is simply because you are attempting to call non-const operator->() on a const. The fix is to just create a const version of it that returns a const pointer.

Also, as Neil Kirk commented, _Tp is probably a reserved identifier so you shouldn't be using that.

edited Mar 17 '15 at 02:01

answered Mar 17 '15 at 01:24

chbaker0

1,758
2
13
27

Thanks! I tried doing the same, but I wrote it like this instead: template class list<_Tp>;
However, I still get errors about this line (52) in list_iterator.h: const list_iterator<_Tp>::iterator& list_iterator<_Tp>::operator++() { – Mar 17 '15 at 01:28
1

@MasterKoder you must use `const typename list_iterator<_Tp>::iterator&` for your type. Any time you refer to a type that's a member of a templated class (or struct) you must use the `typename` keyword beforehand to clarify to the compiler that you are expecting it to be a type. – chbaker0 Mar 17 '15 at 01:34
1

@MasterKoder as far as I'm aware this is due to the fact that different specializations could define a certain name as a type in one and a value in another, but when parsing the compiler must know which it is. – chbaker0 Mar 17 '15 at 01:35
Hmm, I still get an error, and I really have no idea why it complains. The -> operator is defined before the == and != operators which make use of it. Do you have any idea what might be causing it? (I added the error and the code in a 2nd edit in the main post). Thanks again! – Mar 17 '15 at 01:54
1

@MasterKoder The problem is that you have no `const` version of `operator->()` but you're calling it on a `const` qualified `list_iterator<_Tp>::iterator&`. You must create another version of your `operator->()` which is `const` qualified and that returns a `const` pointer – chbaker0 Mar 17 '15 at 01:56
@MasterKoder Let me know if that fixes it and I will update my answer accordingly – chbaker0 Mar 17 '15 at 01:57
1

Sorry, yes that's right. I should be more careful with using const :) – Mar 17 '15 at 01:58
@MasterKoder don't worry, it gets the best of us. Take a glance at the relevant portion of the C++ FAQ: http://isocpp.org/wiki/faq/const-correctness#overview-const – chbaker0 Mar 17 '15 at 01:59
Hmm, apparently it doesn't accept having both versions: `const operator->()` and `operator->()`. Thanks tho, I'll check that link too – Mar 17 '15 at 02:00
1

@MasterKoder http://isocpp.org/wiki/faq/const-correctness#const-member-fns . But to save you some time, you must basically do this: `const [pointer type here] operator->() const`. I'd recommend you look through that FAQ page :) – chbaker0 Mar 17 '15 at 02:02
1

Oh that actually makes sense. The first const is for the type returned and the second const is ensuring the program that the member variables won't be modified from within the function. Thanks! :) – Mar 17 '15 at 02:05
Hmm, the program works almost perfect but there's just one last issue. Do you have any idea why in the Test.cpp file, instead of being able to call `list::iterator it = list.begin();` I have to write this `list_iterator it = list.begin();`? I am told 'Error: The global scope doesn't have iterator'. However, I have declared defined it in the list.h class. – Mar 17 '15 at 02:15
@MasterKoder Just eyeballing it, it looks like you need `typename` for the same reason why you needed it before. If you're using C++11 however I'd recommend you just use the `auto` keyword for your iterators when possible. – chbaker0 Mar 17 '15 at 02:17
@MasterKoder actually I think I'm wrong, let me take another look – chbaker0 Mar 17 '15 at 02:18
I mean, the usage of the `auto` keyword seems to be a good idea. I haven't really used C++11 very much and I was planning on starting to study its capabilities :) – Mar 17 '15 at 02:20
What's weird is that `list_iterator::iterator it = list.begin();` works just fine, but `list::iterator it = list.begin();` doesn't. The thing is that I'm unsure as of where I should place the `typedef` and/or `typename` declaration for `iterator` so that the `list.h` will recognise it. – Mar 17 '15 at 02:28
1

@MasterKoder Your problem is that you are requesting `other->m_pNode` in your function `operator==()` and `operator!=()`, but `other` is a reference type. So, you should just use `other.m_pNode`. For `list_iterator`, `operator->()` returns an `int*` so you're basically attempting to access a member of an `int` (which is obviously impossible) when you do `other->m_pNode`. – chbaker0 Mar 17 '15 at 02:28
Oh I changed that. Sorry. Forgot to say. But thanks. – Mar 17 '15 at 02:29
1

@MasterKoder and when you do `list list` in `main()` your variable `list` is shadowing your class template `list<>`. That's your other problem. Name your variable something else, that's the only fix for that. – chbaker0 Mar 17 '15 at 02:30
Ohh, that's it.. Now that was a naive mistake. Thanks again for taking your time to look over my code and help with all this! I really appreciate it :) – Mar 17 '15 at 02:33

C++ Custom List Iterator Errors

1 Answers1