为什么将循环中的最后一个元素添加到向量段错误？

Question

我有下面的代码，我将标准输入解析为存储在向量中的对象。工作正常，直到它到达

chain->jobs.push_back(job);

出现段错误的迭代之一。我推断当它第二次从地图获取链时它会失败，但只是不明白为什么第二次访问会导致问题。

#include <iostream>
#include <string>
#include <regex>
#include <vector>
#include <map>

using namespace std;

struct Job
{
    Job(){};
    Job(const Job& job) 
        : job_id_(job.job_id_), runtime_sec_(job.runtime_sec_), next_job_id_(job.next_job_id_) {};
    Job(int job_id, int runtime_sec, int next_job_id)
        : job_id_(job_id), runtime_sec_(runtime_sec), next_job_id_(next_job_id) {};
    Job& operator=(const Job& job){
        job_id_ = job.job_id_;
        runtime_sec_ = job.runtime_sec_;
        next_job_id_ = job.next_job_id_;
        return *this;
    }
    ~Job(){};
    int job_id_;
    int runtime_sec_;
    int next_job_id_;
};

struct Chain
{
    std::vector<Job> jobs;
};

void parse_input(std::vector<Chain>& chains)
{
    std::string line;
    std::getline(std::cin, line);
    std::map<int, Chain*> chain_map;
    
    Job job;
    std::regex job_regex("([0-9]+),([0-9]+),([0-9]+)");
    while (getline(std::cin, line))
    {
        std::cout << line << '\n' << std::flush;
        std::smatch matches;
        if (std::regex_match(line, matches, job_regex))
        {
            int job_id = std::stoi(matches[1].str());
            auto res = chain_map.find(job_id);
    
            Chain* chain;
            if (res == chain_map.end())
            {
                chains.emplace_back();
                chain = &chains.back();
            } else
            {
                chain = res->second;
            }
            Job job(std::stoi(matches[1].str()), std::stoi(matches[2].str()), std::stoi(matches[3].str()));
            chain->jobs.push_back(job);
            // chain->jobs.emplace_back(std::stoi(matches[1].str()), std::stoi(matches[2].str()), std::stoi(matches[3].str()));
            //chain->jobs.push_back(Job(std::stoi(matches[1].str()), std::stoi(matches[2].str()), std::stoi(matches[3].str())));
            // auto job = chain->jobs.back();
            chain_map[job.next_job_id_] = chain;
        } else
        {
            std::cout << "Malformed input\n";
        }
        std::cout << chains.size() << '\n';
    }
}

int main()
{
    std::vector<Chain> chains;
    parse_input(chains);
    return 0;
}

标准输入示例

job_id,runtime,next_job_id
1,30,23
2,23,3
3,20,0
23,50,4
4,43,0

编辑： 堆栈跟踪

Program received signal SIGSEGV, Segmentation fault.
0x000055555555e524 in std::construct_at<Job, Job const&> (__location=0x1e8e5f176c2a300c) at /usr/include/c++/11/bits/stl_construct.h:97
97          { return ::new((void*)__location) _Tp(std::forward<_Args>(__args)...); }
(gdb) bt
#0  0x000055555555e524 in std::construct_at<Job, Job const&> (
    __location=0x1e8e5f176c2a300c)
    at /usr/include/c++/11/bits/stl_construct.h:97
#1  0x000055555555e569 in std::allocator_traits<std::allocator<Job> >::construct<Job, Job const&> (__a=..., __p=0x1e8e5f176c2a300c)
    at /usr/include/c++/11/bits/alloc_traits.h:518
#2  0x000055555555cff8 in std::vector<Job, std::allocator<Job> >::push_back (
    this=0x5555555bd2a0, __x=...) at /usr/include/c++/11/bits/stl_vector.h:1192
#3  0x000055555555ad09 in parse_input (
    chains=std::vector of length 2, capacity 2 = {...}) at main.cpp:58
#4  0x000055555555aff8 in main () at main.cpp:85 

Answer 1

您持有无效的指针。

Chain* chain;
if (res == chain_map.end())
{
    chains.emplace_back();
    chain = &chains.back();
} else
{
    chain = res->second;
}

调用 emplace_back() 可能会导致整个 vector 数据被重新分配，并将其内容移动到新的内存位置。当发生这种情况时，您存储在 chain_map 变量中的指针将变得无效。

也许考虑使用list，它不必保存连续的内存块，并且您可以保存插入之间的引用。否则，请避免使用这样的原始指针。正如您所看到的，除非您真正了解发生了什么，否则它们可能会很棘手。

Answer 2

问题在于，在

main

中，您声明了

std::vector<Chain> chains;

，其大小为0，容量为0。第一次匹配您在地图中找不到的线，因此

emplace_back

在

chains

中找到一个新链，并在地图中存储指向该新链的指针。到目前为止没有问题。问题是下次执行

chains.emplace_back()

时，向量没有更多容量，需要获得更多空间。很可能，当前内存附近没有可用空间，因此向量需要重新分配更大的空间，移动所有存储的

Chain

。现在他们住在一个新的内存地址。但是您仍然有一个指向存储在映射中的旧链的指针。下次您使用之前看到的 job_id 解析一行时，您将访问具有垃圾值和潜在段错误的链。

这个问题总是发生在

std::vector

上，当

push_back

-ing 或

emplace_back

-ing 时，之前存在的向量的所有迭代器（也指向元素的指针）可能不再有效，因为可能会发生重定位

std::vector

的记忆。

为了防止这种情况，您可以在

chains

中构造

main

，其大小您知道不会有更多工作。假设最多有

n

个作业，将

chains

构造为

std::vector<Chain> chains(n);

，这会给你一个具有

n

容量的向量。或者，您可以存储链的索引而不是指针，而不是指向映射中的链的指针。