Reputation: 11
This code is a linear search program using arrays. Out of curiosity, I was wondering how this code could be rewritten using STL vectors in place of arrays but still have the same output.
#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;
}
Upvotes: 1
Views: 1318
Reputation: 677
Please look at the following example that uses STL linear search algorithm. And see possible implementations of std::find and an example of usage it for a vector here: https://en.cppreference.com/w/cpp/algorithm/find It would give you a good answer on your question.
#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;
}
Upvotes: 0
Reputation: 14730
template <typename T>
int linearSearch(T list, int key)
Changing the two first lines of your code as above, as well as replacing arraySize
with list.size()
should suffice for any kind of container supporting operator []
(including vectors), and indices as consecutive int
.
Note that while your template tries to abstract the content of the array as the typename T
, it implicitely assumes it is int
in the type of key
. A more generic implementation would be:
template <typename T>
int linearSearch(T list, typename T::value_type key)
Another issue in this solution is the passing mode of list
. We can overcome this issue by converting it to a reference like so:
// 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;
}
Upvotes: 0
Reputation: 158469
With as few changes as possible you could do this:
#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;
}
I would recommend not using using namespace std;
.
Upvotes: 0
Reputation: 56479
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);
}
Note: C++11 is enabled
Upvotes: 1
Reputation: 9063
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.
Upvotes: 1
Reputation: 23634
you can do it by changing your parameter type and in 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;
}
Upvotes: 1