为索引寻找最接近的真实值

Question

是否有一种优雅的 STL 方法可以true在给定索引的数组中找到最接近的(1) 值。例如，对于给定索引 5std::vector<int> v{1,1,1,0,0,0,1,1,0};的最接近true值位于索引 6。

我尝试并最终使用了多个带有迭代器的 while 循环。是否可以使用 C++ STL？

Answer 1

Here's an idea that you can expand on to cover all your use-cases.

You can use std::find and std::distance to achieve that.

Example (live):

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>

int main()
{
    const std::vector<int> v { 1, 1, 1, 0, 0, 0, 1, 1, 0 };

    const auto it = std::find( std::begin(v) + 5, std::end(v), 1 );
    if ( it == std::end(v) )
    {
        std::cerr << "ERROR: Not found!\n";
        return EXIT_FAILURE;
    }

    const auto index = std::distance( std::begin(v), it );
    std::cout << "SUCCESS: Found at index " << index << '\n';

    return EXIT_SUCCESS;
}

You can wrap your own function with your default (i.e. true) for better readability according to your use-case. Also, look at std::next and std::advance for iterator navigation.

Another example using basic constructs only including some tests (live):

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <limits>

using Result = std::tuple<bool, std::size_t, std::string>; // result (T/F), index, message
Result find_nearest( const std::vector<int>& v, const std::size_t index, const int value )
{
    constexpr auto max_index = std::numeric_limits<std::size_t>::max();

    if ( v.empty() || index >= v.size() )
    {
        return { false, max_index, "Empty container or invalid index!" };
    }

    std::size_t ilhs { max_index };
    std::size_t irhs { max_index };

    for ( std::size_t i {0}; i != v.size(); ++i )
    {
        if ( v[i] == value )
        {
            if ( i < index ) { ilhs = i; }
            else if ( i > index ) { irhs = i; break; }
        }
    }

    // if element not found i.e. no index
    if ( ilhs == max_index && irhs == max_index )
    {
        return { false, max_index, "Index not found!" };
    }

    // shortest distance based comparison to determine indexes
    const auto dlhs = ( ilhs != max_index ? index - ilhs : ilhs );
    const auto drhs = ( irhs != max_index ? irhs - index : irhs );
    if ( dlhs == drhs )
    {
        return { true, ilhs, "Equal distance found! Left index returned!" };
    }

    const auto idx = ( dlhs < drhs ? ilhs : irhs );
    return { true, idx, "Index found!" };
}

int main()
{
    using Args  = std::tuple<std::vector<int>, std::size_t, int>; // list, index, value
    using Tests = std::vector<Args>;

    const Tests tests
    {
        { {}, 0, 1 },
        { { 1 }, 0, 1  },
        { { 1 }, 1, 1  },
        { { 1 }, 2, 1  },
        { { 0, 0, 0 }, 1, 1 },
        { { 0, 0, 0, 1, 0 }, 2, 1 },
        { { 1, 0, 0, 0, 1 }, 2, 1 },
        { { 1, 0, 0, 1, 0, 1, 0 }, 3, 1 },
        { { 1, 0, 0, 0, 1, 0, 0, 0, 1 }, 5, 1 },
    };

    for ( const auto& [list, index, value] : tests )
    {
        const auto& [found, idx, msg] = find_nearest( list, index, value );
        if ( found )
            std::cout << "INF: " << msg << " index: " << idx << '\n';
        else
            std::cerr << "ERR: " << msg << '\n';
    }

    return 0;
}

Output:

ERR: Empty container or invalid index!
ERR: Index not found!
ERR: Empty container or invalid index!
ERR: Empty container or invalid index!
ERR: Index not found!
INF: Index found! index: 3
INF: Equal distance found! Left index returned! index: 0
INF: Index found! index: 5
INF: Index found! index: 4