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

7vux5j2d  于 12个月前  发布在  其他
关注(0)|答案(1)|浏览(78)

我想使用STL算法简化索引的工作。具体来说，我有一个按顺序指向另一个容器的索引数组，以便索引相对于另一个容器中的相应值进行排序。
我想通过索引对程序员透明地处理数据。例如，我想使用std::equal_range来使用索引查找数据中的一个范围，而不需要为此编写 predicate 。 predicate 只有两个目的：存储数据容器的begin()和提供间接访问的代码。
我觉得我是在重新发明自行车，STL应该有一些东西来解决这个任务，比如它有std::less，std::greater，std::negate等的 predicate 。我希望有人回答“就这样使用 predicate std::indirect_array和std::indirect_binary_predicate”或类似的东西。我更喜欢与通常的std::vector容器一起工作的解决方案。

我想要避免的

如果我需要在索引数据上使用STL算法，例如一个数组 data 和一个数组 indexes，该算法使用数据容器begin()和索引引用索引数据。
我更喜欢保留索引而不是指针/迭代器，主要是因为我想减少内存占用。对于Winx 64平台，每个int索引需要4个字节，而指针需要8个字节。此外，索引的使用简化了数组的重定位，适合处理数组结构（SoA）和其他一些操作。
问题可分为两个：
1.索引的表示
1.为算法提供一致性
我真的不能解耦这两个，如果有人可以，请提供方法。主要原因是，当我问在哪里以及如何存储容器begin()时，人们会指出带有内部状态的 predicate ，这正是问题的第二部分。
当我谈到透明度时，我的意思是我想使用像std::equal_range这样的算法来查找值中的范围，而不是索引中的范围，而是使用索引作为入口点。不幸的是，std::equal_range不知道我的意图，只会比较索引。当然，我可以在比较器 predicate 中处理这个问题，但这将迫使我在每个 predicate 中编写它，记住间接性。
节省内存，我必须偿还，保持某处或提供容器的begin().
所以，最有可能的是，我必须将begin()传递到算法的某个地方，最好的地方是 predicate ：

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) {}
};

class Comparator {
    const std::vector<Value>& vec;
public:
    Comparator(const std::vector<Value>& vec) : vec(vec) {}

    bool operator () (const Value& lhs, const Index& rhs) const {
        return lhs < vec[rhs.index];
    }
    bool operator () (const Index& lhs, const Value& rhs) const {
        return vec[lhs.index] < rhs;
    }
};

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

    Value value(30);

    auto range_pred = std::equal_range(i1.begin(), i1.end(), value, Comparator(v1));

    std::cout << std::endl << "With predicate:" << std::endl;
    std::cout << "*range_pred.first = " << v1[(*range_pred.first).index] << std::endl;
    std::cout << "*range_pred.second= " << v1[(*range_pred.second).index] << std::endl;

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

字符串
关键问题是：
1.我每次都必须提供 predicate ，即使是简单的间接寻址，因为它是存储对数据向量的引用的唯一位置。
1.如果用户忘记添加 predicate ，错误消息将是致命的。

关键问题

1.这在现代C++中可以做得更简单吗？
1.存储容器begin()的最佳位置是哪里？带状态的 predicate 是最佳解决方案吗？
1.如何使其透明化，以便开发人员使用类似std::indirect（虚构）的东西可以永远忘记这一点，并像使用值一样使用索引。

目标明确

1.耐用性：当用户可能忘记提供 predicate 并开始获得大量STL错误时，这不起作用;当一些隐式转换可能破坏间接时，这不起作用，等等。
1.可读性和避免代码重复。
1.注重性能的内存占用。
我相信在现代C++/STL应该是一些现成的解决方案。
我有几十个索引，几十个 predicate 和许多层次的间接，并希望简化代码，因为在许多地方，它变得复杂，同时，类似，虽然不完全相同。

c++

1条答案

按热度按时间
92dk7w1h

92dk7w1h1#

