A function for a generic STL container

[Nafai]

Hi I want to write a function which erases al the repeated elements in a
range. How should be the prototype?

template <class Iterator>
void eraseRepeated(I terator begin, Iterator end);

doesn't work because I need the container to write: container.erase (p),
where p is an iterator.

[Nafai]

Kristo wrote:

Nafai wrote:

Kristo escribió:

> Nafai wrote:
>>
>>Let's see. It's quite simple. I have a collection C (ie. list or
>>vector):
>>C=(1 4 4 2 1 1 4) and I get: C'=(1 4 2)
>>
>>The algorithm is just this:
>>
>>insert all elements of C into a set.
>>
>>iterate through C and check if each element is in the set.
>>If it is, erase it from the set.
>>If it isn't erase it from C.
>>
>>Or even more simpler (and suitable for any collection):
>>
>>...
>>If it is, erase it from the set and insert it into C'.
>>If it isn't do nothing.
>>
>>
>>I just need to know how to declare the prototype!! ("template". ..)
>
>
> Does this suit you?
>
> template <class T>
> void eraseRepeated(T &container);
>
> Kristo
>

No, it doesn't. This doesn't work:

template <class T>
void f(T& Container)
{
T::iterator it; // <- parse error before token ';'
it = Container.begin ();
...
}

That's because you forgot the typename keyword. The compiler has no
other way of knowing that T::iterator is a type.

typename T::iterator it;

Kristo

But I also have to know the type of elements that contains "Container" .

For example, if T=list<T2>, I need to declare a std::set<T2> as a local
variable:

template <class T>
void f(T& Container)
{
std::set<????> s;
typename T::iterator it;
...
}

[Nafai]

Nafai wrote:

Kristo wrote:

Nafai wrote:

Kristo escribió:
> Nafai wrote:
>>
>>Let's see. It's quite simple. I have a collection C (ie. list or
>>vector):
>>C=(1 4 4 2 1 1 4) and I get: C'=(1 4 2)
>>
>>The algorithm is just this:
>>
>>insert all elements of C into a set.
>>
>>iterate through C and check if each element is in the set.
>>If it is, erase it from the set.
>>If it isn't erase it from C.
>>
>>Or even more simpler (and suitable for any collection):
>>
>>...
>>If it is, erase it from the set and insert it into C'.
>>If it isn't do nothing.
>>
>>
>>I just need to know how to declare the prototype!! ("template". ..)
>
>
> Does this suit you?
>
> template <class T>
> void eraseRepeated(T &container);
>
> Kristo
>

No, it doesn't. This doesn't work:

template <class T>
void f(T& Container)
{
T::iterator it; // <- parse error before token ';'
it = Container.begin ();
...
}

That's because you forgot the typename keyword. The compiler has no
other way of knowing that T::iterator is a type.

typename T::iterator it;

Kristo

But I also have to know the type of elements that contains "Container" .

For example, if T=list<T2>, I need to declare a std::set<T2> as a local
variable:

template <class T>
void f(T& Container)
{
std::set<????> s;
typename T::iterator it;
...
}

Here is my final solution. Any suggestion to improve it?

template <class T, class Container>
void eraseRepeated(C ontainer& c)
{
std::set<T> s;
typename Container::iter ator itc;
for(itc=c.begin ();itc!=c.end() ;++itc)
{
s.insert(*itc);
}

typename std::set<T>::it erator its;

itc=c.begin();
while(itc!=c.en d())
{
its=s.find(*itc );
if(its!=s.end() )
{
s.erase(its);
itc++;
}
else
{
itc=c.erase(itc );
}
}
}
Example of use:

int main()
{
std::list<int> l(3,3);
l.push_back(5); l.push_back(3); l.push_back(2); l.push_back(5);

std::vector<cha r> v;
v.push_back('a' );v.push_back(' b');
v.push_back('a' );v.push_back(' a');
v.push_back('c' );v.push_back(' b');

copy(l.begin(), l.end(),ostream _iterator<int>( cout, " "));
cout << endl;

eraseRepeated< int, list<int> >(l); // ANY WAY TO MAKE IT SIMPLER?:
// eraseRepeated< list<int> >(l); for example.

copy(l.begin(), l.end(),ostream _iterator<int>( cout, " "));
cout << endl;

copy(v.begin(), v.end(),ostream _iterator<char> (cout, " "));
cout << endl;
eraseRepeated< char, vector<char> >(v);
copy(v.begin(), v.end(),ostream _iterator<char> (cout, " "));
cout << endl;
}

Output:

3 3 3 5 3 2 5
3 5 2
a b a a c b
a b c

[davidrubin]

Nafai wrote:

Here is my final solution. Any suggestion to improve it?

template <class T, class Container>
void eraseRepeated(C ontainer& c)
{
std::set<T> s;
typename Container::iter ator itc;
for(itc=c.begin ();itc!=c.end() ;++itc)
{
s.insert(*itc);
}

typename std::set<T>::it erator its;

itc=c.begin();
while(itc!=c.en d())
{
its=s.find(*itc );
if(its!=s.end() )
{
s.erase(its);
itc++;
}
else
{
itc=c.erase(itc );
}
}
}

