CODEWITHSUNDEEP
c++string
Elpezmuerto
Elpezmuerto

Reputation: 5571

Bottleneck from comparing strings

This is a follow up question to Char* vs String Speed in C++. I have declared the following variables:

std::vector<std::string> siteNames_;
std::vector<unsigned int> ids_;
std::vector<std::string> names_;

I call this function tens of thousands of times and is a major bottleneck. Is there a more efficient way to compare strings? The answer must be cross-platform compatible. 

unsigned int converter::initilizeSiteId(unsigned int siteNumber){
    unsigned int siteId = 0;
    for (unsigned int i = 0; i < ids_.size(); i ++){
        if (siteNames_[siteNumber].compare(names_[i]) == 0){
            siteId = ids_[i];
            break; // Once found, will stop searching and break out of for loop
        }
    }
    if (siteId == 0)
        std::cerr << "Could not find ID for site number " << siteNumber << std::endl;

    return siteId;
}

Upvotes: 2

Views: 752

Answers (2)

JoshD
JoshD

Reputation: 12814

Use a map or unordered map instead. Then you can do this:

std::map<string, int>names_;
// ...

unsigned int converter::initilizeSiteId(unsigned int siteNumber){
    unsigned int siteId = 0;
    std::map<string, int>::iterator i = names_.find(siteNames_[siteNumber]);
    if (i != names_.end()){
        siteId = i->second;
    }
    else (siteId == 0)
        std::cerr << "Could not find ID for site number " << siteNumber << std::endl;

    return siteId;
}

This will perform in O(log n) time rather than the O(n) you had before.

There are other options if you have a sorted list, such as binary search.

Upvotes: 6

dutt
dutt

Reputation: 8209

If you often look up just a few different siteNumber and call it enough times it could be worthwile to implement a cache to store the latest siteNumber:s. Although since you're only working in memory and not to/from disk I doubt it.

Upvotes: 0

Related Questions