c++ - 删除整个 vector 中散落的许多站点，从而使内存成本保持最低

Question

恐怕这是一个相当大的问题，但这是简短的版本。我的程序需要删除散布在 vector 中的大量元素。这些元素与粒子有关，它还需要告诉任何在 vector 中移动过的粒子它们移动到了哪里。保持低内存成本是当务之急，因此理想情况下，我希望简化此过程，同时不更改我的数据结构(或尽可能缩小它们)。

现在是长版:

因此，我正在尝试制作一个尽可能高效的程序，在多个箱子(此处称为类别)中存储标签列表(与特定粒子相关)，其中每个粒子只能用一个表示类别但可能出现多次(尽管不一定在相邻站点中)

类别有一个列表，其中列出了它们包含的粒子(每个粒子在数组中有一个元素)，以及一个包含在特定站点中的粒子的列表。 (站点是我在整个特定数组中用于数组元素的特定名称)所以第一个可能是 (1,4,5)，显示粒子 1、4 和 5 属于此类。第二个可能会读作 (4,5,1,1,4,4)。

为了进行反向树搜索，粒子分别知道它们在粒子和位置类别列表中的位置。 (所以 1 会知道它在粒子列表中排在第一位，在站点列表中排在第 3 和第 4 位)

理想情况下，我不想添加更多由这些数据结构存储的数字，因为最小化内存成本是我的首要任务，但如果必须的话，我会这样做。

我的问题是，删除与某个粒子对应的所有元素目前是一项成本非常高的操作，但我必须完成该过程的每一步，主要是因为必须找到与特定粒子相关的所有站点粒子以及告诉其他与之交换的粒子它们的位置已经移动。

我目前将我想要删除的所有网站都发送到后面并将它们弹出，我找不到更好的方法。

请记住，虽然示例中只有 3 个粒子，但在真实模拟中可能有数百万个。

下面是我的数据结构和我目前用来从类别中删除粒子的函数。目前最大的成本是将属于某个粒子的所有站点重新排序，以便按照它们在站点数组中的位置排序，我这样做的唯一原因是我知道在后面发现的任何粒子将是其网站列表的最后一个网站。

非常感谢您的帮助，抱歉这变成了一个大问题

(whichAtom 是已经选择的粒子标签，whichCategory 是它所在的类别)

struct particle
{
    float rate;
    int categorySite;
    vector<int> occupiedSites;
};

struct bin
{
    vector<int> atomsContained;
    vector<int> sites;
};

vector<struct particle> atom (NUMBER_OF_ATOMS);
vector<struct bin> category (10);

void removeAtom()
{
    //tells atom that was last in list of atoms in that category that it has changed position
    atom[category[whichCategory].atomsContained.back()].categorySite = atom[whichAtom].categorySite;

    //removes atom from list of atoms in that category
    category[whichCategory].atomsContained[atom[whichAtom].categorySite] = category[whichCategory].atomsContained.back();
    category[whichCategory].atomsContained.pop_back();

    int numberOfSites = (int) atom[whichAtom].occupiedSites.size();

    //removes sites from that category
    for (int i = 0; i < numberOfSites; i++)
    {
        if (atom[whichAtom].occupiedSites[i] != category[whichCategory].sites.size()-1)
        {
            int categorySize = (int) category[whichCategory].sites.size();
            int distanceFromBack = 1;
            while (category[whichCategory].sites[categorySize-distanceFromBack] == whichAtom && (categorySize-distanceFromBack) != atom[whichAtom].occupiedSites[i])
            {
                distanceFromBack++;
            }


            int originalSite = atom[whichAtom].occupiedSites[i];

            //teling the atom that it has changed site (requires last site listed in the atom to be the one nearest the back)
            int targetAtom = category[whichCategory].sites[categorySize-distanceFromBack];
            std::swap(atom[targetAtom].occupiedSites.back(), atom[whichAtom].occupiedSites[i]);

            // makes sure that the sites are refenced in the order they appear in the array
            if (atom[targetAtom].occupiedSites.size() > 1)
            {
                for (int j = 0; j < atom[targetAtom].occupiedSites.size(); j++)
                {
                    for (int k = (int) atom[targetAtom].occupiedSites.size()-1; k > j; k--)
                    {
                        if (atom[targetAtom].occupiedSites[j] > atom[targetAtom].occupiedSites[k])
                        {
                            std::swap(atom[targetAtom].occupiedSites[j],atom[targetAtom].occupiedSites[k]);
                        }
                    }
                }
            }

            //telling the category that the atoms in the sites have switched
            std::swap(category[whichCategory].sites[originalSite], category[whichCategory].sites[categorySize-distanceFromBack]);
        }
    }

    //removes previously occupied sites from atoms memory (MIGHT BE COMBINEABLE WITH ABOVE)
    for (int i = 0; i < numberOfSites; i++)
    {
        category[whichCategory].sites.pop_back();
        atom[whichAtom].occupiedSites.pop_back();
    }
}

Answer 1

我倾向于建议不要使用这种反向引用(粒子记住它们的成员身份)，正是因为它会使结构僵化并使删除更加乏味。对于粒子来说，只记住它们的类别并在必要时手动扫描这些数组可能比同时记住它们在这些类别中的位置(并保持准确的数据)更快。