Template Specialization

[Senthilvel]

Hi folks,
I was trying to learn the standard library algorithms where i got stuck with
the templates.

I wrote one function to eliminate the duplicates(from The C++ Programming
Language 3rd Edition)

template<class Con> void RemoveDuplicates(Con& seq)
{
sort(seq.begin(),seq.end());
typename Con::iterator p = unique(seq.begin(),seq.end());
seq.erase(p,seq.end());
}

int main()
{
vector<int> ls1;
ls1.push_back(1);
ls1.push_back(2);
ls1.push_back(3);
ls1.push_back(4);
ls1.push_back(1);
ls1.push_back(2);
ls1.push_back(3);
ls1.push_back(4);

print_all(ls1,cout);

RemoveDuplicates(ls1);

print_all(ls1,cout);

return 0;

}

This worked fine for vector,deque but failed for list as sort needs randon
access iterators which is not provided by list

So i thought of specializing the function for list, but how do i do it ???
List needs a template argument and i do not know how to pass that
template argument.I did this way

template<class T> void RemoveDuplicates(list<T> & seq)
{
seq.sort();
typename list<T>::iterator p = unique(seq.begin(),seq.end());
seq.erase(p,seq.end());
}

int main()
{
list<int> ls1;
ls1.push_back(1);
ls1.push_back(2);
ls1.push_back(3);
ls1.push_back(4);
ls1.push_back(1);
ls1.push_back(2);
ls1.push_back(3);
ls1.push_back(4);

print_all(ls1,cout);

RemoveDuplicates<int>(ls1);

print_all(ls1,cout);




return 0;

}

Now i explicity need to specify the type in the RemoveDuplicates function.
Am i correct or am i missing something ???


Thanks and Best Regards,
Senthilvel.

 

[Sumit Rajan]

Hi folks,
I was trying to learn the standard library algorithms where i got stuck with
the templates.

I wrote one function to eliminate the duplicates(from The C++ Programming
Language 3rd Edition)

template<class Con> void RemoveDuplicates(Con& seq)
{
sort(seq.begin(),seq.end());
typename Con::iterator p = unique(seq.begin(),seq.end());
seq.erase(p,seq.end());
}

int main()
{
vector<int> ls1;
ls1.push_back(1);
ls1.push_back(2);
ls1.push_back(3);
ls1.push_back(4);
ls1.push_back(1);
ls1.push_back(2);
ls1.push_back(3);
ls1.push_back(4);

print_all(ls1,cout);

RemoveDuplicates(ls1);

print_all(ls1,cout);

return 0;

}

This worked fine for vector,deque but failed for list as sort needs randon
access iterators which is not provided by list

So i thought of specializing the function for list, but how do i do it ???
List needs a template argument and i do not know how to pass that
template argument.I did this way

template<class T> void RemoveDuplicates(list<T> & seq)
{
seq.sort();
typename list<T>::iterator p = unique(seq.begin(),seq.end());
seq.erase(p,seq.end());
}

int main()
{
list<int> ls1;
ls1.push_back(1);
ls1.push_back(2);
ls1.push_back(3);
ls1.push_back(4);
ls1.push_back(1);
ls1.push_back(2);
ls1.push_back(3);
ls1.push_back(4);

print_all(ls1,cout);

RemoveDuplicates<int>(ls1);

print_all(ls1,cout);




return 0;

}

Now i explicity need to specify the type in the RemoveDuplicates function.
Am i correct or am i missing something ???


Thanks and Best Regards,
Senthilvel.

You could try something like this:


#include <iostream>
#include <vector>
#include <algorithm>
#include <list>

template<class Con> void RemoveDuplicates(Con& seq)
{
std::sort(seq.begin(),seq.end());
typename Con::iterator p = std::unique(seq.begin(),seq.end());
seq.erase(p,seq.end());
}

template<class T> void RemoveDuplicates (std::list<T>& lst)
{
lst.sort();
typename std::list<T>::iterator p = std::unique(lst.begin(),lst.end());
lst.erase(p,lst.end());

}


int main()
{
std::list<int> ls1;
ls1.push_back(1);
ls1.push_back(2);
ls1.push_back(3);
ls1.push_back(4);
ls1.push_back(1);
ls1.push_back(2);
ls1.push_back(3);
ls1.push_back(4);

std::copy(ls1.begin(),ls1.end(),
std:stream_iterator<int>(std::cout, " "));
std::cout << '\n';

RemoveDuplicates(ls1);

std::copy(ls1.begin(),ls1.end(),
std:stream_iterator<int>(std::cout, " "));
std::cout << '\n';

}


Regards,
Sumit.

 

[Senthilvel]

------> By Senthil
------> By Sumit

template<class Con> void RemoveDuplicates(Con& seq)
{
std::sort(seq.begin(),seq.end());
typename Con::iterator p = std::unique(seq.begin(),seq.end());
seq.erase(p,seq.end());
}

template<class T> void RemoveDuplicates (std::list<T>& lst)
{
lst.sort();
typename std::list<T>::iterator p = std::unique(lst.begin(),lst.end());
lst.erase(p,lst.end());

}

Thats exacty what i have done Sumit...
I get the error
"error C2667: 'RemoveDuplicates' : none of 2 overload have a best
conversion"
"error C2668: 'RemoveDuplicates' : ambiguous call to overloaded function"
on the line
RemoveDuplicates(ls1);
in main

BTW..I am using MS -VC++ 6 compiler ..

 

[Sumit Rajan]

BTW..I am using MS -VC++ 6 compiler ..

