问题是:
我需要创建一个简单的向量或类似向量的数据结构,它具有索引访问,例如:
arr[0] = 'a';
arr[1] = 'b';
//...
arr[25] = 'z';
从这个结构中,我想删除一些索引,例如索引[5]
索引中的实际值不需要从内存中擦除,并且值不应该复制到任何地方,我只需要数据结构的索引在之后重新排列,这样:
arr[0] = 'a';
//...
arr[4] = 'e';
arr[5] = 'g';
//...
arr[24] = 'z';
在这种情况下,std::vector是最好的数据结构吗?我应该如何正确地删除索引而不复制数据?请提供代码。
或者有没有一个更好的数据结构,我可以使用它?
注意,除了通过索引之外,我并不打算以任何其他方式访问数据,并且我不需要在任何时候将数据连续地存储在内存中。
4条答案
按热度按时间h5qlskok1#
您想要的内容可能包含在以下内容之一中:
1.针对
std::hive
提出了哪些建议Hive是游戏编程界中通常称为“bucket array”容器的形式化、扩展和优化;类似的结构存在于跨越高性能计算、高性能交易、3D仿真、物理模拟、机器人技术、服务器/客户端应用和粒子仿真领域的各种实施例中。
std::flat_map
flat_map是一种关联容器,它支持唯一键(每个键值最多包含一个),并提供基于键的另一类型T的值的快速检索。
h43kikqp2#
由于您希望更新索引,因此需要一个顺序容器:vector、list、deque或类似的。vector和deque可以复制值,但是list对于几乎所有的目的来说都很慢,所以这些都不适合一开始。
因此,最好的解决方案是
std::vector<std::unique_ptr<Item>>
,这样你可以获得非常快的访问速度,但是当通过索引删除元素时,实际的元素本身并没有移动,只是指针被重新排列。ha5z0ras3#
矢量数据结构要求其数据在内存中是连续的,因此不可能在不移动内存以填充差距(最后一个元素除外)的情况下删除元素。
向量是一个 sequence 容器,一个具有最小O(1)的元素移除代价的序列容器是一个双向链表(如
std::list
所实现的),一个链表可以被有效地顺序访问,但与向量不同的是,随机访问的代价是O(n)。有关各种容器类上的不同操作的时间复杂度的讨论,请参见例如https://dev.to/pratikparvati/c-stl-containers-choose-your-containers-wisely-4lc4
对于不同的操作,每个容器都有不同的性能特征。您需要选择一个最适合您将主要执行的操作的容器。如果顺序访问和元素插入和移除是关键,则列表是合适的。如果随机访问更关键,则在插入/移除不频繁的情况下使用向量可能是值得的。在您的应用程序中,这两种都可能不是最佳的。但对于你问题中所详述的具体情况,链接列表是合适的。
tuwxkamq4#
使用基于视图的方法怎么样?
这里我展示了一个使用
ranges::any_view
的解决方案,答案的底部是完整的工作代码,它显示了我们构建的类似矢量的实体实际上指向原始std::vector
的元素。请注意,我并不是在以任何方式讨论性能问题,一般来说,我并不声称对性能问题了解多少,而且我对与我下面使用的抽象的成本有关的性能问题了解得更少。
该解决方案的核心是用于从输入
range
仅丢弃一个元素(具有索引i
的元素)的函数:具体来说,
range
中移除的项的索引i
,take
对来自range
的前i
个元素(这些是索引i
的元素之前的元素)进行合并来创建范围,drop
从range
开始第一个i + 1
元素(因此保留索引为i
的元素之后的元素)来创建范围,concat
表示这两个范围any_view<char const&, category::random_access>
返回,以避免每次重复应用shoot
时嵌套越来越多的视图;category::random_access
允许基于[]
访问元素。鉴于上述情况,从范围中删除一些元素就像下面这样简单:
然而,如果你要调用
shoot(9, shoot(3, v))
,你将首先移除结果范围的第3个元素,然后是第9个元素,这意味着你已经移除了相对于原始向量的第3个和第10个元素;这与基于范围的方法无关,而只是提供了一个仅删除一个元素的函数。显然,你可以在此基础上建立一个函数,消除另一个范围内的所有指数:
sort
要去除的元素的indices
,for
-在reverse
中在它们上循环(由于上面解释的原因),shoot
(如果不使用any_view
,我们就不能执行view = shoot(n, view);
,因为shoot
的每个应用程序都会更改view
的类型):我尝试过
shoot_many
的另一种解决方案,基本上是索引range
中的所有元素,然后索引filter
中包含索引的元素,最后使用transform
ing来移除索引。然而,这是行不通的,因为管道中有
filter
意味着我们直到真正遍历它时才知道结果范围的长度,这反过来又意味着我返回的输出不满足category::random_access
any_view
.sad的编译时要求。总之,here's the solution: