如何用只允许 array.add(int) 的语言模拟 array.remove(int)

Question

我正在尝试用一种奇特的编程语言实现一种算法，该算法要求我从一维数组中删除一个元素，但该语言没有删除索引 i 处的元素 x 的方法。

这些方法可用于array.[method]() :

add(x) --- 压入 x 并调整长度 + 1
resize(x) --- 新长度 = x
count() --- returns数组的长度

有没有一种方法可以使用原始数据类型、基本控制流和变量来编写自己的数组方法或删除方法？

我考虑过使用包含保留项和丢弃项的数组以及布尔值数组来表示 include == true/false。数组将共享相同的索引，但我不确定这是否是计算上最有效的方法。

Answer 1

如果您不需要保留顺序：

indexToRemove = 3 ;
lastIndex = array.count()-1 ;
array.fill ( indexToRemove , indexToRemove-1 , array[lastIndex] , 0 ) ;
array.resize ( lastIndex ) ;

如果你这样做，你有几个选择：

多次执行以上操作以将所有内容移动过来。
创建一个新数组，其中包含要删除的索引和末尾之间的所有内容，然后调整数组大小，然后将所有其他元素添加回去。
创建一个包含所有内容的新数组，然后分配旧数组。

但一个更根本的问题是为什么这种语言没有删除功能。您用这种语言所做的任何事情的意图是在没有删除概念的领域中吗？

Answer 2

更新： 不使用额外数组的 Staighforward 解决方案。运行使用的时间和内存量取决于 count 和 resize 子例程和索引访问 [] 文档中未描述的实现细节：

sub
   remove( array< int,1 >& initial_array, int item_to_remove )
begin
   loop
      int i = 1
      int removed_count = 0
      int count = initial_array.count()
   until
      i > count - removed_count;
   begin
      if( initial_array[i] != item_to_remove ) then
         # remove item by replacing it with the item from the tail
         initial_array[i] = initial_array[count - removed_count];
         removed_count = removed_count + 1
         continue;
      end;
      i = i + 1;
   end;
   # cut the tail
   initial_array.resize(count - removed_count);
end;

array<int> foo[] = { 1, 2, 3, 2, 3 };
remove( foo, 3 );  # after execution foo must contain { 1, 2, 2 }

更复杂的解决方案将是实施更适合您的目的的数据结构。正如我所理解的那样，您可以通过实施 PCL Extension

来实现这一目标

正如@iAdjunct 指出的，有趣的是为什么 array 首先没有这个方法。

如何用只允许 array.add(int) 的语言模拟 array.remove(int)

How to Simulate array.remove(int) in a Language that only Allows array.add(int)

arrays

optimization

abstraction