Geek Answers Handbook

Name search container

I want to store strings and return each with a unique identification number (the index will be fine). I need only one copy of each line, and I need a quick search. I check if a row in the table exists often enough so that I notice that you are logged in. What is the best container to use for this and how to search if a string exists?

+5
source share
8 answers

I would suggest tr1 :: unordered_map. It is implemented as a hashmap, so it has the expected complexity of O (1) for searching and the worst case of O (n). There is also an enhancement implementation if your compiler does not support tr1.

#include <string>
#include <iostream>
#include <tr1/unordered_map>

using namespace std;

int main()
{
    tr1::unordered_map<string, int> table;

    table["One"] = 1;
    table["Two"] = 2;

    cout << "find(\"One\") == " << boolalpha << (table.find("One") != table.end()) << endl; 
    cout << "find(\"Three\") == " << boolalpha << (table.find("Three") != table.end()) << endl; 

    return 0;
}
+9
source

std:: map.

+5

. , , , , .

N - , , C , ( ).

  • :

    • O(C) - ,
    • O(1 x C) O(N x C), 1..N - , -, C,
    • : O(2 x C) O((N + 1) x C)

  • std::map ( - ) :

    • : O(1 x C) O(log(N) x C) - O(log(N)) - , O(C) - std::map generic less<>,

N -, , log (N) , , , (std::map) . N , , - ( , .)

- , :

+4

, , . , , , NULL.

EDIT: , , .

EDIT: , , std::map<std::string, int>. .

+2

String ? ,

+2

std:: map.

:

#include <map>
using namespace std;

...

   map<string, int> myContainer;
   myContainer["foo"] = 5; // map string "foo" to id 5
   // Now check if "foo" has been added to the container:
   if (myContainer.find("foo") != myContainer.end())
   {
       // Yes!
       cout << "The ID of foo is " << myContainer["foo"];
   }
   // Let get "foo" out of it
   myContainer.erase("foo")
+1

Google

0

More articles:


All Articles