在C++中从类似向量的数据结构中删除索引而不复制数据的最佳方法

r7s23pms  于 2023-01-28  发布在  其他
关注(0)|答案(4)|浏览(179)

问题是:
我需要创建一个简单的向量或类似向量的数据结构,它具有索引访问,例如:

arr[0] = 'a';
arr[1] = 'b';
//...
arr[25] = 'z';

从这个结构中,我想删除一些索引,例如索引[5]索引中的实际值不需要从内存中擦除,并且值不应该复制到任何地方,我只需要数据结构的索引在之后重新排列,这样:

arr[0] = 'a';
//...
arr[4] = 'e';
arr[5] = 'g';
//...
arr[24] = 'z';

在这种情况下,std::vector是最好的数据结构吗?我应该如何正确地删除索引而不复制数据?请提供代码。
或者有没有一个更好的数据结构,我可以使用它?
注意,除了通过索引之外,我并不打算以任何其他方式访问数据,并且我不需要在任何时候将数据连续地存储在内存中。

h5qlskok

h5qlskok1#

您想要的内容可能包含在以下内容之一中:
1.针对std::hive提出了哪些建议
Hive是游戏编程界中通常称为“bucket array”容器的形式化、扩展和优化;类似的结构存在于跨越高性能计算、高性能交易、3D仿真、物理模拟、机器人技术、服务器/客户端应用和粒子仿真领域的各种实施例中。

  1. C++23中的std::flat_map
    flat_map是一种关联容器,它支持唯一键(每个键值最多包含一个),并提供基于键的另一类型T的值的快速检索。
h43kikqp

h43kikqp2#

由于您希望更新索引,因此需要一个顺序容器:vector、list、deque或类似的。vector和deque可以复制值,但是list对于几乎所有的目的来说都很慢,所以这些都不适合一开始。
因此,最好的解决方案是std::vector<std::unique_ptr<Item>>,这样你可以获得非常快的访问速度,但是当通过索引删除元素时,实际的元素本身并没有移动,只是指针被重新排列。

ha5z0ras

ha5z0ras3#

矢量数据结构要求其数据在内存中是连续的,因此不可能在不移动内存以填充差距(最后一个元素除外)的情况下删除元素。
向量是一个 sequence 容器,一个具有最小O(1)的元素移除代价的序列容器是一个双向链表(如std::list所实现的),一个链表可以被有效地顺序访问,但与向量不同的是,随机访问的代价是O(n)。
有关各种容器类上的不同操作的时间复杂度的讨论,请参见例如https://dev.to/pratikparvati/c-stl-containers-choose-your-containers-wisely-4lc4
对于不同的操作,每个容器都有不同的性能特征。您需要选择一个最适合您将主要执行的操作的容器。如果顺序访问和元素插入和移除是关键,则列表是合适的。如果随机访问更关键,则在插入/移除不频繁的情况下使用向量可能是值得的。在您的应用程序中,这两种都可能不是最佳的。但对于你问题中所详述的具体情况,链接列表是合适的。

tuwxkamq

tuwxkamq4#

使用基于视图的方法怎么样?
这里我展示了一个使用ranges::any_view的解决方案,答案的底部是完整的工作代码,它显示了我们构建的类似矢量的实体实际上指向原始std::vector的元素。
请注意,我并不是在以任何方式讨论性能问题,一般来说,我并不声称对性能问题了解多少,而且我对与我下面使用的抽象的成本有关的性能问题了解得更少。
该解决方案的核心是用于从输入range仅丢弃一个元素(具有索引i的元素)的函数:

constexpr auto shoot =
    [](std::size_t i, auto&& range)
        -> any_view<char const&, category::random_access> {
    return concat(range | take(i), range | drop(i + 1));
};

