Sign in to follow this  

Find _all_ equal ranges in a set - using STL

This topic is 3597 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I have a set which contains elements of a custom class. I take care that insertion in the set happens on the basis of strict weak ordering (function of one of the data elements that the class contains) Now, due to some requirements, I need to find all the equal ranges in the set - mind you the equality/equivalence is defined on the basis of a _different_ data element of the class (as compared to when I do insertion). e.g. class Data{ private: int insert_sort_field; char* some_data; }; In the example above, I insert based on ordering of "insert_sort_field", but I need equal ranges on the basis of "some_data" - and moreover, all such equal ranges. The first thing that occurs to me is copy over the elements of a set to a vector and sort them on basis of "some_data" - then use a for loop in the foll manner: Data * previous=0; typedef vector<Data*>::iterator DataIter; DataIter iter_begin=sorted_vector.begin(), iter_end=sorted_vector.end(); for(;iter_begin!=iter_end;) { if(!previous) { previous=(*iter_begin); ++iter_begin; continue; } pair<DataIter,DataIter> p= equal_range(iter_begin, iter_end, compare_functor(*iter_begin) ); DoSomeWorkOnTheRange(p.first, p.second); iter_begin=p.second; previous=NULL; } Is there a cleaner way - using for_each and stuff. I mean I want to do it in a clean manner using standard STL algos, rather roll my own loop. Any ideas??

Share this post


Link to post
Share on other sites
The same algorithmic performance as your version but worse constant multipliers in both time and space, best I could come up with just using the SC++L algorithms.

typedef std::multiset<Data*, compare_functor> mset_t;

struct do_work
{
do_work(mset_t& mset) : mset(&mset) { }

void operator()(Data* d)
{
std::pair<mset_t::iterator, mset_t::iterator> iters = mset->equal_ranges(d);
DoSomeRealWork(iters.first, iters.second);
}

mset_t* mset;
};

int main()
{
mset_t mset(input.begin(), input.end());
std::vector<Data*> unique;
std::unique_copy(mset.begin(), mset.end(), std::back_inserter(unique), compare_functor());
std::foreach(unique.begin(), unique.end(), do_work(mset));
}

Share this post


Link to post
Share on other sites
1) Why not std::string for some_data?

2) Instead of sorting the vector, you could iteratively 'partition' it:


typedef vector<Data*>::iterator DataIter;

// You could change 'it' via a reference, but the code doesn't really
// get any simpler.
DataIter grabAndProcessMatchingElements(DataIter it, DataIter end) {
// Move elements matching the current iterator to the beginning of the
// remaining part of the vector.
DataIter result = std::partition(it, end, eq_functor(*it));
DoSomeWorkOn(it, result);
return result;
}

DataIter end = v.end();

for (DataIter it = v.begin(); it != end;
it = grabAndProcessMatchingElements(it, end));



Also notice the loop structure :) You don't actually want weird incrementing logic, because of how iterator ranges work.

This is pretty, but probably quite a bit slower. :( In the worst case, O(N^2), because the iterated partitionings don't help each other out.

I guess O(N lg N) is really unbeatable here. We might save time in the sorted version, in "bad" cases, by just doing a linear sweep: std::equal_range will do a binary search every time, because it doesn't "know" that you want to iteratively search out every possible value.

Share this post


Link to post
Share on other sites

This topic is 3597 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this