How to find a specific element of a value in a vector?

[possum swallower]

If I have 2 values being added multiple times to a vector like this :

	int one = 1, four = 4;
	std::vector<int> numbers{ one,one, one, four,four , one, four};

see how I have three "four" values added into the vector , how could I find the second to last four inside the vector? I'd assume I could find it by finding it's index like

numbers[four].at(4)

but that does not work.

[jonnin]

.at is the same as [] except it has an extra safety check that makes it slower. If for some weird reason (there are designs like a hash function where it could make sense) you don't know that your index is safe to use, .at is your answer for that.

.find can be called repeatedly, using the last found location as a new starting point to look for the next one until you find the one you want.
or you can just do it yourself in a for loop. the find logic isnt any cleaner for this task.
Find would work better here in reverse... there is a reversed find (rfind I think).

[Ganado]

There is probably some <algorithm> you can leverage, but let's just do the cheap and dirty way with a good old for loop:

// Example program
#include <iostream>
#include <vector>
using std::cout;

// returns index of the second-to-last instance of the given number_to_find
// returns -1 if there are not at least two instances of the number_to_find
int index_of_second_to_last(const std::vector<int>& numbers, int number_to_find)
{
    int count = 0;

    for (int i = (int)numbers.size() - 1; i >= 0; i--)
    {
        if (numbers[i] == number_to_find)
        {
            count++;
            if (count == 2)
            {
                return i;   
            }
        }
    }
    
    return -1;
}

void test_equals(int actual_value, int expected_value)
{
    if (actual_value == expected_value)
    {
        cout << "Passed\n";
    }
    else
    {
        cout << "Failed\n";   
    }
}

int main()
{
    // Tests
    {
	    std::vector<int> numbers { 1, 1, 1, 4, 4, 1, 4 };	
	    test_equals(index_of_second_to_last(numbers, 4), 4);
    }
    {
	    std::vector<int> numbers { };	
	    test_equals(index_of_second_to_last(numbers, 4), -1);
    }
    {
	    std::vector<int> numbers { 42 };	
	    test_equals(index_of_second_to_last(numbers, 42), -1);
    }
    {
	    std::vector<int> numbers { 1, 2, 3, 4 };	
	    test_equals(index_of_second_to_last(numbers, 4), -1);
    }
    {
	    std::vector<int> numbers { 4, 4 };	
	    test_equals(index_of_second_to_last(numbers, 4), 0);
    }
}

Edit: +1 to jonnin's idea of a 2x std::find with reverse iterators. Although, honestly, using a for loop might just be easier.

// Example program
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using std::cout;

// returns index of the second-to-last instance of the given number_to_find
// returns -1 if there are not at least two instances of the number_to_find
int index_of_second_to_last(const std::vector<int>& numbers, int number_to_find)
{
    auto first_it = std::find(numbers.rbegin(), numbers.rend(), number_to_find);
    auto second_it = std::find(std::next(first_it), numbers.rend(), number_to_find); // WARNING: bug. See later post in thread.
    
    // this is a reverse iterator, so it's the distance from the last element
    int distance = second_it - numbers.rbegin();
    if (distance == 0)
    {
        return -1;   
    }
    else
    {
        return (int)numbers.size() - distance - 1;
    }
}

void test_equals(int actual_value, int expected_value)
{
    if (actual_value == expected_value)
    {
        cout << "Passed\n";
    }
    else
    {
        cout << "Failed\n";   
    }
}

int main()
{
    // Tests
    {
	    std::vector<int> numbers { 1, 1, 1, 4, 4, 1, 4 };	
	    test_equals(index_of_second_to_last(numbers, 4), 4);
    }
    {
	    std::vector<int> numbers { 4, 4, 1, 1, 0, 0, 1, 0 };	
	    test_equals(index_of_second_to_last(numbers, 4), 0);
    }
    {
	    std::vector<int> numbers { 1, 1, 1, 4, 4, 1, 4, 1 };	
	    test_equals(index_of_second_to_last(numbers, 4), 4);
    }
    {
	    std::vector<int> numbers { };	
	    test_equals(index_of_second_to_last(numbers, 4), -1);
    }
    {
	    std::vector<int> numbers { 42 };	
	    test_equals(index_of_second_to_last(numbers, 42), -1);
    }
    {
	    std::vector<int> numbers { 1, 2, 3, 4 };	
	    test_equals(index_of_second_to_last(numbers, 4), -1);
    }
    {
	    std::vector<int> numbers { 4, 4 };	
	    test_equals(index_of_second_to_last(numbers, 4), 0);
    }
}

