C++ 中 STL 算法的透明索引

不完全确定这是否是你所期望的，但通常索引是通过投影实现的，正如@Jarod42在对这个问题的评论中指出的那样。您还可以使用自定义视图。下面显示了这两种方法，其中显示了两个密切相关的变体，用于自定义视图方法。

#include <vector>
#include <concepts>
#include <ranges>
#include <algorithm>
#include <iostream>

struct Value {
    int data;
public:
    Value(int value) : data(value) {}
    operator int() const { return data; }

    bool operator < (const Value& rhs) const { return data < int(rhs); }
};

struct Index {
public:
    int index;
public:
    Index(int i) : index(i) {}
};

// Reusable generic for the standard approach using projections
// Added following @Jarod42's comment on this answer
template<std::ranges::random_access_range R>
auto create_index_projection(R&& range) { 
    return [&range](const Index& i){
        return std::ranges::begin(range)[i.index]; 
    }; 
}

// Reusable generic for the custom view approach
template<std::ranges::random_access_range R>
auto indexing(R&& range){
    return std::views::transform([&range](const Index& i) -> decltype(auto) {
        return std::ranges::begin(range)[i.index];
    });
};

// Variant of the custom view approach, with the operands swapped
// Requires more work, but the order may be more "natural" and easier for composition
template<std::ranges::random_access_range I>
requires std::same_as<std::ranges::range_value_t<I>, Index>
struct IndexObject {
    I&& indices;
    explicit IndexObject(I&& indices_):indices{std::forward<I>(indices_)}{}
};

template <typename I>
IndexObject<I> indexedby(I&& indices_){
    return IndexObject<I>{std::forward<I>(indices_)};
}

template <std::ranges::random_access_range R, std::ranges::random_access_range I>
auto operator | (R&& range, IndexObject<I> index_obj){
    return std::forward<I>(index_obj.indices) | indexing(std::forward<R>(range));
}

int main()
{
    std::vector<Value> v1 = { 0,30,20,40,10 };
    std::vector<Index> i1 = { 0,4,2,1,3 };

    Value value(30);

    //Standard approach: Using projection
    auto range_pred1 = std::ranges::equal_range(i1, value, {}, create_index_projection(v1));
    std::cout << "*range_pred.first = " << v1[(*range_pred1.begin()).index].data << std::endl;
    std::cout << "*range_pred.second= " << v1[(*range_pred1.end()).index].data << std::endl;

    std::cout << std::endl << "range_pred.second-range_pred.first " << std::distance(range_pred1.begin(), range_pred1.end()) << std::endl;

    //Alternatve approach: Using custom view
    //May be the syntax you are looking for
    auto indexing_view = i1 | indexing(v1);

    auto range_pred2 = std::ranges::equal_range(indexing_view, value);
    std::cout << "*range_pred.first = " << (*range_pred2.begin()).data << std::endl;
    std::cout << "*range_pred.second= " << (*range_pred2.end()).data << std::endl;

    std::cout << std::endl << "range_pred.second-range_pred.first " << std::distance(range_pred2.begin(), range_pred2.end()) << std::endl;

    //Variant of above, with more "natural" order in syntax
    auto indexing_view2 = v1 | indexedby(i1);

    auto range_pred3 = std::ranges::equal_range(indexing_view2, value);
    std::cout << "*range_pred.first = " << (*range_pred3.begin()).data << std::endl;
    std::cout << "*range_pred.second= " << (*range_pred3.end()).data << std::endl;

    std::cout << std::endl << "range_pred.second-range_pred.first " << std::distance(range_pred3.begin(), range_pred3.end()) << std::endl;

    //Also works for rvalues provided that std::ranges::dangling is not returned by the algorithm
    bool binary_search_result1 = std::ranges::binary_search(std::vector<Value>{0,20,10}|indexedby(std::vector<Index>{0,2,1}), Value{10});
    bool binary_search_result2 = std::ranges::binary_search(std::vector<Value>{0,20,10}|indexedby(std::vector<Index>{0,2,1}), Value{15});
    std::cout << std::boolalpha;
    std::cout << std::endl << "binary search for 10 " << binary_search_result1 << std::endl;
    std::cout << "binary search for 15 " << binary_search_result2 << std::endl;
}

演示：https://godbolt.org/z/389Y99Mnz

适配器 和 旨在进行重复数据删除。您只需要定义一次，然后使用任一 or 来获取几乎可以用作重新排序范围的视图。只需定义两个变体中的一个，因此您可以选择您认为最自然的语法。这解决了您问题中的透明要求。因此，假设您有以下几点indexingindexedbyindex_range | indexing(indexed_range)indexed_range | indexedby(index_range)

std::string s="abc";
std::array<Index> indices[]{1,2,0};
auto sView = s | indexedby(indices);
//Or, equivalently
//auto sView = indices | indexing(s);

