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

パラメータタイプとメインを変更することでそれを行うことができます。

#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 に答える
1

これは機能する可能性があります（STL実装に基づいています）：

#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;
}

注:std::list 、およびにも機能しstd::dequeます。通常の配列でも正しい結果が得られると思います。

于 2013-03-22T19:40:06.207 に答える
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 に答える
0 
 template <typename T>
 int linearSearch(T list, int key)

上記のようにコードの最初の 2 行を変更するだけでなく、(ベクトルを含む) をサポートするあらゆる種類のコンテナー、および連続するインデックスで十分arraySizeです。list.size()operator []int

テンプレートは配列の内容を typename として抽象化しようとしますが、T暗黙的intに の型であると想定していることに注意してくださいkey。より一般的な実装は次のようになります。

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

このソリューションのもう 1 つの問題は、 の受け渡しモードです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 に答える