Find all instances of element in array

Question

I've created a function to return all the indices where an element is to be found in an array. If it occurs twice or more, all the respective indices will be returned, for now it returns them in natural counting (1,2,3...) and not how the computer sees them (0,1,2,...).

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

void searchList(int theArray[], int sizeOfTheArray, int findFor);

void searchList(int theArray[], int sizeOfTheArray, int findFor){
  vector<int> foundIndices;

  int j = 0;

  for (int i = 0; i < sizeOfTheArray; i++)
  {
    if (theArray[i] == findFor){
      foundIndices.push_back(i);
      j++;
    }
  }

  if (foundIndices.size()!=0){
    cout << "Found in index: ";
    for (int i = 0; i < foundIndices.size(); i++){
      cout << foundIndices[i]+1 << " ";
    }
  }
  else
    cout << "Not found in array";
}

int main(){
  int test[8] = {87, 75, 98, 100, 100, 234, 265, 9};
  searchList(test, 8, 99);
  return 0;
}

Answer 1

Separation of Concerns

The function should have only one concern--finding the indices. Printing out results is a separate concern that shouldn't be combined with finding the indices. Combining the two makes it difficult or impossible to use in a wide variety of situations.

Vacuous Declaration

Having the declaration followed immediately by the definition renders the declaration just extra visual noise.

Pointless Work

In your function, you initialize and increment j, but you never seem to make any use of it.

Inconsistent Types

The type normally used for indices into arrays is size_t, but you're returning a vector of int instead.

Intermixing Arrays and Vectors

Although it's not exactly an error, it is a bit strange to have an array as the input type, and a vector as the result type. Typically you'd want to pick one or the other, and use it consistently. The other obvious possibility would be to have the function itself work with iterators, so it doesn't have to specify the type of the collection itself at all (and can be written generically, so it can work with essentially any collection).

const Correctness

Since this function shouldn't modify the input array, it's better to pass that as a pointer to const (note: although your parameter definition uses array notation, what's passed is actually a pointer). If you use a vector as input, you'd probably want to pass it as a reference to const.

Answer 2

Everything @Jerry said.

In addition I echo the view of @Bizket but disagree with the better solution.

C++ emphasize the use of concepts (the exact type does not matter, the interface of the type is what matters when designing). You loop over an C-array and Bizkit says you should update to specific C++ container types. I would suggest that you update to use generic C++ container types (as long as your input acts like a container) that support the interface you need (then let the compiler verify its correct).

Also C++ tends to use Iterators to define ranges (or containers). This allows you to be more flexible issue.

Also why are you constraining your algorithm to int? Just make it generic then you don't need to write it again for other types.

template<typename C, typename V>
std::vector<std::size_t> searchList(C const& theContainer, V const& findFor)
{
    return searchList(std::begin(theContainer), std::end(theContainer), findFor);
}
template<typename I>
std::vector<std::size_t> searchList(I begin, I end, std::iterator_traits<I>::value_type const& findFor)
{
    std::vector<std::size_t> result;

    for(std::size_t  index = 0; begin != end; ++begin, ++index)
    {
        if ((*begin) == findFor)
        {
            result.emplace_back(index);
        }
    }
    return result;
}

Note: the exact type does not matter. Type is still the most important thing of a C++ object. But the exact type does not matter just that it has a specific type and that you can determine the interface of the type at compile time.

Answer 3

Your description of what the function does is actually not correct. You mention that the function:

return[s] all the indices where an element is to be found in an array. If it occurs twice or more, all the respective indices will be returned, for now it returns them in natural counting (1,2,3...) and not how the computer sees them (0,1,2,...)

However, your function declaration is this:

void searchList(int theArray[], int sizeOfTheArray, int findFor);

As you can see, the function doesn't actually return anything.

Since this is C++, you should stay away from using C-style arrays and use either std::array or std::vector instead. In this way, you won't need to supply the size of the provided array into the function. Also, as @Jerry Coffin mentioned, you should use size_t as the type to hold array indexes:

vector<size_t> searchList(const vector<int>& theArray, int findFor)
{
    vector<size_t> indexes;
    for (size_t i = 0; i < theArray.size(); ++i){
        if (theArray[i] == findFor){
            indexes.push_back(i + 1);
        }
    }
    return indexes;
}

You can then handle all I/O in the main function like this:

int main()
{
    vector<int> test {87, 75, 98, 100, 100, 234, 265, 9};
    auto indexes = searchList(test, 99);
    if (indexes.empty()) {
        cout << "Not found in array";
    } else {
        for (const auto &index : indexes) {
            cout << index << " ";
        }
    }
}

Answer 4

My 5 cents,

Welcome to the future!

If you are allow to use C++11, you can use shiny new C++11 range for loop, e.g.

     for(const auto &item : container)
           std::cout << item << std::endl;

However if you can not use C++11 stick to good old for loop, but with iterator.

Why collect indexes in container?

Another thing I do not like - why you collecting the indexes into std::vector? If this is requirement - OK. If is not - print the data inside search loop. Another way is make 2 functions, one to search and return std::vector, another for printing the results:

 std::vector<int> findDuplicates(...);
 void print(const std::vector<int> &container);

Print

you could also do printing function to be able to print all kind of containers:

 template<class CONTAINER>
 void print(const CONTAINER &container){
     // C++11 for
     for(const auto &item : container)
           std::cout << item << std::endl;
 }

using namespace std;

Finally, I did not saw anybody mention it - remove using namespace std; and type std:: when need. This is because lots of packages provide same classes, for example there is std::string and boost::string. In mid-size project using namespace std; will do lot of harm.