Beginner C++: Transforming index-syntax into iterator-syntax

Question

I'm trying to learn C++ with a little Java background, and I am trying to write code that returns the intersection of two lists. I believe I have the right idea conceptually, but am having trouble with the syntax as nothing is compiling.

Here's the code I have come up with:

#include <iostream>
using namespace std;
#include <list>

template <typename Object>
list<Object> intersection( const list<Object> & L1, const list<Object> & L2){

  std::list<Object> result;                 
  int pos1 = 0;
  int pos2 = 0;

  while (pos1 < L1.size() && pos2 < L2.size()) {
    if (L1[pos1] > L1[pos2]) {
      pos1++;
    } else if (L2[pos2] > L1[pos1]) {
      pos2++;
    } else {
      result.push_back(L2[pos2]);
      pos1++;
      pos2++;
    }
  }
  return result;

}

Things I think that I need: an iterator (I'm sure the way I'm accessing the list is not correct)

Answer 1

Change pos1 and pos2 to iterators:

list<Object> intersection( const list<Object> & L1, const list<Object> & L2){
  std::list<Object> result;                 
  std::list<Object>::iterator pos1 = L1.begin(), pos2 = L2.begin();
  while (pos1 != L1.end() && pos2 != L2.end()) {
     if (*pos1 > *pos2) { //works only if pos1 != L1.end() and pos2 != L2.end()
       pos1++;
       ...

pos1 = L1.begin() points pos1 to first element of L1.

++pos1 moves iterator forward, to next element

*pos1 gets element from pos1

pos1 != L1.end() checks if pos1 reached end of the list. You can't take element from pos1 when pos1 == L1.end().

Answer 2

You need a const_iterator not an iterator.

All the c++ container classes have typedefs on them defining things like the type they contain, and the iterator types, amongst other things.

In your case list<Object>::value_type is of type Object. So you can say:

list<Object>::value_type object = Object();

Similarly list<Object>::iterator is the type of the iterator used for traversing the container. You can get the iterators representing the beginning and end of the container by using begin() and end().

If your container is const as in your question, begin and end don't return iterator they return const_iterator. You can't assign this to the iterator type. They are different as one allows you to modify the value, the other doesn't.

You can fix your problem by using the const_iterator. However, there are a number of other ways of fixing this.

• auto means you don't have to be explicit about the type. It does the right thing for you.
• Templates can use generic parameters so, again, you don't have to be explicit.
• The standard library has various algorithms which might already do what you want (e.g. set_intersection).