1

此代码是使用数组的线性搜索程序。出于好奇，我想知道如何使用 STL 向量代替数组重写这段代码，但仍然具有相同的输出。

#include <iostream>
#include <string>
using namespace std;

template <typename T>
int linearSearch(T list[], int key, int arraySize)
{
  for (int i = 0; i < arraySize; i++)
  {
    if (key == list[i])
      return i;
  }

  return -1;
}

int main()
{
  int intArray[] =
  {
    1, 2, 3, 4, 8, 15, 23, 31
  };
  cout << "linearSearch(intArray, 3, 8) is " << linearSearch(intArray, 3, 8) << endl;
  cout << "linearSearch(intArray, 10, 8) is " << linearSearch(intArray, 10, 8) << endl;

  return 0;
}
4

6 回答 6

1

This could work (it is based on the STL implementation):

#include <iostream>
#include <string>
#include <vector>

using namespace std;

template <typename ForwardIter, typename Type>
int linearSearch(ForwardIter beg, ForwardIter end, Type key )
{
  int i = 0;
  for (;beg != end; ++beg)
  {
    if (key == *beg)
      return i;
    i++;
  }

  return -1;
}

int main()
{
  vector< int > vec = { 1, 2, 3, 4, 5, 6, 7 };
  cout << "linearSearch 1 is " << linearSearch(vec.begin(), vec.end(), 4) << endl;
  cout << "linearSearch 2 is " << linearSearch(vec.begin()+2, vec.end(), 1) << endl;

  return 0;
}

Note: it can also work for, std::list and std::deque. I think it will produce correct results even in a normal array.

于 2013-03-22T19:40:06.207 回答
1

您可以通过更改参数类型和 main.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

template <typename T>
int linearSearch(vector<T> list, int key)
{
   for (size_t i = 0; i < list.size(); i++)
   {
      if (key == list[i])
        return i;
   }

   return -1;
}

int main()
{
  int intArray[] =
  {
    1, 2, 3, 4, 8, 15, 23, 31
   };
   vector<int> list(intArray, intArray+8);

   cout << "linearSearch(list, 3,) is " << linearSearch(list, 3) << endl;
   cout << "linearSearch(list, 10) is " << linearSearch(list, 10) << endl;

   return 0;
}
于 2013-03-22T19:34:22.453 回答
1 
template <typename T>
int linearSearch(const vector<T> &list, const T &key)
{
    auto itr = std::find(list.begin(), list.end(), key);

    if (itr != list.end())
        return std::distance(list.begin(), itr);
    else
        return -1;
}

int main()
{
    int intArray[] = {1, 2, 3, 4, 8, 15, 23, 31};

    std::vector<int> vec(intArray, intArray + 8);

    int i = linearSearch(vec, 15);
}

注意：启用 C++11

于 2013-03-22T19:31:55.793 回答
0

请看以下使用 STL 线性搜索算法的示例。并在此处查看 std::find 的可能实现以及将其用于向量的示例：https ://en.cppreference.com/w/cpp/algorithm/find 它会为您的问题提供一个很好的答案。

#include <algorithm>
#include <iostream>
#include <vector>


int main() {

    std::vector<int> intsCollection {1, 2, 3, 4, 8, 15, 23, 31};
        
    std::vector<int>::iterator val1 = std::find(intsCollection.begin(), intsCollection.end(), 3);
    int pos1 = (val1 != intsCollection.end()) ? (val1 - intsCollection.begin()) : -1;
    
    std::vector<int>::iterator val2 = std::find(intsCollection.begin(), intsCollection.end(), 10);
    int pos2 = (val2 != intsCollection.end()) ? (val2 - intsCollection.begin()) : -1;
        
    std::cout << "linearSearch(intsCollection, 3, 8) is " << pos1 << std::endl;
    std::cout << "linearSearch(intsCollection, 10, 8) is " << pos2 << std::endl;

}
于 2014-08-02T01:53:40.787 回答
0 
 template <typename T>
 int linearSearch(T list, int key)

如上所述更改代码的前两行，以及替换arraySize为list.size()应该足以支持任何类型的容器operator []（包括向量），并且索引为连续int.

请注意，虽然您的模板尝试将数组的内容抽象为 typename T，但它隐含地假定它int的类型为key. 更通用的实现是：

template <typename T>
int linearSearch(T list, typename T::value_type key)

此解决方案中的另一个问题是list. 我们可以通过将其转换为参考来克服这个问题，如下所示：

// includes ...
#include <type_traits>
using namespace std;

template <typename T>
int linearSearch(add_lvalue_reference<T> list, typename T::value_type key){
    for (size_t i = 0; i < list.size(); i++) {
        if (key == list[i])
            return i;
    }
    return -1;
}
于 2013-03-22T19:40:49.520 回答
0

通过尽可能少的更改，您可以这样做：

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// Using const std::vector<T> & to prevent making a copy of the container
template <typename T>
int linearSearch(const std::vector<T> &list, int key)
{
  for (size_t i = 0; i < list.size(); i++)
  {
    if (key == list[i])
      return i;
  }

  return -1;
}

int main()
{
  std::vector<int> arr = { 1 ,2, 3, 4, 8, 15, 23, 31 } ;

  cout << "linearSearch(intArray, 3) is " << linearSearch(arr, 3) << endl;
  cout << "linearSearch(intArray, 10) is " << linearSearch(arr, 10) << endl;

  return 0;
}

我建议不要使用using namespace std;.

于 2013-03-22T19:35:30.947 回答