请注意，现在和上面的类型完全不同，但具有相同定义的适配器可以用作包含“bca”的随机访问范围。它是随机访问，因为基础范围也是如此。例如，这意味着并执行您期望它们执行的操作（尽管后者实际上并不需要随机访问范围），这对于大多数应用程序来说已经足够了。indicesssViewindicessView[2]=='a'for(const auto c: sView){...}

它也是可组合的。因此，例如，如果除了 和 之外，还有另一个使用索引向量的间接级别，那么您可以只使用视图来透明地访问元素。由于重载必须是成员函数的限制，因此不可能使用类似语法。i2i1v1auto view = v1 | indexedby(i1) | indexedby(i2)[]v1[indexedby(i1)][indexedby(i2)]

关于模板定义的更多解释：它是一个薄包装器（在大多数 C++ 实现中，额外的成本是单个指针的内存），范围（例如 在您的示例中），实际上只是 函数的一个更具描述性的名称，它可以像 is to 一样被调用。IndexObjectIndexstd::vector<Index>indexedbymakeIndexObjectmakeIndexObjectmake_pairstd::pair

现在，这个围绕原始范围的薄包装器可确保为语法选择正确的运算符。它本来可以只是通过更改 的签名，但我认为这太容易出错并且不能很好地传达意图，所以我选择制作这个额外的包装器。Index|v1 | indexedby(i1)v1 | i1operator|

所以用一句话来概括它的目的：它是包装（捕获）现有的范围，使语法成为可能。在实现许多范围适配器的相应算子时，这称为闭包。Indexv1 | indexedby(i1)|

对于“工作原理”部分。上面已经介绍了大部分信息，但我可以用与自然程序流程相对应的方式重新表述它。

1. indexedby包装（捕获）范围 ，这是一个 .IndexIndexObject
2. 捕获与要检查的范围相结合，返回随机访问 。std::transform_view
3. 然后可以使用透明地访问。std::transform_view

从概念上讲，它与 没有太大区别。(Capture(i1))(v1) -> std::transform_view<decltype(i1), F>

在这一点上，完全摆脱类可能很诱人，因为最初的意图是防止将索引向量误用为值向量。事实上，就类型安全而言，这样做是完全安全的。原因如下。ValueIndex

对于适配器，由于构造函数无法将范围转换为 an，并且 an 本身不是有效的范围，因此现在很清楚，对于值，您必须使用实数范围，而对于索引，您必须使用 .它们不可能混淆在类型系统中。同样，对于适配器，对于值，您必须使用范围适配器，对于索引，您必须使用实际范围，当然，标准库不允许它们之间的隐式转换。indexedbyIndexObjectexplicitIndexObjectIndexObjectindexing

此演示中的以下代码片段清楚地显示了类型安全。有关演示中涉及的类型的定义，请参阅演示本身的链接。该演示改编自 OP 提供的另一个演示。

namespace TypeSafetyDemo{
    namespace Approach1{
        using Value = ValueObject<std::vector<int>&>;
        using Index = std::vector<int>;
        using F = void(*)(Value, Index);
        static_assert(std::invocable<F, Value, Index>);
        static_assert(!std::invocable<F, Value, Value>);
        static_assert(!std::invocable<F, Index, Value>);
        static_assert(!std::invocable<F, Index, Index>);
    }
    namespace Approach2{
        using Value = std::vector<int>;
        using Index = IndexObject<std::vector<int>&>;
        using F = void(*)(Value, Index);
        static_assert(std::invocable<F, Value, Index>);
        static_assert(!std::invocable<F, Value, Value>);
        static_assert(!std::invocable<F, Index, Value>);
        static_assert(!std::invocable<F, Index, Index>);
    }
}

另外需要注意的是，由于两个适配器都通过引用捕获基础范围，因此通常的生存期警告和引用成员适用。不要将一个东西存放在某个地方，并在结束的生命周期后使用它。出于类似的原因，拥有函数签名 是危险的，而且不是很有用，因为在第一次使用 时，底层将被移动到 ，而后续使用 的 将是无效的。我还修改了模板，使其格式不正确，以防止与此类似的误用。indexedby(i1)i1f(std::vector<int>, IndexObject<std::vector<int>&&> index_obj)vectorowning_viewindex_objindex_objIndexObjectIndexObject<std::vector<int>>

如果您真的想变得有用且安全，这里提供了另一种选择。只有当它和它本身都是右值时，它才会移动底层。f(std::vector<int>, IndexObject<std::vector<int>&&>)vectorvectorIndexObject

关于现已删除的评论中的建议：with 不保证格式正确。事实上，这个概念并没有说太多关于它本身的成员函数，而只是关于它的迭代器。因此，为了足够通用，仍然有必要使用.尽管标准库中的所有随机访问范围都提供了 .R rangerandom_access_range Rrange[i.index]Rstd::ranges::begin(range)[i.index]operator[]