Template function vector iterator won't compile

[Clockowl]

Hey guys,

I got this code, and I can't get it to compile, no clue what I'm doing wrong.

#include <iostream>
#include <vector>
#include <iterator>
using namespace std;

template <class T>
void kill_dupes(vector<T> &x){
    vector<T> y;

    for(vector<T>::iterator it = x.begin(); it != x.end(); it++){
        if(find(x.begin(), x.end(), *it) == x.end()){
            y.push_back(*it);
        }
    }

    x = y;

    return;
}

int main(){
    return 0;
}

GCC MinGW says:

main.cpp||In function `void kill_dupes(std::vector<T, std::allocator<_CharT> >&)':|
main.cpp|12|error: expected `;' before "it"|
main.cpp|12|error: `it' was not declared in this scope|
main.cpp||In function `void kill_dupes(std::vector<T, std::allocator<_CharT> >&) [with T = int]':|
main.cpp|31|instantiated from here|
main.cpp|12|error: dependent-name ` std::vector<T,std::allocator<_CharT> >::iterator' is parsed as a non-type, but instantiation yields a type|
main.cpp|12|note: say `typename  std::vector<T,std::allocator<_CharT> >::iterator' if a type is meant|
||=== Build finished: 3 errors, 0 warnings ===|

Of course it wasn't declared, I'm trying to declare it (no pun intended).

kill_dupes is called with a vector<int>.

Thanks in advance,

Edit:

This works as expected:

void kill_dupes(vector<int> &x){
    vector<int> y;

    for(vector<int>::iterator it = x.begin(); it != x.end(); it++){
        if(find(x.begin(), x.end(), *it) == x.end()){
            y.push_back(*it);
        }
    }

    x = y;

    return;
}

What's the difference? *-)

[Sky Diploma]

Firstly i dont prefer using your own version of duplicate assasin ;)

I prefer unique_copy function in the standard library.

unique_copy(x.begin(),x.end(),y.begin());

Would do the trick.

[Clockowl]

That will not do the trick: Unique only removes when consecutive duplicates are found:

Copies the values of the elements in the range [first,last) to the range positions beginning at result, except for the duplicate consecutive elements, which are not copied

[Clockowl]

Durr, code should be:

void kill_dupes(vector<int> &x){
    vector<int> y;

    for(vector<int>::iterator it = x.begin(); it != x.end(); it++){
        if(find(y.begin(), y.end(), *it) == y.end()){
            y.push_back(*it);
            cout << *it << " ";
        }
    }

    x = y;

    return;
}

Of course. But I want a template like that, as stated above.

[nucleon]

