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
std::unique will do what you want. But it comes with a conditions though... You must have 'consecutive equal elements' std::unique can't be used on an associative container If you can't satisfy these requirements, you could try inserting all your data into a set<>, as Dave suggests. Then copying it all into a vector<> and calling unique() on it. Perhaps you could copy from the set<> into a list<>, then use the set class's unqiue() member, as it's more efficient due to relinking ptrs and not assigning element values. ~Damian(); On Wed, Feb 25, 2009 at 6: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 _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Wed, Feb 25, 2009 at 1:18 PM, Damian Coventry <damian.coventry@gmail.com> wrote:
std::unique will do what you want. But it comes with a conditions though...
You must have 'consecutive equal elements' std::unique can't be used on an associative container
If you can't satisfy these requirements, you could try inserting all your data into a set<>, as Dave suggests. Then copying it all into a vector<> and calling unique() on it.
Perhaps you could copy from the set<> into a list<>, then use the set class's unqiue() member, as it's more efficient due to relinking ptrs and not assigning element values.
~Damian();
Thanks Damian, Not sure if I understood correctly. Stl set is a "Unique Associative Container". Hence storing them in set will remove duplicates automatically. there wont be any need to call unique on the set elements. -sandeep
On Wed, Feb 25, 2009 at 6: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 _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (3)
-
Damian Coventry -
David Abrahams -
Sandeep Gupta