C++大向量搜索项目

Question

第一次在这里发帖，这让我抓狂！我不能很好地解释它，所以我试着举个例子。

我正在尝试检索一个非常大的( 100k )向量中的一个元素来擦除它。反复地说，这需要很长时间……所以我试了一下：

这是我的列表中的一个小例子。它存储在我的单例粒子发射器类中。

vector<Particle> particles;
particles.reserve(100);

这是我的粒子的剥离版本

class Particle
{
Particle:
~Particle:

void Delete
{
  int listNum = (this - &particles[0]);
  particles.erase(particles.begin+listNum);
}
};

这一切都很好，但是我不想保存堆栈中的每个粒子，所以我想要更改它

vector<Particle> particles;

转到

vector<Particle*> particles;

现在我的问题是:如果向量由粒子指针组成，是否仍然可以从列表中删除和擦除粒子？

我不确定我的问题是否清楚，但我希望您能理解！

或者，如果有人知道更好的性能解决方案，我很想听听！

提前感谢！

Answer 1

您究竟计划如何使用此std::vector

您说迭代将需要很长时间，但是如果您的目标是迭代所有的值，那么您不可能比一个连续的数组做得更好。您谈到了从容器中删除元素，这意味着您需要一个动态数组，而这正是std::vector。

无论如何，您肯定不希望存储原始指针的向量。如果您测量发现由于使用某些操作而导致性能不足，则您的两个选项应该是std::vector<Particle> (通常首选)或std::vector<unique_ptr<Particle>> (仅限C++11)。根据您的用例，std::map<Particle>或std::set<Particle>可能是好主意，但我们没有足够的信息。

您没有在堆栈上存储任何Particle。std::vector中的每个元素都已经在空闲存储中(“堆”)。

您的插入和删除代码也应该与您的Particle类无关。插入和删除是对容器执行的操作，而不是对包含的元素执行的操作。

为了回答你的问题，我们需要知道一些事情。

首先，Particle有多大？这可能是最重要的信息。

其次，你对容器做了什么？您是一般地查看每个Particle并使用它们进行操作，还是在整个容器中搜索特定的Particle？如果您正在搜索，您是尝试基于某种关键字进行查找(例如，每个Particle都有一个惟一的ID，并且您在该ID上查找整个Particle )，还是尝试查找一个Particle以查看是否与另一个匹配(换句话说，您是基于Particle的身份进行查找的)？

如果您正在查找单个Particle，那么为了便于使用，std::set可能是您的首选，因为它允许二进制搜索。如果您的用例让您按键搜索粒子，那么您将需要std::map<Key, Particle>。

如果你有一堆粒子，并且你想从容器中移除几个，那么对象的大小就相当重要了。但是，对于这种情况，您通常需要一个std::vector。

简而言之，我需要更多的信息来完整地回答你的问题。

Answer 2

如果您担心将向量放到堆栈上，为什么不尝试这样的操作：

vector <Particle> * particles = new vector <Particle>;

这将使向量持续到您对其执行delete操作。此外，如果您担心性能问题，set将是一个好主意。这保证了所有的插入和删除都是对数时间，而且您不必使用自己的delete函数。要在C++11中获得更好的性能，请尝试unordered_set。