Comparing a string to many strings?

[arao6]

I need to compare one string to nearly 60 other strings in real-time. Right now I'm doing this:

if (str.compare("somestring") == 0)
   DoSomething();
else if (str.compare("anotherstring") == 0)
   DoSomethingElse();
// 60 or so else..ifs later
else
   DoSomeOtherThing();

It works, but you can sort of notice the lag. Is there any fast method to compare a string to many other strings?

[vlad from moscow]

In any case as I have understood you must compare str with each string literal until you find the exact match. Only I would use == operator instead of the member function compare.

If you could have all string literals in a sorted array then you could use the binary search and switch statement for the index of the array.

[JLBorges]

Assuming that the compiler will generate the fastest possible code for std::memcmp() (perhaps an intrinsic):

constexpr std::size_t NSTRINGS = 60 ;

const char* literal_cstr[NSTRINGS] =
{
    "abcd",
    "efghijk",
    // 58 more strings
};

std::size_t string_length[NSTRINGS] ;

int main()
{
    // one time initialization
    std::transform( literal_cstr, literal_cstr+NSTRINGS, string_length, std::strlen ) ;

    std::string str ;
    std::getline( std::cin, str ) ;
    const std::size_t sz = str.size() ;

    for( std::size_t i = 0 ; i < NSTRINGS ; ++i )
    {
        if( ( sz == string_length[i] ) && ( std::memcmp( str.data(), literal_cstr[i], sz ) == 0 ) )
        {
            // equal
        }
    }
}

[Peter87]

You can use std::map (or std::unordered_map) to look up things very fast.

One way to do it is to define constants or enum values for each of the strings.

enum E
{
	e1,
	e2
};

You should probably use more descriptive names in the real code.

Then you define and initialize a map to map string values to the enum values. The map can be reused for all lookups so you only need to do this once.

std::map<std::string, E> m;
m["somestring"] = e1;
m["anotherstring"] = e2;

When you have a string to handle you first lookup the enum value in the map. You then use a switch to handle all the enum values.

std::map<std::string, E>::iterator it = m.find(str);
if (it != m.end())
{
	switch (it->second)
	{
	case e1:
		DoSomething();
		break;
	case e2:
		DoSomethingElse();
		break;
	}
}
else
{
	DoSomeOtherThing();
}

The switch should be very fast because the enum values doesn't contain any gaps, allowing the compiler to implement it as a branch table.


Another way is to have a map mapping strings to function pointers (or std::function, possibly using lambdas).

std::map<std::string, void(*)()> m;	
m["somestring"] = &DoSomething;
m["anotherstring"] = &DoSomethingElse;

To handle a string you just need to look up the function pointer and call the function.

std::map<std::string, void(*)()>::iterator it = m.find(str);
if (it != m.end())
{
	it->second();
}
else
{
	DoSomeOtherThing();
}

[ne555]

It works, but you can sort of notice the lag.

60 is a really low number, you shouldn't be able to notice it.
¿are you sure that there is your bottleneck?

[arao6]

Thanks everyone! This helped a lot.

@ne555: The strings are being compared in the graphics thread in a game. Unfortunately, this part of the code could not be put on a separate thread because the subsequent action taken by the graphics engine relies on the input provided here.

[hanst99]

The strings are being compared in the graphics thread in a game.

In that case, rather than comparing strings you should probably keep a symbol table (a mapping from strings to numbers) around. String comparisons can be rather costy, number comparisons not so much. While doing a few thousand string comparisons per second still isn't likely to be a bottleneck, you could definitely save some cycles there if you really have to.