HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Linear search algorithm template implementation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
lineartemplatesearchalgorithmimplementation

Problem

This template class is a linear search algorithm with a simple search function. I have tested it with int and char and it seems to be working fine. I would like pointers on how I can make it more efficient and on my coding technique. I do know that the standard library provides this algorithm, i am just doing it for fun and practice

sLinear.h

//Linear search template

#ifndef SLINEAR_H
#define SLINEAR_H

namespace fm
{
    template 
    class sLinear
    {
        T *_list;
        T _item;
        int _sizeOfList;

    public:
        sLinear();
        sLinear(T *myArray, T item, int size);

        ~sLinear();

        int findItem();

    };

    //------public methods------
    template 
    sLinear::sLinear()
    {
        _list = nullptr;
        _sizeOfList = 0;
    }

    template 
    sLinear::sLinear(T *myArray, T item, int size)
    {
        _list = myArray;
        _item = item;
        _sizeOfList = size;
    }

    template 
    sLinear::~sLinear()
    {
        _list = nullptr;
        _sizeOfList = 0;
    }

    template 
    int sLinear::findItem()
    {
        while (_list != nullptr)
        {
            for (int i = 0; i < _sizeOfList; i++)
            {
                if (_list[i] == _item)
                {
                    return i + 1;
                }

            }

            return -1;

        }
    }
}
#endif


main.h

#include
#include "sLinear.h"

using namespace fm;

int main()
{

    /* Linear search with integer */
    int iList[] = { 1,9,2,6,5,3,7,4,8,0 };
    int size = (sizeof(iList) / sizeof((iList[0])));

    sLinear mySearch(iList, 8, size);
    int k = mySearch.findItem();

    if (k == -1)
        std::cout << "Item not found!" << std::endl;
    else
        std::cout << "Item found:" << k << std::endl;

    return 0;
}

Solution

-
Returning int is dubious; it unnecessarily narrows the range of possible return values. Consider retuning an iterator.

-
The line if (_list[i] == _item) implies that _list must provide an operator[](int), which is very restrictive. A linear search is just like its name implies, linear. It is expected to work on any linear collection, e.g. forward iterator (maybe even on input iterator).

-
The class sLinear exposes one public method, and keeps no state. There's no reason to make it a class. A standalone

template 
I findItem(I first, I last, I::value_type value) {
    ....
}


will do as well.

-
while (_list != nullptr) is very strange. _list never changes; why do you want to loop?

PS: Could you explain a rationale for returning i+1?

Code Snippets

template <typename I>
I findItem(I first, I last, I::value_type value) {
    ....
}

Context

StackExchange Code Review Q#161561, answer score: 4

Revisions (0)

No revisions yet.