std::set<std::pair<size_t, std::string> >::find(), without a string copy construction

3
votes

I have an std::set of std::pairs, and the second pair is a string. I want to check if a pair exists in the set.

std::set< std::pair<size_t, std::string> > set_;

bool exists(size_t x, const std::string& s)
{
    std::set< std::pair<size_t, std::string> >::iterator i = set_.find(std::make_pair(x, s)); // copy of s is constructed by make_pair!
    return i != set_.end();
}

I call this function often (yes, very often), so I want to perform this check without making a temporary copy of the string. Is there a way to do this which is as simple and terse as what I have here, but which does not make a temporary copy of the string? Any solution with STL or Boost containers would be nice.

5
c++stl
You're doing it wrong. Write the code that's straight-forward, clean, and works. Then way down the line, when you're done, profile your application, and optimize what the results say are slow; not guess. - GManNickG
There's a lot of advice here that I shouldn't worry about the performance of this function until I have evidence that this function is causing performance problems, and I just want to mention to anyone reading this post that this is marvelously good advice in general. Just not in this particular case. - James Brock
Copy a string is not as expensive as you think. Write clean code first optimize latter when you prove it is a choke point. - Martin York

5 Answers

5
votes

Use pointer to string and override predicate less (see constructor of std::set)

2
votes

Did profiling actually show that the string copy is a significant problem here?

If so, are you able to change the exists function so it accepts a pair instead of the two arguments, and arrange for the string to be constructed directly into the pair instead of separately?

If you can't do that, you could always use a shared_ptr<std::string> as the second element of your pair and concoct a comparison function that compares strings from addresses rather than value strings.

1
votes

Unfortunately, you cannot do that in C++ Standard Library without changing the key_type to something reference-like. There are other container libraries that have a template-parametrized find function which allows different lookup-types and comparators (E.g. Boost.Intrusive). Other than that, you can just hope for the optimizer to remove the copy-construction. (Benchmark!)

1
votes

You could always do the find yourself.

static pair<size_t, std::string> helper(0,"");
typedef std::set< std::pair<size_t, std::string> >::iterator iterator_type;
helper.first = x;
for (iterator_type i = set_.lower_bound(helper); i != set_.end(); ++i) {
    if (i->first != x)
        return false;
    if (i->second == s)
        return true;
}
return false;
-1
votes

Write a functor that keeps a reference of the target string:

struct match_str : public std::unary_function<bool, std::string>
{
  match_str(const std::string& s) : s_(s) {};
  bool operator()(const std::pair<size_t, std::string>& rhs) const
  {
    return rhs.second == s_;
  }
};

Usage:

std::set< std::pair<size_t, std::string> >::iterator i = std::find_if( set_.begin(), set_.end(), match_str(s) );