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

问题描述 投票：0回答：1

我想使用 STL 算法简化索引工作（当您有另一个容器的索引数组以加快访问速度时，比如说对索引进行排序）。我想通过索引对数据进行操作，这对程序员来说是透明的。例如，我想使用 std::equal_range 使用索引查找数据中的范围，而不为此编写谓词（该谓词只有两个目的：存储数据容器的 begin() 并为间接提供代码访问）。

我问这个问题是因为我觉得我正在重新发明自行车，STL 应该有一些东西来解决这个任务，比如它有 less、greater、negate 等谓词。我希望有人回答“只需使用谓词” std::indirect_array 和 std::indirect_binary_predicate 以这种方式......”或类似的东西。我更喜欢适用于通常的 std::vector 容器的解决方案。

我想避免什么

如果我需要对索引数据使用 STL 算法（假设我有带有值的数组 data 和带有索引的数组 indexes），该算法使用数据容器 begin() 引用索引数据（假设现在我们使用 std::vector ）和索引（取自索引数组）。

我更喜欢保留索引（而不是指针/迭代器），主要是因为我想减少内存占用。对于 Winx64 平台，每个 int 索引占用 4 个字节，而指针占用 8 个字节。此外，索引的使用简化了数组重定位，适合处理数组结构 (SoA) 和一些其他操作。

在我看来，问题分为两个：

  1. 指标的表示方式
  2. 为算法提供透明度

我真的无法将这两者解耦，如果有人可以，请提供方法。主要原因是，当我问在哪里以及如何存储容器 begin() 时，人们会指出具有内部状态的谓词，这正是问题的第二部分。

当我谈论透明度时，我的意思是我想使用像 std::equal_range 这样的算法来查找值的范围，而不是在索引中，而是使用索引作为入口点。不幸的是， std::equal_range 对我的意图一无所知，只会比较索引。当然，我可以在比较器谓词中处理这个问题，但这将迫使我编写它，并且在每个谓词中记住间接寻址。

节省内存，我必须回报，将容器的 begin() 保留在某处（或提供）。

因此，最有可能的是，我必须将 begin() 传递给算法，而最好的位置是谓词：

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. 我每次都必须提供谓词（即使是简单的间接），因为它是存储对数据向量的引用的唯一位置。
  2. 如果用户忘记添加谓词，错误消息将是致命的（STL 中的数十行错误，很难理解和快速修复）。

关键问题

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

有目标

  1. 稳健性；当用户忘记提供谓词并开始出现大量 STL 错误时，这不起作用；当一些隐式转换（这就是为什么我有 Value 类而不是 int ）可能会破坏间接寻址时，这不起作用，等等。
  2. 可读性并避免代码重复。
  3. 注重性能的内存占用。

我确信在现代 C++/STL 中应该有一些现成的解决方案。

我有几十个索引、几十个谓词和许多间接级别，并且希望简化代码，因为在许多地方它变得复杂，同时虽然不完全相同，但很相似。大部分都是间接代码。

c++ stl
1个回答
0
投票

不完全确定这是否是您所期望的，但通常索引是通过投影实现的，正如 @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) {}
};

template<std::ranges::random_access_range R>
auto indexing(R&& range){
    return std::views::transform([&range](const Index& i){
        return *(std::ranges::begin(range)+i.index);
    });
};

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

    Value value(30);

    //Using projection
    auto range_pred1 = std::ranges::equal_range(i1, value, {}, [&v1](auto&& i){return (*(std::ranges::begin(v1)+i.index));});
    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;

    //Using custom view
    auto indexingView = i1 | indexing(v1);

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

    std::cout << std::endl << "range_pred.second-range_pred.first " << std::distance(range_pred.begin(), range_pred.end()) << std::endl;
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.