[seeplus]

There seems to be an issue with test 4. I get a run-time exception with VS2019.

This works for all the tests with VS2019:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using std::cout;

// returns index of the second-to-last instance of the given number_to_find
// returns -1 if there are not at least two instances of the number_to_find
template <typename T>
int index_of_second_to_last(const std::vector<T>& numbers, T number_to_find)
{
	if (const auto first_it {std::find(numbers.crbegin(), numbers.crend(), number_to_find)}; first_it != numbers.crend())
		if (const auto second_it {std::find(std::next(first_it), numbers.crend(), number_to_find)}; second_it != numbers.crend())
			return static_cast<int>(std::distance(numbers.cbegin(), second_it.base()) - 1);

	return -1;
}

void test_equals(int actual_value, int expected_value)
{
	cout << (actual_value == expected_value ? "Passed" : "Failed") << '\n';
}

int main()
{
	// Tests
	{
		const std::vector numbers {1, 1, 1, 4, 4, 1, 4};
		test_equals(index_of_second_to_last(numbers, 4), 4);
	}
	{
		const std::vector numbers {4, 4, 1, 1, 0, 0, 1, 0};
		test_equals(index_of_second_to_last(numbers, 4), 0);
	}
	{
		const std::vector numbers {1, 1, 1, 4, 4, 1, 4, 1};
		test_equals(index_of_second_to_last(numbers, 4), 4);
	}
	{
		const std::vector<int> numbers { };
		test_equals(index_of_second_to_last(numbers, 4), -1);
	}
	{
		const std::vector numbers {42};
		test_equals(index_of_second_to_last(numbers, 42), -1);
	}
	{
		const std::vector numbers {1, 2, 3, 4};
		test_equals(index_of_second_to_last(numbers, 4), -1);
	}
	{
		const std::vector numbers {4, 4};
		test_equals(index_of_second_to_last(numbers, 4), 0);
	}
}

Passed
Passed
Passed
Passed
Passed
Passed
Passed

[Ganado]

Thanks, it was because I was calling std::next on the rend iterator.
Quick fix for my second code is:

    auto first_it = std::find(numbers.rbegin(), numbers.rend(), number_to_find);
    if (first_it == numbers.rend())
    {
        return -1;
    }

[possum swallower]

Thanks guys.

[mbozzi]

You could use find_if with a stateful predicate:

#include <algorithm>
#include <iterator>
#include <iostream>

int main()
{
  int xs[] = { 1, 2, 7, 8, 123, 4, 4, 8, 5, 4, 2, 10 }; 
  int number_to_find = 4;
  int nth = 3;

  auto const iter = std::find_if(std::begin(xs), std::end(xs), 
    [=](auto x) mutable { return (number_to_find == x && --nth == 0); });
    
  // *iter is the second 4 
  std::cout << "occurrence number " << nth << " of the value " << number_to_find 
            << " is located at index " << std::distance(std::begin(xs), iter) 
            << " in the array\n";  
}

[Ganado]

That solves a different problem than the original one, assuming the original problem is "finding the [nth] to last [number]".

[mbozzi]

Okay, to fix it you have to use std::rbegin and std::rend instead.

#include <algorithm>
#include <iterator>
#include <iostream>

int main()
{
  int xs[] = { 1, 2, 7, 8, 123, 4, 4, 8, 5, 4, 2, 10 }; 
  int number_to_find = 4;
  int nth = 2;

  auto const iter = std::find_if(std::rbegin(xs), std::rend(xs), 
    [=](auto x) mutable { return (number_to_find == x && --nth == 0); });
    
  std::cout << "The nth-to-last occurence of the value " << number_to_find 
            << " (where n = " << nth << ") is located at index " 
            << std::size(xs) - std::distance(std::rbegin(xs), iter) - 1
            << " in the array\n";  
}