best way to remove duplicates from forwardIterator [startIter, endIter]
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
on Tue Feb 24 2009, Sandeep Gupta <gupta.sandeep-AT-gmail.com> 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
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 <dave@boostpro.com> wrote:
on Tue Feb 24 2009, Sandeep Gupta <gupta.sandeep-AT-gmail.com> 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
On Tue, Feb 24, 2009 at 5:46 PM, Sandeep Gupta <gupta.sandeep@gmail.com>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<std::iterator_traits<IterType>::value_type> make_unique_elements; make_unique_elements uniques_(startIter, endIter); Hope that helps, Ovanes
On Thu, Feb 26, 2009 at 5:05 AM, Ovanes Markarian <om_boost@keywallet.com> wrote:
On Tue, Feb 24, 2009 at 5:46 PM, Sandeep Gupta <gupta.sandeep@gmail.com> 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<std::iterator_traits<IterType>::value_type> 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
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
participants (3)
-
David Abrahams -
Ovanes Markarian -
Sandeep Gupta