未处理的异常 .. Microsoft C++ 异常：std::bad_alloc 在内存位置

Question

我有一个结构信息对象的大向量 (mainvect)（大约 800 万个元素），我想删除重复项，该结构由 pid 和 uid 组成。

 struct info
 {
    int pid;
    string uid;

 }

我有另一个向量 (vect1)，它包含每个 pid 的信息及其在 mainvect 中的出现（它有助于搜索特定索引而不是所有主 vect）vect1 的大小是42 万个元素

struct pidInfo
 {
    int pid;
    int numofoccurence;
}

我想在 vect2.

中的 mainvect 中存储不重要的元素

 .
 .
// sort mainvect based on pid
sort(mainvect.begin(), mainvect.end(), sortByPId());

int start = 0;
int end = 0;
vector <string> temp;  // to store uids with a specific pid 

for (int i = 0; i < vect1.size(); i++)
{
   end = end + vect1[i].numofoccurence;

    for (int j = start; j < end; j++)
    {
        temp.push_back(mainvect[j].uid);
    }

    start = start + vect1[i].numofoccurence;

    // remove duplicate uid 
    sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end());

    // push remaining unique uids 
    for (int k = 0; k < temp.size(); k++)
    {
        info obb;
        obb.pid = vect1[i].pid;
        obb.uid = temp[k];
        vect2.push_back(obb);
    }

    // empty the temp vector to use in next i iteration
    temp.erase(temp.begin(), temp.end());

}
 .
 .

但是当我运行代码时，它给了我如下图所示的异常

Answer 1

您运行内存不足。您可以做的事情很少：

您正在 Windows 上构建 32 位程序。这意味着无论您的机器上有多少物理内存，您都只有 2 GB 的 RAM 可用。您应该为 64 位架构构建程序以访问您拥有的所有 RAM。为此，您需要为项目创建新配置，并将平台设置为 x64.
你应该更聪明地使用你的记忆力。对于大向量，您可以做的最快的事情是将 std::vector 替换为 std::dequeu。

std::vector 的问题是每次它增长时都会分配一个新的内存块并复制所有数据。您正在使用的 MSVC 实现每次都会将向量增长 1.5。因此，如果 vector 占用 1 GB 内存，则下次调整大小时它将尝试分配 1.5 GB，在调整大小时总共占用 2.5 GB RAM。

std::deque 的实现通常会以较小的块分配内存，因此调整大小的问题较少。

你应该注意的另一件事是std::string。 MSVC 实现使用。 Every instance ofstd::string` 在 x86 上占用 32 个字节。因此，您的 800 万个元素向量中的每个元素可能会也可能不会浪费此内存。

根据您想在程序上花费多少时间，您可能想了解 memory-mapped files。

Answer 2

我认为你实际上有算法问题。在每次迭代中，您都会对 temp 向量中的唯一元素进行排序和保留。但是使用这种方法，每次迭代都会将越来越多的重复项添加到 vect2 中。因此，您也应该对 vect2 中的唯一元素进行排序和保留。实际上，使用 std::set 而不是 temp 和 vect2.

可能会更好

另一个建议是，如果 uid 具有某种固定长度格式（例如 GUID），则为 uid 使用更好的存储。

Answer 3

如上所述，您运行内存不足。如果你真的有这么多元素，那么研究一个小型数据库（如 sqlite）可能是一个明智的想法。

但是由于问题是关于 C++ 标准容器的，所以您处理这个问题有点笨拙。你正在做许多不必要的排序和循环。不仅漏洞百出，你的算法至少是 O(n^3)

为什么不使用已经排序的容器之一，例如 std::map？您可以像这样删除一个列表：

std::vector<info> input;

// copy into map
std::map<int, info> tmp;
for (info& i : mainvect) {
  tmp[i.pid] = i;
}

// copy back out
std::vector<info> output(tmp.size());
std::transform(tmp.begin(), tmp.end(), output.begin(), [] (const std::pair<int, info>& p) {
    return p.second;
});

不仅代码更简洁，而且运行时间为 O(n + ln(n))。或者，跳过第二步，首先使用 std::map 或 std::set 作为数据。

此外，如果您要处理大量项目，您也不想使用 std::vector。关键问题是向量的内存需要是一块连续的内存。您可能需要使用双端队列或列表。

未处理的异常 .. Microsoft C++ 异常：std::bad_alloc 在内存位置

Unhandled exception at .. Microsoft C++ exception: std::bad_alloc at memory location

c++

exception

unhandled-exception