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

Question

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

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

• add(x) --- 压入 x 并调整长度 + 1
• 调整大小(x) --- 新长度 = x
• count() --- 返回数组的长度

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

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

Answer 1

更新: 不使用额外数组的直接解决方案。运行时间和使用的内存量取决于 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 首先没有这个方法。