-1

I'm using map to store data. The map has really big data. I want to find keys that has a prefix, the limit for number of result items is 50. I want to use fastest way for search, not iterate through whole map and check, since map is a structured key-value container already.

For example, if I have some pairs: 

<"foo123", value>

<"foo234", value>

<"bar12", value>

<"foo456", value> 

<"bar200", value>

if I search for "foo", it will suggest for me 

foo123, foo234, foo456.
Filip Roséen - refp
  • 62,493
  • 20
  • 150
  • 196
abelhoang
  • 271
  • 4
  • 14
  • You may use [`std::find_if()`](http://en.cppreference.com/w/cpp/algorithm/find) and provide your own function to check for the prefix. – πάντα ῥεῖ May 31 '15 at 09:53
  • 1
    @πάντα ῥεῖ That's linear time, and totally unnecessary in this case. – Ami Tavory May 31 '15 at 09:56
  • I researched the question you provided above before asking. I see lower_bound return the first iterator of found key. Can you instruct me how to find the next one. Thanks so much! – abelhoang May 31 '15 at 10:13
  • After you find the iterator, you can simply increment it until it no longer matches the prefix or 50 passes. I suggest you close this question, however. In the future, if there's a question strongly resembling your own, perhaps you should reference it, and explain what is the delta between it and the problem you're having. – Ami Tavory May 31 '15 at 10:15

1 Answers1

7

There are two approaches that come to mind:

  • The first is a special container called trie, for which there is no equivalent in the C++ standard library, but you should be able to locate working versions easily.

  • The second approach simply uses the fact that in a std::map, the key "foo" sorts before "foo123". Using the upper_bound or lower_bound functions to find a starting range quickly and from there on use a linear search.

Ulrich Eckhardt
  • 16,572
  • 3
  • 28
  • 55