c++ - 与迭代相比，为什么我的二进制搜索如此慢？

Question

我正在编写一个自动完成程序，该程序根据给定的字典文件和输入文件查找与一个字母或一组字符的所有可能匹配项。我刚刚完成了一个通过迭代搜索实现二分搜索的版本，我认为我可以提高程序的整体性能。

事实是，二分搜索比迭代搜索快 9 倍。是什么赋予了？我以为我是通过使用二进制搜索而不是迭代来提高性能。

运行时间(向左搜索)[Larger] :

这里是每个版本的重要部分，完整代码可以在my github构建和运行用 cmake。

二进制搜索函数(在循环给定的输入时调用)

---

bool search(std::vector<std::string>& dict, std::string in,
        std::queue<std::string>& out)
{
    //tick makes sure the loop found at least one thing. if not then break the function
    bool tick = false;  
    bool running = true;
    while(running) {
        //for each element in the input vector
        //find all possible word matches and push onto the queue
        int first=0, last= dict.size() -1;
        while(first <= last)
        {
            tick = false;
            int middle = (first+last)/2;
            std::string sub = (dict.at(middle)).substr(0,in.length());
            int comp = in.compare(sub);
            //if comp returns 0(found word matching case)
            if(comp == 0) {
                tick = true;
                out.push(dict.at(middle));
                dict.erase(dict.begin() + middle);      
            }
            //if not, take top half
            else if (comp > 0)
                first = middle + 1;
            //else go with the lower half
            else
                last = middle - 1;
        }
        if(tick==false)
            running = false;
    }
    return true;
}

迭代搜索(包含在主循环中):

---

for(int k = 0; k < input.size(); ++k) {
        int len = (input.at(k)).length();
        // truth false variable to end out while loop
        bool found = false;
        // create an iterator pointing to the first element of the dictionary
        vecIter i = dictionary.begin();
        // this while loop is not complete, a condition needs to be made
        while(!found && i != dictionary.end()) {
            // take a substring the dictionary word(the length is dependent on
            // the input value) and compare
            if( (*i).substr(0,len) == input.at(k) ) {
                // so a word is found! push onto the queue
                matchingCase.push(*i);
            }
            // move iterator to next element of data
            ++i;    
        }

    }

---

示例输入文件:

z
be
int
nor
tes
terr
on

Answer 1

不是删除 vector 中间的元素(这是相当昂贵的)，然后重新开始搜索，只需比较找到的项目前后的元素(因为它们应该彼此相邻)直到找到所有匹配的项目。

或者使用std::equal_range ，正是这样做的。