Take the 2-minute tour ×

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.

share|improve this question
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 Jan 10 '11 at 17:03
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 Jan 10 '11 at 17:40
Copy a string is not as expensive as you think. Write clean code first optimize latter when you prove it is a choke point. –  Loki Astari Jan 10 '11 at 18:31

5 Answers 5

up vote 4 down vote accepted

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

share|improve this answer
I think this is probably the best answer. I'm using C++03 (no C++0x r-value reference features, so can't use unique_ptr), and yes, I do want to keep the O(log n) time. This will be messy, but C++ is messy. –  James Brock Jan 10 '11 at 16:45
This has the bad side effect of forcing you to manually manage the memory stored in the container. In the original code, as the set goes out of scope the memory held in the strings will automatically be freed by the container, by changing it to hold pointers, the set destructor will not release the strings. This will add complexity and fragility to other parts of the code. –  David Rodríguez - dribeas Jan 10 '11 at 16:55
Yes, that's true. –  James Brock Jan 10 '11 at 17:32

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.

share|improve this answer
or unique_ptr, which is a bit lighter on resources –  rubenvb Jan 10 '11 at 16:23
@rubenvb: If unique_ptr is available, anyway. It depends on rvalue references, which are not yet actually in the standard, and isn't implemented in all modern compilers. –  David Thornley Jan 10 '11 at 16:27
@David: true, but it really is better in simple use cases ;) –  rubenvb Jan 10 '11 at 20:53

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!)

share|improve this answer

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


std::set< std::pair<size_t, std::string> >::iterator i = std::find_if( set_.begin(), set_.end(), match_str(s) );
share|improve this answer
Remove the copy and exchange an O(log n) algorithm by an O(n) one? I think that'll make things slower, not faster. –  ltjax Jan 10 '11 at 16:36
@ltjax: So? @James Brock asked for "Any solution" that did not copy strings. This does that. –  John Dibling Jan 10 '11 at 16:43
Common-sense! Don't make the algorithm worse in an optimization question ;-) –  ltjax Jan 10 '11 at 17:17

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;
share|improve this answer
But unlike the built-in find, this does not have log(n) look-up times. –  ltjax Jan 10 '11 at 16:27
@ltjax: I've edited the answer so that it skips to the portion with the correct size_t part in log(n) look-up time. The search within that portion is still linear, though. If there's only a few strings per size_t, this will be not noticeable. –  etarion Jan 10 '11 at 17:03

Your Answer


