如果它们位于不同的数据结构中，那么维护相同数据的两个副本是不好的做法吗？

Question

假设我有一组通用的索引对象，U，以及这些对象的子集S。 S很大（比方说，1,000,000个元素），但U更大（比如至少100,000,000）。

我想对这些集合执行两个基本操作：

（1）给定从0到x大小减去1的任何整数U，检查S的成员资格，如果不是成员，则将x添加到S，并且

（2）从S中选择（并删除）随机元素。

为了执行操作的第一部分（1），对我来说保持v大小的布尔向量U是有意义的，如果元素true是set x的成员，则值为S。

然而，因为U比S大得多，在v中选择一个随机元素并希望它也是S中的一个元素没有意义。我，如果U比S大100倍，那么它只能找到S的元素，平均每100次尝试一次。

因此，为了执行第二个操作，维护S中的元素索引列表并从中选择随机元素是有意义的。

现在唯一的问题是，现在有两个相同数据的副本，并且它们都需要在每个操作中单独更新。这是第一个操作的伪代码：

** operation 1 - check membership and add **
input: boolean vector, v
       integer vector, S
       integer, x

if v[x] is not true:
    v[x] = true
    append x to S
return

这是相对简单的，但它必须更新索引的向量，即使它没有使用它。这是第二个操作：

** operation 2 - select and remove random element of S **
input: boolean vector, v
       integer vector, S

generate random integer x between 0 and size of S
set v[S[x]] to false
remove S[x] from S
return

维护两个数据副本使得这两个操作都变得更加复杂，因为每个操作都需要更新两个数据结构，即使它只需要一个。这是不好的做法吗？

我能提出的唯一选择是使用其中一种。但这使得一个操作更简单，但另一个更复杂。例如（只给出了更复杂的）：

** operation 1 - check membership and add**
input: integer vector, S
       integer, x

iterate over S
if x in S:
    return
else:
    append x to S
    return

因此，每次，它都必须遍历整个S，而不是单个查找，并且

** operation 2 - select and remove random element of S **
input: boolean vector, v

while true:
    generate random integer x between 0 and size of S
    if v[x] true:
        v[x] = false
        return

这两个看起来效率都很低，特别是如果U和S的大小很大，而且U和S之间的差异也很大。有没有办法只用一个数据结构才能有效地执行这两个操作？或者维护同一件事的两份副本真的没有什么大问题吗？

编辑：

我写的代码是用c ++编写的，所以我想我特别询问c ++数据结构，但问题并不是特定于语言。