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(Iterator begin, Iterator end);

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

 

[Alf P. Steinbach]

* 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(Iterator begin, Iterator end);

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

Check out std::unique.

 

[Nafai]

Alf P. Steinbach escribió:

* Nafai:



Check out std::unique.

Unique only erases consecutive elements. I want to erase all of them.
And I don't want to sort them.

But above all I would like to know how to program a function like that,
which can get any container and do something with its iterators.

 

[Alf P. Steinbach]

* Nafai:

Alf P. Steinbach escribió:

Unique only erases consecutive elements. I want to erase all of them.
And I don't want to sort them.

I don't think you understand the requirements.

Some way of identifying an element as duplicate is needed.

If not consecutive, and no sorting, you'll need to register elements in
a hash table or something like that.

But above all I would like to know how to program a function like that,
which can get any container and do something with its iterators.

See std::unique.

 

[davidrubin]

Alf P. Steinbach escribió:

Unique only erases consecutive elements. I want to erase all of them.

And I don't want to sort them.

But above all I would like to know how to program a function like that,
which can get any container and do something with its iterators.

No such function exists because different containers have different
"erase" semantics. For example, an algorithm that erases sequential
iterators may work for one container, but may yield undefined behavior
for another. The best you can do is to copy the range, remove the
range, and then add back unique (or non-repeated) elements from the
copied data, but this is very inefficient. /david

 

[Nafai]

* Nafai:

I don't think you understand the requirements.

Some way of identifying an element as duplicate is needed.

If not consecutive, and no sorting, you'll need to register elements in
a hash table or something like that.



See std::unique.

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"...)

 

[Nafai]

Some way of identifying an element as duplicate is needed.

A and B are duplicate if and only if A==B.

 

[Kristo]

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

 

[Nafai]

Kristo escribió:

elements in


elements in



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();
....
}

 

[Kristo]

Kristo escribió:

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

 

[Nafai]

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]

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(Container& c)
{
std::set<T> s;
typename Container::iterator itc;
for(itc=c.begin();itc!=c.end();++itc)
{
s.insert(*itc);
}

typename std::set<T>::iterator its;

itc=c.begin();
while(itc!=c.end())
{
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<char> 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]

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

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

typename std::set<T>::iterator its;

itc=c.begin();
while(itc!=c.end())
{
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::iterator'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(ForwardIterator first,
InputIterator last, OutputIterator result, BinaryPredicate pred)

template< class ForwardIterator, class OutputIterator>
OutputIterator unsorted_unique_copy(ForwardIterator first,
InputIterator last, OutputIterator result)

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

template< class ForwardIterator, class OutputIterator>
ForwardIterator unsorted_unique(ForwardIterator 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(ForwardIterator 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,*current)) )
// wasn't found, add to destination range
*result++ = *current;
}
return result;
}

template< class ForwardIterator, class OutputIterator>
OutputIterator unsorted_unique_copy(ForwardIterator 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 BidirectionalIterator> inline
BidirectionalIterator unsorted_unique(BidirectionalIterator first,
BidirectionalIterator last)
{
for( ; first != last; ++first )
{
BidirectionalIterator current = first;
for( ++current; current != last; )
{
if( *first == *current )
{
BidirectionalIterator rotend(current);
++rotend;
rotate(current,rotend,last--);
}
else
++current;
}
}
return last;
}

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

</dib>

 

[red floyd]

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(Container& c)
{
typedef typename Container::value_type T;

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

// ...


}

 

[Kristo]

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]

(e-mail address removed) escribió:

Nafai wrote:




You cannot call 'c.erase' while looping over 'c' with
'Container::iterator'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);

?

 

[Nafai]

Kristo escribió:

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]

(e-mail address removed) escribió:

Nafai wrote:

[snip]

You cannot call 'c.erase' while looping over 'c' with
'Container::iterator'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'.

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.

How do I do that?:

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

/david

 

[Kristo]

Kristo escribió:

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(Iterator 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:stream_iterator<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