C++重组数组以填补空白？

Question

我不确定单词重组是否是正确的术语，但它是我能描述我所寻找的唯一方法。

如果我有发言权，猫阵列，像这样：

CAT *myCats[99]; 

myCats[0] = new CAT; 
myCats[1] = new CAT; 
myCats[2] = new CAT; 
myCats[3] = new CAT; 
myCats[4] = new CAT; 
myCats[5] = new CAT; 

在一个时间点上，可以说myCats [3]被删除：

delete myCats[3]; 

现在我有以下：

myCats[0] 
myCats[1] 
myCats[2] 
myCats[4] 
myCats[5] 

有一种简单的方法来重组阵列，使其莫ves 4> 3和5> 4，基本上填补了空白？

myCats[0] 
myCats[1] 
myCats[2] 
myCats[3] 
myCats[4] 

是实现这一目标的最佳方式，基本上通过数组进行迭代，并确定如果一个元素是空的/丢失，我只需要下一个已存在的元素搬进自己的位置？我将如何做到这一点？我将如何确定数组中任何点上的Cat元素是否存在？还是有更简单的预先确定的方法来完成我所需要的？

对不起，如果示例和语法有点关闭。我是C++新手。

UPDATE

感谢您的快速建议。看起来像矢量是要走的路。我总是忘记矢量。在我心中的前面，一个Vector就是如果你使用的是C++持有的X，Y和Z值:-)

Answer 1

的容器，你可以更轻松地完成这项使用std::vector：

std::vector<CAT*> cats; 
cats.push_back(new CAT); 
cats.push_back(new CAT); 
cats.push_back(new CAT); 

// remove the second cat 
delete cats[1]; 
cats.erase(cats.begin() + 1); 

现在，矢量中有两只猫（插入的第一只和第三只猫），它们位于索引零和一。

然而，在C++中，没有任何理由来动态分配的一切，所以你可能只是一个vector<CAT>更好：

std::vector<CAT> cats; 
cats.push_back(CAT()); 
cats.push_back(CAT()); 
cats.push_back(CAT()); 

// remove the second cat 
cats.erase(cats.begin() + 1); 

这样，猫的破坏自动处理和你不必担心自己管理任何内存。

如果做必须使用指针（例如，你的类是一个多态基类），你可能想使用智能指针（例如，shared_ptr S）的std::vector。使用智能指针，您不必记得在完成对象时删除对象 - 它会自动完成。例如，使用shared_ptr上面的代码看起来像：

std::vector<std::shared_ptr<CAT> > cats; 
cats.push_back(std::make_shared(new CAT)); 
cats.push_back(std::make_shared(new CAT)); 
cats.push_back(std::make_shared(new CAT)); 

// remove the second cat 
// note we don't need to call delete; shared_ptr does that for us 
cats.erase(cats.begin() + 1); 

（你的标准库中可能不包括在std命名空间shared_ptr然而，在这种情况下，you may find it elsewhere）。如果您不熟悉shared_ptr,the Boost documentation是一个很好的介绍。

Answer 2

您可以在删除指针后指定NULL，然后检查指针是NULL还是保留一个相同大小的bools数组，以指示该对象是否存在。至于重组：如果订单确实重要，那么您必须按照所述移动所有元素。如果订单无关紧要，只需将最后一个元素移至缺失的空白处。

Answer 3

是否有任何具体原因，您不能使用std::vector而不是数组？矢量自动调整大小，所以你不必担心这一点。

Answer 4

正如其他人已经指出，使用std :: vector会为你做所有的重新分配，但它仍然是一个O（n）操作。不过，您可能可以使用其他数据结构做得更好。例如std :: list将允许您从O（1）列表中的任何位置删除元素。

最终哪个数据结构是最合适的将取决于您需要支持的所有操作，它们的相对频率以及每个需要的性能。