c++ - 如何在 C++ 中对两个向量进行线性搜索？

Question

更新：我的代码有效，此代码之外有问题。

我有两个包含类书籍对象的向量。一个向量有新书，另一个向量包含请求的书。我正在尝试创建一个线性搜索函数来计算两个向量之间匹配书籍的数量。

这是我的线性搜索功能：

int linear(vector<Books> New, vector<Books> Requested){
  int matches = 0;
  for (int i = 0; i < New.size(); i++){
    for (int j = 0; j < Requested.size(); j++){
      if (New[i].convstr() == Requested[j].convstr())
        matches++;
    }
  }
  cout << matches << endl;
}

我还有一个 convstr() 函数将对象转换为字符串以比较它们（在类 Books 中它是公共的）：

string Books::convstr(){
  string strisbn;
  strisbn = to_string(isbn);
  return strisbn + language + type;
}

每当我输入两个向量并尝试打印匹配数时，即使存在匹配，它也总是打印零。

Answer 1

std::set_intersection正如@ Jarod42所说，您可以使用O(n log n). 如果数组已排序，则此代码段正在完成工作。

#include <algorithm>

template <typename T>
T getCommonItems(T &container_0, T &container_1) {
    T cache;
    cache.reserve(std::min(container_0.size(), container_1.size()));
    std::set_intersection(container_0.begin(), container_0.end(), container_1.begin(), container_1.end(),
                          std::back_inserter(cache));
    return cache;
}

Answer 2

对于初学者，该函数应至少声明为

size_t linear( const vector<Books> &New, const vector<Books> &Requested );

否则将创建向量的冗余副本。

还假设向量不包含重复的书籍，第二个循环可以缩短。

至于您的函数实现，那么您忘记了返回变量的值matches。

该函数可以通过以下方式定义

#include <iterator>
#include <algorithm>

//...

size_t linear( const vector<Books> &New, const vector<Books> &Requested )
{
    size_t matches = 0;

    for ( const auto &book : New )
    {
        if ( std::find_if( std::begin( Requested ), std::end( Requested ), 
                           [&book]( const auto &item ) { return book.convstr() == item.convstr(); } ) != std::end( Requested ) )
        {
            ++matches; 
        }
    }

    return matches;
}

请注意，成员函数 convstr 应使用限定符声明const。例如

bool convstr() const;