假设我正在初始化一个向量vector<bool> V(n);。我能知道V[n]是否初始化了吗?我需要它来进行动态规划。如果初始化V[n]，我将使用值V[n]来获得结果。如果它还没有初始化，我会应用一个函数foo(.., n)或其他东西来获得V[n]的值。我问这个问题是因为我不想初始化一个vector<int> V(n, -1);与3个状态，如-1(未分配，或尚未找到)，0(为假)和1(为真)。相反，如果有一种方法可以知道变量V[n]是否未赋值，我可能能够为较大的n值节省一些空间。
只是把所有的评论收集成一个可读的答案。
存在的vector的所有成员都是初始化的，因此为了解决这个问题，我们实际上需要表示3种状态，uninitialized, False, True，并将条目创建为uninitialized。我们希望向量最初包含处于未初始化状态的节点。
那么如何最好地代表这三种状态呢?注意事项:代码可维护性;访问速度;内存使用。
vector<bool>是vector的一个特殊实现，可以优化为每字节存储多于1个值。可以将8个bool位压缩到一个字节中。因此，bool值为1000的向量将只使用125字节。
如果您创建任何其他数据向量，它将存储该数据类型大小的对象，例如char，或者更确切地说是vector
一个vector<int>会在每个条目中使用一定数量的字节，可能至少4个字节，所以保存1000个元素需要花费4000字节。
但是你只会在char中使用可能的255种状态中的3种，所以使用char的向量会比使用int的向量更有效，但与vector<bool>相比仍然有些浪费存储。你可能不关心这个，这是一个公平的方法。vector<bool>生成的代码比法向量生成的代码更复杂，所以你的代码会变慢。
让我们疯狂地使用enum:
enum class State: int8_t
{
uninitialised = -1,
False: 0,
True: 1
};
std::vector<State> V(n,State::uninitialised);
那么vector<bool>呢?
建议使用更紧凑的形式是使用2个bool向量，一个表示条目是否有效，第二个表示其值已设置。这将花费2*125字节，或者为1000个条目花费256字节。与char类型的vector相比，这仍然是一个节省。
或者您可以为vector编写自己的包装器，其中将2个连续条目视为有效和设置标志，并将其分配为您想要的两倍大。这具有参考局部性的优点，并且潜在的优化器可以在某种程度上合并连续的问题"它是否有效"。
所以你节省了一些存储空间，代价是一些额外的复杂性(速度损失)。您可以将其封装在带有访问器的类中，以隐藏复杂性。
如果你打算这样做，你可以在vector<unit8_t>周围编写自己的包装器，它将输入索引除以4，并将存储的值分成4个2位的三状态值。这可能会稍微快一点，因为你不需要单独问向量"它是否有效"。
你/可以/将4个以上的三态压缩到一个字节中——你可以得到5个，但这会生成非常慢的代码。编译器知道如何高效地除以4，但不太能快速地除以5或3的幂。
现在我们倾向于选择速度和简单而不是节省空间，所以如果你喜欢，可以做vector<bool>的事情，但坚持使用char的向量。
很好。
我想我要问的另一个问题是，在什么条件下条目无效?它们是顺序有效的吗?如果有效条目的数量表明更高的索引还没有有效?
在这种情况下，你可以从一个空的vector<bool>开始，并在你需要的时候把新的值推到它上面——使用index < size()来决定当前索引是否有效?您可以使用reserve()来避免向量在增长时重新分配。这节省了一半所需的存储空间，并使代码复杂性易于管理，因此值得考虑。
当然，在你的情况下，initializing/validity可能是一个完全随机的状态，在这种情况下，这不是一个选项。