std::find and std::find_if

If we are looking for an element in a sequence, not knowing much on the sequence itself beside the fact that it could contain a specific value, we will probably use for our job find() or find_if(), both included as algorithm in the C++ STL.

The Google Text fixture I use to make some examples on these algorithm is based on this class:

class FindTest : public ::testing::Test
{
protected:
   FindTest()
   {
      vi_.reserve(10);
      for(int i = 1; i <= 10; ++i)
         vi_.push_back(i*i);
   }

   std::vector<int> vi_;
};

As you can see, we have a vector containing the first 10 natural square numbers (zero excluded).

Find - Negative test.

The find algorithm scans all the items in the passed sequence comparing them with the value passed as third parameter. If successful, it returns the iterator to the found item, otherwise it return the right delimiter of the interval.

Let's if find() works like expected when looking for a value it is not in the sequence:

TEST_F(FindTest, CantFind)
{
   auto it = std::find(vi_.begin(), vi_.end(), 42);

   EXPECT_TRUE(it == vi_.end());
}

Notice that I use the C++11 keyword "auto" for saving a bit of typing. If your compiler does not support it yet, you should tell it the exact type, std::vector<int>::iterator, an iterator to a vector of int. Since the compiler could deduce that without our help, it's nice to let it doing the job.

Find - Positive test.

Easy enough. If we pass to find() a square number below or equals to 100, we expect it to find it:

TEST_F(FindTest, Find)
{
   auto it = std::find(vi_.begin(), vi_.end(), 64);

   ASSERT_TRUE(it != vi_.end());
   EXPECT_EQ(*it, 64);
}

From the point of view of the Google Test user, this code is (mildly) interesting because it shows the use of an ASSERT macro. Since we don't want to dereference the iterator in case we actually find that it is an invalid one, we assert that it should be different from end() on the vector.

Find If - Function.

If we want to find the first element in a sequence of integers that has 5 as divisor, we could create a function that checks its parameter for that, and use it as third parameter in a find_if() call:

bool five(int i) { return i%5 == 0; }

TEST_F(FindTest, FindIfFunction)
{
   auto it = std::find_if(vi_.begin(), vi_.end(), five);

   ASSERT_TRUE(it != vi_.end());
   EXPECT_EQ(*it, 25);
}

Find If - Functor.

If we are looking for a more generic solution, a functor could be a solution. Here we use Divisor, a functor that check if the passed value has as factor (aka divisor) the number we passed to its ctor:

class Divisor
{
private:
   int mod_;
public:
   Divisor(int mod) : mod_(mod) {}
   bool operator()(int i){ return i % mod_ == 0; }
};

TEST_F(FindTest, FindIfFunctor)
{
   auto it = std::find_if(vi_.begin(), vi_.end(), Divisor(5));

   ASSERT_TRUE(it != vi_.end());
   EXPECT_EQ(*it, 25);
}

Find If - Reusing standard functors by adaptors.

Instead of creating a new class, it is better checking in the libraries at hand if there is anything we could reuse. In this specific case, we could think of using the modulus<> functor. That could be a good idea, but we should take care of the fact that find_if() expects a functor accepting one parameter, and not two, as modulus<>. This is not an issue, since we could wrap it with bind2nd, passing 5 as second parameter. Still, that is not all, because we need to reverse the result: our number has five as divisor if it is zero modulus five. This is not a problem too. We just apply the unary negator not1 to the result:

TEST_F(FindTest, FindFiveMod)
{
   const int mod = 5;
   auto it = std::find_if(vi_.begin(), vi_.end(),
   std::not1(std::bind2nd(std::modulus<int>(), mod)));

   ASSERT_TRUE(it != vi_.end());
   EXPECT_EQ(*it % mod, 0);
}

Find If - Lambda.

The previous example was cool, but probably a bit too complex for such an easy task as the one we are dealing with. We can get a more readable code using a lambda function (if this C++11 feature has already reached your compiler):

TEST_F(FindTest, FindFiveLambda)
{
   const int mod = 5;
   auto it = std::find_if(vi_.begin(), vi_.end(), [mod](int i)
   {
      return i % mod == 0;
   });

   ASSERT_TRUE(it != vi_.end());
   EXPECT_EQ(*it % mod, 0);
}