具体来说,

  • 给定要从输入range中移除的项的索引i
  • 它通过take对来自range的前i个元素(这些是索引i的元素之前的元素)进行合并来创建范围,
  • 它通过droprange开始第一个i + 1元素(因此保留索引为i的元素之后的元素)来创建范围,
  • 最后concat表示这两个范围
  • 将结果范围作为any_view<char const&, category::random_access>返回,以避免每次重复应用shoot时嵌套越来越多的视图;
  • category::random_access允许基于[]访问元素。

鉴于上述情况,从范围中删除一些元素就像下面这样简单:

auto w = shoot(3, shoot(9, shoot(10, v)));

然而,如果你要调用shoot(9, shoot(3, v)),你将首先移除结果范围的第3个元素,然后是第9个元素,这意味着你已经移除了相对于原始向量的第3个和第10个元素;这与基于范围的方法无关,而只是提供了一个仅删除一个元素的函数。
显然,你可以在此基础上建立一个函数,消除另一个范围内的所有指数:

  • sort要去除的元素的indices
  • for-在reverse中在它们上循环(由于上面解释的原因),
  • shoot(如果不使用any_view,我们就不能执行view = shoot(n, view);,因为shoot的每个应用程序都会更改view的类型):
constexpr auto shoot_many = [](auto&& indices, auto&& range){
    any_view<char const&, category::random_access> view{range};
    sort(indices);
    for (auto const& idx : reverse(indices)) {
        view = shoot(idx, view);
    }
    return view;
};

我尝试过shoot_many的另一种解决方案,基本上是索引range中的所有元素,然后索引filter中包含索引的元素,最后使用transform ing来移除索引。

constexpr auto shoot_many = [](auto&& indices, auto&& range){
    std::set<std::size_t> indices_(indices.begin(), indices.end()); // for easier lookup
                                                                    // (assuming they're not sorted)
    auto indexedRange = zip(range, iota(0)); // I pretty sure there's a view doing this already
    using RandomAccessViewOfChars
        = any_view<char const&, category::random_access>;
    return RandomAccessViewOfChars{
        indexedRange | filter([indices_](auto&& pair){ return indices_.contains(pair.second); })
                     | transform([](auto&& pair){ return pair.first; })};
};

然而,这是行不通的,因为管道中有filter意味着我们直到真正遍历它时才知道结果范围的长度,这反过来又意味着我返回的输出不满足category::random_accessany_view.sad的编译时要求。
总之,here's the solution

#include <assert.h>
#include <cstddef>
#include <functional>
#include <iostream>
#include <memory>
#include <range/v3/algorithm/sort.hpp>
#include <range/v3/range/conversion.hpp>
#include <range/v3/view/any_view.hpp>
#include <range/v3/view/concat.hpp>
#include <range/v3/view/drop.hpp>
#include <range/v3/view/iota.hpp>
#include <range/v3/view/reverse.hpp>
#include <range/v3/view/take.hpp>
#include <set>
#include <vector>

using namespace ranges;
using namespace ranges::views;

// utility to drop one element from a range and give you back a view
constexpr auto shoot =
    [](std::size_t i, auto&& range)
        -> any_view<char const&, category::random_access> {
    return concat(range | take(i), range | drop(i + 1));
};

constexpr auto shoot_many = [](auto&& indices, auto&& range){
    any_view<char const&, category::random_access> view{range};
    sort(indices);
    for (auto const& idx : reverse(indices)) {
        view = shoot(idx, view);
    }
    return view;
};

int main() {
    // this is the input
    std::vector<char> v = iota('a') | take(26) | to_vector;
    // alternavively,   = {'a', 'b', ...)

    // remove a few elements by index
    auto w = shoot_many(std::vector<int>{3, 10, 9}, v);

    for (std::size_t i = 0, j = 0; i != v.size(); ++i, ++j) {
        if (i == 10 || i == 9 || i == 3) {
            --j;
            std::cout << v[i] << ',' << '-' << std::endl;
        } else {
            std::cout << v[i] << ',' << w[j] << std::endl;

            assert( v[i] ==  w[j]);
            assert(&v[i] == &w[j]);
        }
    }
}

相关问题