best way to remove duplicates from forwardIterator [startIter, endIter]

newer
C_time.hpp fails to get a vaild...

Sandeep Gupta

24 Feb 2009 24 Feb '09

4:46 p.m.

Hi, Given a collection in terms of [startIter, endIter] how can obtain [uniqBeginIter, uniqEndIter] that represents unique elements of the original container. I can always explicitly instantiate a set S of [startIter, endIter] and use [S.begin(), S.end()]. Is it possible to express this in terms of algorithms. Please note that I won't be able to use std::sort as startIter does not conform to RandomAccessIterator. Its a forward iterator. Thanks Sandeep

Show replies by date

David Abrahams

24 Feb 24 Feb

5:22 p.m.

New subject: [boost] best way to remove duplicates from forwardIterator [startIter, endIter]

on Tue Feb 24 2009, Sandeep Gupta wrote:

...

Hi, Given a collection in terms of [startIter, endIter] how can obtain [uniqBeginIter, uniqEndIter] that represents unique elements of the original container. I can always explicitly instantiate a set S of [startIter, endIter] and use [S.begin(), S.end()]. Is it possible to express this in terms of algorithms.

Please note that I won't be able to use std::sort as startIter does not conform to RandomAccessIterator. Its a forward iterator.

If they are not already arranged so that all the equal elements are adjacent to one another, your best bet is set<> (or unordered_set<>). FWIW, It is possible to write a conforming std::sort that works on forward iterators, but for some reason the standard only requires sort to work on random access iterators. -- Dave Abrahams BoostPro Computing http://www.boostpro.com

Sandeep Gupta

5:39 p.m.

New subject: [boost] best way to remove duplicates from forwardIterator [startIter, endIter]

Hi Dave, So i will stick with set solution. Its very kind of you reply promptly. Appreciate it and thanks so much. - sandeep On Tue, Feb 24, 2009 at 9:22 AM, David Abrahams wrote:

...

on Tue Feb 24 2009, Sandeep Gupta wrote:

...
Hi, Given a collection in terms of [startIter, endIter] how can obtain [uniqBeginIter, uniqEndIter] that represents unique elements of the original container. I can always explicitly instantiate a set S of [startIter, endIter] and use [S.begin(), S.end()]. Is it possible to express this in terms of algorithms.

Please note that I won't be able to use std::sort as startIter does not conform to RandomAccessIterator. Its a forward iterator.

If they are not already arranged so that all the equal elements are adjacent to one another, your best bet is set<> (or unordered_set<>).

FWIW, It is possible to write a conforming std::sort that works on forward iterators, but for some reason the standard only requires sort to work on random access iterators.

-- Dave Abrahams BoostPro Computing http://www.boostpro.com _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Ovanes Markarian

26 Feb 26 Feb

1:05 p.m.

New subject: best way to remove duplicates from forwardIterator [startIter, endIter]

On Tue, Feb 24, 2009 at 5:46 PM, Sandeep Gupta wrote:

...

Hi, Given a collection in terms of [startIter, endIter] how can obtain [uniqBeginIter, uniqEndIter] that represents unique elements of the original container. I can always explicitly instantiate a set S of [startIter, endIter] and use [S.begin(), S.end()]. Is it possible to express this in terms of algorithms.

Hi! I thought a bit about this issue. If you would like to use an algorithm to just make your code more descriptive, you still can achieve it by using typedef. typedef std::set make_unique_elements; make_unique_elements uniques_(startIter, endIter); Hope that helps, Ovanes

Sandeep Gupta

4:15 p.m.

New subject: best way to remove duplicates from forwardIterator [startIter, endIter]

On Thu, Feb 26, 2009 at 5:05 AM, Ovanes Markarian wrote:

...

On Tue, Feb 24, 2009 at 5:46 PM, Sandeep Gupta wrote:

...
Hi, Given a collection in terms of [startIter, endIter] how can obtain [uniqBeginIter, uniqEndIter] that represents unique elements of the original container. I can always explicitly instantiate a set S of [startIter, endIter] and use [S.begin(), S.end()]. Is it possible to express this in terms of algorithms.

Hi!

I thought a bit about this issue. If you would like to use an algorithm to just make your code more descriptive, you still can achieve it by using typedef.

typedef std::set make_unique_elements;

make_unique_elements uniques_(startIter, endIter);

Hope that helps,

Ovanes

Thanks Ovanes, This would be better that what i have currently. However the bigger problem was to avoid explicitly creating storage. As Dave mentioned if sort was supported over forward iterators (and not bidirectional iterators) then duplicate removal could have been expressed more directly. -sandeep

...

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Ovanes Markarian

4:48 p.m.

New subject: best way to remove duplicates from forwardIterator [startIter, endIter]

...

Thanks Ovanes, This would be better that what i have currently. However the bigger problem was to avoid explicitly creating storage. As Dave mentioned if sort was supported over forward iterators (and not bidirectional iterators) then duplicate removal could have been expressed more directly. -sandeep

Sandeep, that with storage depends on how you are going to solve your problem. You might use boost::iterator_adaptor to put an iterator ontop of your ForwardIterator range and deal with iteratos only. That might be cheaper instead of createing set of value_types create a set of iterators. Overloading your own less then operator might compare boost::iterator_adaper-specialization instances which are than stored in std::set. Set will only contain iterators and not real object instances. This assumes that your input range lives long enough. Or you can intorduce a filter_iterator which might implement a sort of lazy unique iterator. So it might contain a set with objects already iterated though and decide whether to skip to the next element when incremented or not. Hope that helps, Ovanes

5741

Age (days ago)

5743

Last active (days ago)

List overview

Download

5 comments

3 participants

participants (3)

David Abrahams
Ovanes Markarian
Sandeep Gupta