Well, it compiles using VC++ 7.1 and Comeau C++ 4.3.3. I guess it
VC++ 6.0 does not extend full support to overloading templates (but I'm not
sure as I have never used 6.0).

Regards,
Sumit.

 

[Alf P. Steinbach]

* Senthilvel:

template<class Con> void RemoveDuplicates(Con& seq)
{
sort(seq.begin(),seq.end());
typename Con::iterator p = unique(seq.begin(),seq.end());
seq.erase(p,seq.end());
}

int main()
{
vector<int> ls1;
ls1.push_back(1);
ls1.push_back(2);
ls1.push_back(3);
ls1.push_back(4);
ls1.push_back(1);
ls1.push_back(2);
ls1.push_back(3);
ls1.push_back(4);

print_all(ls1,cout);

RemoveDuplicates(ls1);

print_all(ls1,cout);

return 0;

}

This worked fine for vector,deque but failed for list as sort needs randon
access iterators which is not provided by list

So i thought of specializing the function for list, but how do i do it ???
List needs a template argument and i do not know how to pass that
template argument.I did this way

template<class T> void RemoveDuplicates(list<T> & seq)
{
seq.sort();
typename list<T>::iterator p = unique(seq.begin(),seq.end());
seq.erase(p,seq.end());
}

int main()
{
list<int> ls1;
ls1.push_back(1);
ls1.push_back(2);
ls1.push_back(3);
ls1.push_back(4);
ls1.push_back(1);
ls1.push_back(2);
ls1.push_back(3);
ls1.push_back(4);

print_all(ls1,cout);

RemoveDuplicates<int>(ls1);

print_all(ls1,cout);
return 0;

}

Now i explicity need to specify the type in the RemoveDuplicates function.
Am i correct or am i missing something ???

No, you don't need to specify the type, it's inferred.

But your implementation is tied specifically to std::list.

It's generally better to separate the template requirements, e.g. like


#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

template< class T >
struct HasRandomIterators_{ enum{ yes = true }; };

template< typename T >
struct HasRandomIterators_< std::list<T> >{ enum{ yes = false }; };

template< class Container, bool genericIsOK = true>
struct RemoveDuplicates_
{
static void from( Container& c )
{
std::sort( c.begin(), c.end() );
typename Container::iterator it = std::unique( c.begin(),
c.end() );
c.erase( it, c.end() );
}
};

template< class Container>
struct RemoveDuplicates_<Container, false>
{
static void from( Container& c )
{
c.sort();
c.unique();
}
};

template< class Container >
void removeDuplicates( Container& c )
{
RemoveDuplicates_<Container,
HasRandomIterators_<Container>::yes>::from( c );
}

template< class Container >
void printAll( Container const& c )
{
typedef Container::const_iterator Iterator;
for( Iterator it = c.begin(); it != c.end(); ++it )
{
std::cout << *it << std::endl;
}
}

int main()
{
std::list<int> c;

c.push_back( 1 );
c.push_back( 2 );
c.push_back( 3 );
c.push_back( 4 );
c.push_back( 1 );
c.push_back( 2 );
c.push_back( 3 );
c.push_back( 4 );

printAll( c );
std::cout << std::endl;

removeDuplicates( c );
printAll( c );
}

 

[Senthilvel]

No, you don't need to specify the type, it's inferred.

But your implementation is tied specifically to std::list.

It's generally better to separate the template requirements, e.g. like


#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

template< class T >
struct HasRandomIterators_{ enum{ yes = true }; };

template< typename T >
struct HasRandomIterators_< std::list<T> >{ enum{ yes = false }; };

template< class Container, bool genericIsOK = true>
struct RemoveDuplicates_
{
static void from( Container& c )
{
std::sort( c.begin(), c.end() );
typename Container::iterator it = std::unique( c.begin(),
c.end() );
c.erase( it, c.end() );
}
};

template< class Container>
struct RemoveDuplicates_<Container, false>
{
static void from( Container& c )
{
c.sort();
c.unique();
}
};

template< class Container >
void removeDuplicates( Container& c )
{
RemoveDuplicates_<Container,
HasRandomIterators_<Container>::yes>::from( c );
}

template< class Container >
void printAll( Container const& c )
{
typedef Container::const_iterator Iterator;
for( Iterator it = c.begin(); it != c.end(); ++it )
{
std::cout << *it << std::endl;
}
}

Thanks Alf...Thats a nice technique...
But my only problem it does not compile on VC++ 6.0 : - (

error C2988: unrecognizable template declaration/definition
error C2989: 'RemoveDuplicates_<Container,0>' : template class has already
been defined as a non-template class
error C2988: unrecognizable template declaration/definition

Got to keep this in mind until we move to VC 7.0..(Hoping this code compiles
will compile in that version )

 

[John Harrison]

Thanks Alf...Thats a nice technique...

But my only problem it does not compile on VC++ 6.0 : - (

error C2989: 'HasRandomIterators_<class std::list<T,class
error C2988: unrecognizable template declaration/definition
error C2989: 'RemoveDuplicates_<Container,0>' : template class has already
been defined as a non-template class
error C2988: unrecognizable template declaration/definition

Got to keep this in mind until we move to VC 7.0..(Hoping this code compiles
will compile in that version )

Alf was using partial template specialisation, which is not supported in
VC++ 6. I would leave off learning templates until you upgrade to VC++ 7.1
(not 7.0), VC++ 6 template support is poor and you'll only end up learning
stuff which isn't true.

John

 

[red floyd]

[redacted]

Your problem is MSVC6. VC6 is widely known (and acknowledged by MS) to
have problems with template specializations.