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

Question

I have std :: set from 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 often call this function (yes, very often), so I want to perform this check without creating a temporary copy of the string. Is there a way to do this as simple and red as what I have here, but which does not create a temporary copy of the string? Any solution with STL or Boost containers would be nice.

Answer 1

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

Answer 2

Does profiling actually show that string copy is a significant issue here?

If so, can you change the existence function so that it pairtakes instead of two arguments and arranges a line that should be built directly in a pair, and not separately?

If you cannot do this, you can always use shared_ptr<std::string>as your second element pairand come up with a comparison function that compares strings from addresses, not strings of values.

Answer 3

.

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;

Answer 4

Unfortunately, you cannot do this in the C ++ standard library without changing key_typeto something referenced. There are other container libraries that have a search function with template parameters, which allows you to use various types of search and comparators (for example, Boost.Intrusive). Other than that, you can simply hope that the optimizer will remove the copy build. (Benchmark!)

Answer 5

Write a functor that stores the link of the target line:

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_;
  }
};

Using:

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