How do I find an element position in std::vector?

Question

I need to find an element position in an std::vector to use it for referencing an element in another vector:

int find( const vector<type>& where, int searchParameter )
{
    for( int i = 0; i < where.size(); i++ ) {
       if( conditionMet( where[i], searchParameter ) ) {
           return i;
       }
    }
    return -1;
}
// caller:
const int position = find( firstVector, parameter );
if( position != -1 ) {
    doAction( secondVector[position] );
}

however vector::size() returns size_t which corresponds to an unsigned int type that can't directly store -1. How do I signal that the element is not found in a vector when using size_t instead of int as an index?

Answer 1

Take a look at the answers provided for this question: Invalid value for size_t?. Also you can use std::find_if with std::distance to get the index.

  std::vector<type>::iterator iter = std::find_if(vec.begin(), vec.end(), comparisonFunc);
    size_t index = std::distance(vec.begin(), iter);
    if(index == vec.size())
   {
     //invalid
   }

Answer 2

In this case, it is safe to cast away the unsigned portion unless your vector can get REALLY big.

I would pull out the where.size() to a local variable since it won't change during the call. Something like this:

int find( const vector<type>& where, int searchParameter ){
    int size = static_cast<int>(where.size());
    for( int i = 0; i < size; i++ ) {
       if( conditionMet( where[i], searchParameter ) ) {
           return i;
       }
    }
    return -1;
}

Answer 3

First of all, do you really need to store indices like this? Have you looked into std::map, enabling you to store key => value pairs?

Secondly, if you used iterators instead, you would be able to return std::vector.end() to indicate an invalid result. To convert a vector to an index you simply use

size_t i = it - myvector.begin();

Answer 4

Something like this, I think. find_if_counted.hpp:

#ifndef FIND_IF_COUNTED_HPP
#define FIND_IF_COUNTED_HPP

#include <algorithm>

namespace find_if_counted_impl
{
    template <typename Func>
    struct func_counter
    {
     explicit func_counter(Func& func, unsigned &count) :
     _func(func),
     _count(count)
     {
     }

     template <typename T>
     bool operator()(const T& t)
     {
      ++_count;

      return _func(t);
     }

    private:
     Func& _func;
     unsigned& _count;
    };
}

// generic find_if_counted,
// returns the index of the found element, otherwise returns find_if_not_found
const size_t find_if_not_found = static_cast<size_t>(-1);

template <typename InputIterator, typename Func>
size_t find_if_counted(InputIterator start, InputIterator finish, Func func)
{
    unsigned count = 0;
    find_if_counted_impl::func_counter<Func> f(func, count);

    InputIterator result = find_if(start, finish, f);

    if (result == finish)
    {
     return find_if_not_found;
    }
    else
    {
     return count - 1;
    }
}

#endif

Example:

#include "find_if_counted.hpp"
#include <cstdlib>
#include <iostream>
#include <vector>

typedef std::vector<int> container;

int rand_number(void)
{
    return rand()  % 20;
}

bool is_even(int i)
{
    return i % 2 == 0;
}

int main(void)
{
    container vec1(10);
    container vec2(10);

    std::generate(vec1.begin(), vec1.end(), rand_number);
    std::generate(vec2.begin(), vec2.end(), rand_number);

    unsigned index = find_if_counted(vec1.begin(), vec1.end(), is_even);

    if (index == find_if_not_found)
    {
     std::cout << "vec1 has no even numbers." << std::endl;
    }
    else
    {
     std::cout << "vec1 had an even number at index: " << index <<
      " vec2's corresponding number is: " << vec2[index] << std::endl;
    }
}

Though I feel like I'm doing something silly... :X Any corrections are welcome, of course.

Answer 5

You could use std::numeric_limits<size_t>::max() for elements that was not found. It is a valid value, but it is impossible to create container with such max index. If std::vector has size equal to std::numeric_limits<size_t>::max(), then maximum allowed index will be (std::numeric_limits<size_t>::max()-1), since elements counted from 0.

Answer 6

std::vector has random-access iterators. You can do pointer arithmetic with them. In particular, this my_vec.begin() + my_vec.size() == my_vec.end() always holds. So you could do

const vector<type>::const_iterator pos = std::find_if( firstVector.begin()
                                                     , firstVector.end()
                                                     , some_predicate(parameter) );
if( position != firstVector.end() ) {
    const vector<type>::size_type idx = pos-firstVector.begin();
    doAction( secondVector[idx] );
}

As an alternative, there's always std::numeric_limits<vector<type>::size_type>::max() to be used as an invalid value.

Answer 7

If a vector has N elements, there are N+1 possible answers for find. std::find and std::find_if return an iterator to the found element OR end() if no element is found. To change the code as little as possible, your find function should return the equivalent position:

size_t find( const vector<type>& where, int searchParameter )
{
   for( size_t i = 0; i < where.size(); i++ ) {
       if( conditionMet( where[i], searchParameter ) ) {
           return i;
       }
    }
    return where.size();
}
// caller:
const int position = find( firstVector, parameter );
if( position != secondVector.size() ) {
    doAction( secondVector[position] );
}

I would still use std::find_if, though.