You cannot call 'c.erase' while looping over 'c' with
'Container::ite rator's as this invalidates 'itc' in some cases causing
'itc++' to produce undefined behavior. Furthermore, not all containers
(e.g., Associative Containers) return a valid iterator from 'erase'.

It seems like you want to sort 'c', copy unique elements to a temporary
'Container' object, 'c2', and then 'swap' between 'c' and 'c2'.

You can even better performance if you tmplatize on container type
*and* element type. Then you can specialize for sorted containers by
simply copying repeated elements into a second container of the same
type and finally calling 'swap' to get the result back into the
original container.

In any case, except where radix-sort is appropriate (again, a
specialization) , any solution is going to be O(n log n).

/david

[John Dibling]

You should very carefully consider whether or not you really don't want
to use std::unique(). Here are the unsorted_unique () and related
algorithms from my STL Extensions library, and it does what I believe
you want done. But it is extremely expensive. Choose your tools
wisely.

/* ---

25.2.8
template< class ForwardIterator , class OutputIterator, class
BinaryPredicate >
OutputIterator unsorted_unique _copy(ForwardIt erator first,
InputIterator last, OutputIterator result, BinaryPredicate pred)

template< class ForwardIterator , class OutputIterator>
OutputIterator unsorted_unique _copy(ForwardIt erator first,
InputIterator last, OutputIterator result)

template< class ForwardIterator , class OutputIterator, class
BinaryPredicate >
ForwardIterator unsorted_unique (ForwardIterato r first,
ForwardIterator last, OutputIterator result, BinaryPredicate pred)

template< class ForwardIterator , class OutputIterator>
ForwardIterator unsorted_unique (ForwardIterato r first,
ForwardIterator last, OutputIterator result)

Requires :

The ranges [first, last) and [result, result+last-first) shall not
overlap

Effects :

Eliminates all but the first occurance of any element referred to by
the iterator i in the range [first, last).
The range [first, last) does not need to be sorted before executing
unsorted_unique _copy.

Complexity :

If the range [first, last) is not empty, (n^2 + n) / 2 applications
of the comparison predicate or operator.
Otherwise, no applications of the predicate.

Returns :

The end of the resulting range.

--- */

template< class ForwardIterator , class OutputIterator, class
BinaryPredicate >
OutputIterator unsorted_unique _copy(ForwardIt erator first,
ForwardIterator last, OutputIterator result, BinaryPredicate pred)
{
for( ForwardIterator current = first; current != last; ++current )
{
// make sure this item isnt repeated previously in the source range
if( current == find_if(first, current, bind1st(pred,*c urrent)) )
// wasn't found, add to destination range
*result++ = *current;
}
return result;
}

template< class ForwardIterator , class OutputIterator>
OutputIterator unsorted_unique _copy(ForwardIt erator first,
ForwardIterator last, OutputIterator result)
{
for( ForwardIterator current = first; current != last; ++current )
{
// make sure this item isnt repeated previously in the source range
if( current == find(first, current, *current) )
// wasn't found, add to destination range
*result++ = *current;
}
return result;
}

template< class BidirectionalIt erator> inline
BidirectionalIt erator unsorted_unique (BidirectionalI terator first,
BidirectionalIt erator last)
{
for( ; first != last; ++first )
{
BidirectionalIt erator current = first;
for( ++current; current != last; )
{
if( *first == *current )
{
BidirectionalIt erator rotend(current) ;
++rotend;
rotate(current, rotend,last--);
}
else
++current;
}
}
return last;
}

template< class BidirectionalIt erator, class BinaryPredicate >
BidirectionalIt erator unsorted_unique (BidirectionalI terator first,
BidirectionalIt erator last, BinaryPredicate pred)
{
for( ; first != last; ++first )
{
BidirectionalIt erator current(first);
for( current++; current != last; )
{
if( pred(*first, *current) )
{
BidirectionalIt erator rotend(current) ;
rotend++;
rotate(current, rotend,last--);
}
else
++current;
}
}
return last;
}

</dib>

[red floyd]

Nafai wrote:

But I also have to know the type of elements that contains "Container" .

For example, if T=list<T2>, I need to declare a std::set<T2> as a local
variable:

template <class T>
void f(T& Container)
{
std::set<????> s;
typename T::iterator it;
...
}

How about this:

template <typename Container>
void eraseRepeated(C ontainer& c)
{
typedef typename Container::valu e_type T;

std::set<T> s;
typename Container::iter ator iter;

// ...
}

[Kristo]

Nafai wrote:

Let's see. It's quite simple. I have a collection C (ie. list or
vector):
C=(1 4 4 2 1 1 4) and I get: C'=(1 4 2)

The algorithm is just this:

insert all elements of C into a set.

One thing I forgot to mention: this step is O(n log n), so you're not
gaining anything over sorting and then calling std::unique.

[snip the rest of the algorithm]

Kristo

[Nafai]

da********@warp mail.net escribió:

Nafai wrote:

Here is my final solution. Any suggestion to improve it?