不完全确定这是否是您所期望的，但通常索引是通过投影实现的，正如@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
适配器indexing和indexedby是针对代码重复得，只需要定义一次。然后使用index_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);

型
请注意，现在indices和s的类型与上面的完全不同，但是具有相同的适配器定义，sView可以用作包含“bca”的随机访问范围。它是随机访问，因为底层范围indices也是如此。这意味着，例如sView[2]=='a'和for(const auto c: sView){...}执行您期望它们执行的操作（虽然后者实际上并不需要随机接入范围），这对于大多数应用来说已经足够好了。
它也是可组合的。例如，如果你有另一个使用索引向量i2的间接层，除了i1和v1之外，那么你可以只使用视图auto view = v1 | indexedby(i1) | indexedby(i2)来透明地访问元素。由于重载的[]必须是成员函数的限制，像v1[indexedby(i1)][indexedby(i2)]这样的语法是不可能的。
关于IndexObject模板定义的更多说明：它是一个薄 Package （大多数C++实现中的额外开销是单个指针的内存）（例如，示例中的std::vector<Index>），而indexedby实际上只是IndexObject的make函数的一个更具描述性的名称，它可以被称为makeIndexObject，就像make_pair到std::pair一样。
现在，这个围绕Index的原始范围的瘦 Package 器确保为语法v1 | indexedby(i1)选择了正确的运算符|。它本来可以只是v1 | i1，只需更改operator|的签名即可，但我认为这太容易出错，并且不能很好地传达意图。所以我选择做这个额外的 Package 。
所以用一句话来概括它的目的：它是 Package （捕获）Index的一个现有范围，使语法v1 | indexedby(i1)成为可能，在许多范围适配器的相应操作符|的实现中，这被称为闭包。
对于“它是如何工作的”部分。大部分信息已经在上面呈现了，但我可以用一种与自然程序流相对应的方式重新表述它。

  1. indexedby包含（捕获）Index的一个范围，即IndexObject。
    1.捕获与要检查的范围相结合，这将返回一个随机访问std::transform_view。
  2. std::transform_view可用于透明访问。“
    从概念上讲，它与(Capture(i1))(v1) -> std::transform_view<decltype(i1), F>没有太大的不同。
    在这一点上，完全删除Value和Index类是很有诱惑力的，因为最初的目的是防止将索引向量误用为值向量。这样做实际上在类型安全方面是完全安全的。原因如下。
    对于indexedby适配器，由于explicit构造函数无法将范围转换为IndexObject，并且IndexObject本身不是有效的范围，现在很清楚，对于值，必须使用真实的范围，对于索引，必须使用IndexObject。对于indexing适配器，对于值，必须使用范围适配器，对于索引，必须使用真实的范围，当然，标准库不允许在它们之间进行隐式转换。
    下面的this demo代码片段清楚地显示了类型安全性。有关演示中涉及的类型的定义，请参阅演示本身的链接。该演示改编自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)存储在某个地方，并在i1的生存期结束后使用它。出于类似的原因，具有f(std::vector<int>, IndexObject<std::vector<int>&&> index_obj)的函数签名是危险的，并且不是很有用。因为在第一次使用index_obj时，底层的vector将被移到owning_view，随后使用index_obj将无效。我还修改了模板IndexObject，使IndexObject<std::vector<int>>的格式不正确，以防止类似的误用。
如果你真的想让f(std::vector<int>, IndexObject<std::vector<int>&&>)变得有用和安全，here提供了一个替代方案，它只在vector和IndexObject本身都是右值的情况下才移动底层的vector。

关于已删除评论中的建议：R range与random_access_range R的组合并不能保证range[i.index]是格式良好的。事实上，这个概念并没有对R本身的成员函数做太多的说明，因此，为了足够通用，仍有必要使用std::ranges::begin(range)[i.index]。尽管标准库中的所有随机访问范围都请提供operator[]。

赞(0）分享  回复(0）举报  12个月前
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com