1

Say I have two std::set<std::string>s. The first one, old_options, needs to be merged with additional options, contained in new_options. I can't just use std::merge (well, I do, but not only that) because I also check for doubles and warn the user about this accordingly. To this effect, I have

void merge_options( set<string> &old_options, const set<string> &new_options )
{
    // find duplicates and create merged_options, a stringset containing the merged options
    // handle duplicated the way I want to
    // ...
    old_options = merged_options;
}
  1. Is it better to use

    std::swap( merged_options, old_options );
    

    or the assignment I have?

  2. Is there a better way to filter duplicates and return the merged set than consecutive calls to std::set_intersection and std::set_union to detect dupes and merge the sets? I know it's slower than one traversal and doing both at once, but these sets are small (performance is not critical) and I trust the Standard more than I trust myself.

3 Answers 3

1

What's wrong with

void merge_options( set<string> &old_options, const set<string> &new_options )
{
    for (set<string>::iterator i = new_options.begin();
         i != new_options.end(); ++i)
        if (old_options.find(*i) != old_options.end())
            warn_duplicate(*i);
        else
            old_options.insert(*i);
}

This is a simple O(m lg n) algorithm, where m = new_options.size() and n = old_options.size().

3
  • simple, yes, but isn't mine the same in performance (if you neglect the factor 2, which shouldn't matter in big-O). I had a simultaneous traverse in mind, which would essentially be O(log(max(M,N)). That would really gain performance, but as Jerry says, is more complicated and perhaps not useful here. I was just making sure I'm not missing a C++ library function.
    – rubenvb
    Mar 6, 2011 at 16:34
  • @rubenvb: A simultaneous traversal would be O(max(m,n)), I think. The difference between this and your version is 1) less allocations and copying (assuming C++03) and 2) I think mine is clearer. I don't think the standard library has a shorter way of doing this, but I must admit <algorithm> keeps surprising me.
    – Fred Foo
    Mar 6, 2011 at 16:40
  • ah yes, log is for binary search, stupid me =s. @Blastfurnace has a nice one too. (and <algorithm> keeps surprising me as well, hence the question)
    – rubenvb
    Mar 7, 2011 at 10:32
1

Given (as you've stated) that performance isn't critical here, I'd use the assignment and the two-pass algorithm. It's simpler and easier to understand; it's only worth using a "trick" like swap if you really need what it gains.

Writing your own algorithm wouldn't be such a bad thing, but again, unless you have a real use for the benefit it provides, I wouldn't bother.

1

This is in part an answer to larsmans. There is a remove_copy_if algorithm that encapsulates his for loop into a single function. The following uses a C++0x lambda for the predicate.

void merge_options( set<string> &old_options, const set<string> &new_options )
{
    remove_copy_if(
        new_options.begin(),
        new_options.end(),
        inserter(old_options, old_options.end()),
        [&](const string &s) {
            return (old_options.count(s)) ? warn_duplicate(s), true : false;
        }
    );
}
2
  • Yes, same complexity. What does the & in the lambda introducer do? I'm not familiar with lambdas yet.
    – Fred Foo
    Mar 7, 2011 at 10:50
  • 1
    @larsmans: It's a capture clause that allows the lambda to access variables in the enclosing scope. The & accesses all captured variables by reference. In this case it allows the lambda to see (and modify) the old_options set. Mar 7, 2011 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.