c++ - 计算搜索比较 C++

Question

此程序在字典文本文件中搜索用户输入的单词并输出它所在的行。我需要计算在线性搜索和二分搜索中找到单词的比较次数。现在它说进行了零比较。任何关于在何处或如何实现这些计数器的想法都将不胜感激。

string linearSearch(const vector<string> &L, string k);
string binarySearch(const vector<string> &L, string k, int a = 0, int b = -1);
int count1 = 0;
int count2 = 0;

int main()
{

    ifstream inFile;
    inFile.open("dictionary.txt");

    vector < string > words;
    string line;

    while (getline(inFile, line))
    {
        words.push_back(line);
    }

    inFile.close();
    string userWord;
    cout << "Search for a word: " << endl;
    cin >> userWord;

    if (words.empty())
    {
        return -1;
    }

    cout << "Using binary search, the word " << userWord << " is in slot "
            << binarySearch(words, userWord) << ". There were " << count2
            << " comparisons  made." << endl;

    cout << "Using linear search, the word " << userWord << " is in slot "
            << linearSearch(words, userWord) << ". There were " << count1
            << " comparisons made." << endl;

    return 0;
}
string linearSearch(const vector<string> &L, string k)
{

    for (int i = 0; i < L.size(); ++i)
    {
        count1++;
        if (L[i] == k)
        {
            count1++;
            return to_string(i);
        }
    }
    return to_string(-1);

}
string binarySearch(const vector<string> &L, string k, int a, int b)
{

    ++count2;
    if (b == -1)
    {
        b = L.size();
    }
    int n = b - a;

    if (n == 0)
    {
        return to_string(-1); //?
    }

    int mid = (a + b) / 2;

    if (L[mid] == k)
    {
        ++count2;
        return to_string(mid);
    }
    else if (L[mid] > k)
    {
        ++count2;
        return binarySearch(L, k, a, mid);
    }
    else
    {
        count2 += 2;
        return binarySearch(L, k, mid + 1, b);
    }
    return to_string(-1);

}

Answer 1

哦，哦，这看起来像是由序列点引起的未定义行为(有关更多信息，请参阅 this question)。

引用那个问题的答案，

the order of evaluation of operands of individual operators and subexpressions of individual expressions, and the order in which side effects take place, is unspecified.

您正在尝试对同一序列点中的同一变量(计数之一)执行集合和获取。哪个先发生(设置或获取)是未定义的。

将你的 cout 分成两部分，一切都应该得到解决。

cout << "Using binary search, the word "<< userWord << " is in slot " << 
    binarySearch(words,userWord) << ".";
cout << "There were " << count2 << " comparisons made." << endl;

cout << "Using linear search, the word "<< userWord << " is in slot " << 
    linearSearch(words,userWord) << ".";
cout << "There were " << count1 << " comparisons made." << endl;