"Empty" array\vector 成员 c++
"Empty" array\vector members c++
我必须通过从磁盘读取数据来填充一个包含 1000 个对象的数组。但是，并非每个对象都存在。
一旦我声明了一个数组，内存就会被预留给1000个对象。
当我一张一张地阅读它们时，我将内存设置为相应的值。但是，可能没有成员 #276 的对象，它的内存将保持设置为声明数组时存在的任何内容。
如何保留数组的某个成员invalid/doesn不存在的信息？
我可以通过某种方式将成员的所有字节设置为零，但这可能是一个有效的对象。
显而易见的解决方案是添加另一个字节数组，根据该索引处的对象是否存在将其设置为 1 或 0，但这似乎不是很优雅。
这可以用向量代替吗？它能以某种方式存储一个空值吗？
从逻辑上讲，您需要同时跟踪存在的值和实际存储了数据的值。没有一种最好的方法可以做到这一点，您做出的选择将取决于您在做什么。
在某些情况下——你的实现似乎不是其中之一——你可以保留一些特殊值，如 nullptr 或 -1 作为标记，并用它来标记空槽.不过，您已经提到这里不存在此选项，因此我们将排除该选项。
另一个非常合理的选择是为每个插槽存储一个并行位向量或一些辅助数据，以标记该插槽是否正在使用。如果您使用位向量，与您将用于元素本身的内存相比，此处所需的额外内存非常小。
上述两种方法的缺点是，如果您有一个真正庞大的数组（例如，数百万个元素），您将为未使用的插槽使用大量内存，包括插槽本身和任何额外的簿记。另一种选择是使用像 std::map 或 std::unordered_map 这样的稀疏数据结构，从索引到元素，然后只将元素加载到实际使用的稀疏结构中。通过这种方式查找单个元素的性能成本会稍慢一些，但内存增益可能会很大。
Could this be done with a vector instead?
没有.
当然，如果您使用一些额外的 space 来存储该信息（存在与否）或不存在对象的标记值，则除外。 std::vector 具有根据其存储的元素数量调整自身大小的强大能力；所以如果它能满足你的要求，它就会失去那个能力。
我会使用 std::unordered_map，其中每个键都是对象的索引（例如 #276），值是实际对象。如果某个对象不存在，请不要在映射中插入该键。
或 std::map, if you need to iterate over your data efficiently. Choosing between std::map and std::unordered_map.
很难找到一个将数组的单元格标记为空的标记值。例如，如果你已经在内存中的某个地方有了数据（我认为这不是你的情况），那么你可以使用一个指针数组，而不是一个存储整个对象的数组。那么很明显，NULL 指针将用于空单元格
另一种选择是使用成对数组，如下所示：std::pair<myClass, bool>，其中第二个操作数指示相应的单元格是否为空。
此外，您可以使用 std::vector<bool> instead, which is very memory efficient (if you decide to follow an approach of an extra data structure), as mentioned in 。然而，它将缺乏索引性能。
首先，请确保您确实担心内存不足，无法进行优化。 1000 个对象并不多，除非它们很大并且您希望它们很稀疏。他们的指数重要吗？也就是说，如果加载 2 个对象，可以将它们放入数组的元素 0,1 中，还是它们在数组中的位置很重要，并且每个对象都有一个必须使用的特定数组索引？如果是这种情况，您最终可能会在数组中出现大洞，并且需要一个指示器来指示哪些元素被使用或未使用（因此我不推荐这样做。）相反，您可能会考虑一个初始化为null，然后分配使用的元素，并在适当的索引处将相应的指针设置为它们。如果可以压缩数组，还不如使用向量。
另一种选择是不将项目放在数组中，而是像树图一样的东西，它只包含您插入的元素，但仍然可以使用类似于数组索引的键找到。
（注意：std::unordered_map 比 std::map 快，但哈希表会过度分配内存（通常，如果使用了分配的 space 的 70%，则它们被认为是高负载）这个问题的全部目的是减少内存使用。）
我必须通过从磁盘读取数据来填充一个包含 1000 个对象的数组。但是，并非每个对象都存在。
一旦我声明了一个数组，内存就会被预留给1000个对象。 当我一张一张地阅读它们时，我将内存设置为相应的值。但是，可能没有成员 #276 的对象，它的内存将保持设置为声明数组时存在的任何内容。
如何保留数组的某个成员invalid/doesn不存在的信息？
我可以通过某种方式将成员的所有字节设置为零，但这可能是一个有效的对象。
显而易见的解决方案是添加另一个字节数组，根据该索引处的对象是否存在将其设置为 1 或 0，但这似乎不是很优雅。
这可以用向量代替吗？它能以某种方式存储一个空值吗？
从逻辑上讲，您需要同时跟踪存在的值和实际存储了数据的值。没有一种最好的方法可以做到这一点，您做出的选择将取决于您在做什么。
在某些情况下——你的实现似乎不是其中之一——你可以保留一些特殊值，如 nullptr 或 -1 作为标记，并用它来标记空槽.不过，您已经提到这里不存在此选项，因此我们将排除该选项。
另一个非常合理的选择是为每个插槽存储一个并行位向量或一些辅助数据，以标记该插槽是否正在使用。如果您使用位向量，与您将用于元素本身的内存相比，此处所需的额外内存非常小。
上述两种方法的缺点是，如果您有一个真正庞大的数组（例如，数百万个元素），您将为未使用的插槽使用大量内存，包括插槽本身和任何额外的簿记。另一种选择是使用像 std::map 或 std::unordered_map 这样的稀疏数据结构，从索引到元素，然后只将元素加载到实际使用的稀疏结构中。通过这种方式查找单个元素的性能成本会稍慢一些，但内存增益可能会很大。
Could this be done with a vector instead?
没有.
当然，如果您使用一些额外的 space 来存储该信息（存在与否）或不存在对象的标记值，则除外。 std::vector 具有根据其存储的元素数量调整自身大小的强大能力；所以如果它能满足你的要求，它就会失去那个能力。
我会使用 std::unordered_map，其中每个键都是对象的索引（例如 #276），值是实际对象。如果某个对象不存在，请不要在映射中插入该键。
或 std::map, if you need to iterate over your data efficiently. Choosing between std::map and std::unordered_map.
很难找到一个将数组的单元格标记为空的标记值。例如，如果你已经在内存中的某个地方有了数据（我认为这不是你的情况），那么你可以使用一个指针数组，而不是一个存储整个对象的数组。那么很明显，NULL 指针将用于空单元格
另一种选择是使用成对数组，如下所示：std::pair<myClass, bool>，其中第二个操作数指示相应的单元格是否为空。
此外，您可以使用 std::vector<bool> instead, which is very memory efficient (if you decide to follow an approach of an extra data structure), as mentioned in
首先，请确保您确实担心内存不足，无法进行优化。 1000 个对象并不多，除非它们很大并且您希望它们很稀疏。他们的指数重要吗？也就是说，如果加载 2 个对象，可以将它们放入数组的元素 0,1 中，还是它们在数组中的位置很重要，并且每个对象都有一个必须使用的特定数组索引？如果是这种情况，您最终可能会在数组中出现大洞，并且需要一个指示器来指示哪些元素被使用或未使用（因此我不推荐这样做。）相反，您可能会考虑一个初始化为null，然后分配使用的元素，并在适当的索引处将相应的指针设置为它们。如果可以压缩数组，还不如使用向量。
另一种选择是不将项目放在数组中，而是像树图一样的东西，它只包含您插入的元素，但仍然可以使用类似于数组索引的键找到。
（注意：std::unordered_map 比 std::map 快，但哈希表会过度分配内存（通常，如果使用了分配的 space 的 70%，则它们被认为是高负载）这个问题的全部目的是减少内存使用。）