template <class T, class Container>
void eraseRepeated(C ontainer& c)
{
std::set<T> s;
typename Container::iter ator itc;
for(itc=c.begin ();itc!=c.end() ;++itc)
{
s.insert(*itc);
}

typename std::set<T>::it erator its;

itc=c.begin();
while(itc!=c.en d())
{
its=s.find(*itc );
if(its!=s.end() )
{
s.erase(its);
itc++;
}
else
{
itc=c.erase(itc );
}
}
}

You cannot call 'c.erase' while looping over 'c' with
'Container::ite rator's as this invalidates 'itc' in some cases causing
'itc++' to produce undefined behavior. Furthermore, not all containers
(e.g., Associative Containers) return a valid iterator from 'erase'.

For lists and vectors it works. And after calling c.erase(itc) I dont
write itc++, I do that after s.erase(its).
It seems like you want to sort 'c', copy unique elements to a temporary
'Container' object, 'c2', and then 'swap' between 'c' and 'c2'.
I don't want to sort c. That's because I don't sort and use unique.

For example:
I want: 3 1 3 2 3 2 --> 3 1 2
but not: 3 3 2 3 2 --> 1 2 2 3 3 3 --> 1 2 3
You can even better performance if you tmplatize on container type
*and* element type.
How do I do that?:

template < class T, class Container<T> >
void f(Container<T>& c);
....
f<int>(L);

or...

template < class T, class Container >
void f(Container& c);
....
f< int, list<int> >(L);

?
In any case, except where radix-sort is appropriate (again, a
specialization) , any solution is going to be O(n log n).

/david

[Nafai]

Kristo escribió:

Nafai wrote:

Let's see. It's quite simple. I have a collection C (ie. list or
vector):
C=(1 4 4 2 1 1 4) and I get: C'=(1 4 2)

The algorithm is just this:

insert all elements of C into a set.

One thing I forgot to mention: this step is O(n log n), so you're not
gaining anything over sorting and then calling std::unique.

[snip the rest of the algorithm]

Kristo

But I don't want the elements to get sorted!

For example:
I want: 3 1 3 2 3 2 --> 3 1 2
but not: 3 3 2 3 2 --> 1 2 2 3 3 3 --> 1 2 3

[davidrubin]

Nafai wrote:

da********@warp mail.net escribió:

Nafai wrote:

Here is my final solution. Any suggestion to improve it?

[snip] You cannot call 'c.erase' while looping over 'c' with
'Container::ite rator's as this invalidates 'itc' in some cases causing 'itc++' to produce undefined behavior. Furthermore, not all containers (e.g., Associative Containers) return a valid iterator from 'erase'.

For lists and vectors it works. And after calling c.erase(itc) I dont write itc++, I do that after s.erase(its).
This is not useful to OP who asked about a solution given a generic
container.

The point about iterators and erase is that you can't always execute
'itc++' after executing 'c.erase(itc)', notwithstanding the fact that
not all container types return an iterator from 'erase'.
It seems like you want to sort 'c', copy unique elements to a temporary 'Container' object, 'c2', and then 'swap' between 'c' and 'c2'.

I don't want to sort c. That's because I don't sort and use unique.

Your example does not use 'unique'...
For example:
I want: 3 1 3 2 3 2 --> 3 1 2
but not: 3 3 2 3 2 --> 1 2 2 3 3 3 --> 1 2 3

....and 'unique' does not work this way. It requires an ordered
collection to be effective for the pupose stated by OP.

You can even better performance if you tmplatize on container type
*and* element type.

How do I do that?:

With either two template parameters or a template-template parameter.

/david

[Kristo]

Nafai wrote:

Kristo escribió:

Nafai wrote:

Let's see. It's quite simple. I have a collection C (ie. list or
vector):
C=(1 4 4 2 1 1 4) and I get: C'=(1 4 2)

The algorithm is just this:

insert all elements of C into a set.

One thing I forgot to mention: this step is O(n log n), so you're not gaining anything over sorting and then calling std::unique.

[snip the rest of the algorithm]

Kristo

But I don't want the elements to get sorted!

For example:
I want: 3 1 3 2 3 2 --> 3 1 2
but not: 3 3 2 3 2 --> 1 2 2 3 3 3 --> 1 2 3

Whoops, that's right, you said that. I came up with an O(n^2)
algorithm that might work for you. It uses the prototype you initially
rejected. I'm sure you could modify it to suit your needs.

/* begin foo.cpp */
#include <algorithm>
#include <iostream>
#include <iterator>
#include <ostream>
#include <vector>

template <class Iterator>
Iterator eraseRepeated(I terator begin, Iterator end)
{
for (Iterator i = begin; i != end;)
{
Iterator prev = i++;
end = std::remove(i, end, *prev);
}

return end;
}

int main()
{
int a[] = {3, 1, 3, 2, 3, 2};

int *e = eraseRepeated(a , a+5);
std::copy(a, e, std::ostream_it erator<int>(std ::cout, " "));
std::cout << std::endl;

return 0;
}
/* end foo.cpp */

The output from this program is:
3 1 2

Hope this helps.

Kristo