You need to use typename. for (typename vector<T>::iterator it = x.begin(); it != x.end(); it++) {

[Clockowl]

main.cpp|12|note: say `typename  std::vector<T,std::allocator<_CharT> >::iterator' if a type is meant|

So that's what it meant. Thanks. :)

Working code:

template <typename T>
void kill_dupes(vector<T> &x){
    vector<T> y;

    for(typename vector<T>::iterator it = x.begin(); it != x.end(); it++){
        if(find(y.begin(), y.end(), *it) == y.end()){
            y.push_back(*it);
        }
    }

    x = y;

    return;
}

Could someone explain why typename is needed though? I still don't quite get it...

[nucleon]

I don't know exactly why it's needed either. The compiler seems to be saying that's it's syntactically unclear (at that point in the compilation anyway) whether or not vector<T>::iterator is a typename, so you need to provide the clue. But that leads to the question, what else could it be?

[Narue]

>I don't know exactly why it's needed either.
There's the potential for a parsing ambiguity when you use dependent names[1]. Let's look at an example:

template <typename T>
void meep()
{
    T::Baz *p;
}

Clearly this code is intended to create a pointer to T::Baz and T::Baz is a type, right? Not quite. What happens when T is instantiated into the class Bar below?

class Bar {
public:
    static int Baz;
};

Now T::Baz *p takes on a whole new meaning. Since Baz is actually an object after template instantiation, the expression now says to evaluate the product of Baz and p, then throw it away. Since p doesn't yet exist, that's a syntax error in this case, but it shouldn't be hard to see more subtle errors that will compile and simply not do what's expected.

The dependent name rules and the typename keyword help alleviate this problem. The dependent name rules state that without the typename keyword, dependent names are assumed to be non-types (hence, your error). If you really want a type, you need to apply the typename keyword, which will remove the ambiguity and the Bar case above will fail to compile instead of silently do something unintended.

[1] A dependent name is a name that relies on a template parameter such that the name doesn't really exist until the template is instantiated.

[StuXYZ]

First of all, Narue's explaination is really well done (as usual).

Second, has ClockOwl noticed that REGARDLESS of the template issue
he has written the algorithm wrong and you get absolutely no items in x after kill_dupes is called you might as well write

template<typename T>
void kill_dupes(vector<T>& X)
{ 
    X.clear();
    return;
}

What you actual need I think --
is to change the test in the loop to

typename vector<T>::const_iterator it;
for(it = x.begin(); it != x.end(); it++)
   {
      if(find(y.begin(), y.end(), *it) == y.end())
	  y.push_back(*it);
   }

N.B. The iterator is out of the loop, too keep it looking nice on a web page.

[nucleon]

StuXYZ> Narue's explanation is really well done

No doubt! That was a good one. :)

So even in a situation like this (where T is a template param) for (vector<T>::iterator it = v.begin(); ...) where it seems that it MUST be a type, it's interpreted as a non-type, enforcing a simple, consistent rule. And so it gives an error essentially along the lines of "Hey, idiot, you just put two variable names in a row." So you MUST put typename before all such uses.

Narue> It shouldn't be hard to see more subtle errors that will compile

Making p a shadow of an int p sneaks the error past the compiler in your example.

class Bar {
public:
    static int Baz;
};

int p;

template <typename T>
void meep()
{
//    typename  // Compiles with logic error if commented out
        T::Baz *p;
}

int main() {
    meep<Bar>();
}

[Clockowl]

Second, has ClockOwl noticed that REGARDLESS of the template issue
he has written the algorithm wrong and you get absolutely no items in x after kill_dupes is called you might as well write

Yup, see my second post and the post with the "working code".

[siddhant3s]

Making p a shadow of an int p sneaks the error past the compiler in your example.

//    typename  // Compiles with logic error if commented out`

end quote.

If you uncomment the typename, you are intentionally telling compiler that T::Baz is a type which is, off course logically wrong.

This was exactly Narue point.
That if suppose there was a global variable p somewhere defined. And you wrote the code without typename. Then, the compiler will compile the code, but your program will not as you wanted. So, as the saying goes, sooner you detect error, the better.

There is a section about this in Scot Mayers Effective C++ Item 42.

[nucleon]

>If you uncomment the typename, you are intentionally telling compiler
> that T::Baz is a type which is, off course logically wrong.

Telling the compiler that T::Baz is a type (as far as meep is concerned) is not the error. In the given example, that is actually what we want. The logic error here (when typename is in play) is that Bar misdefines Baz as an object and not a type.

> This was exactly Narue point;

I know. I was just posting a runnable (or not) example of what she said.

[siddhant3s]

Telling the compiler that T::Baz is a type (as far as meep is concerned) is not the error. In the given example, that is actually what we want. The logic error here (when typename is in play) is that Bar misdefines Baz as an object and not a type.

If writing the above, you are saying that the error is not while uncommenting the typename but actually when you instantiate the template with Bar, you are right.
The error is sure in Bar. But the logical error here is off course that we are telling the compiler that T::Baz is the type while it is not.

>>I know. I was just posting a runnable (or not) example of what she said.
I appreciate your efforts from my heart and soul.