c++ - vector 中的元素更改为随机值

Question

我正在尝试解决 infoarena.ro(类似于 codeforces.com 的站点，但它是罗马尼亚语)上的问题，由于某种原因，集合中的某些元素只是更改为随机值。相关代码:

#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ofstream out("test.out");
ifstream in("test.in");

struct Edge
{
    int from, to, color, index;
    bool erased = false, visited = false;
};

struct Event;
int point(const Event* event);

struct Event
{
    int time;
    bool add;
    Edge *edge;

    bool operator < (const Event other) const
    {
        return (this->time < other.time) ||
               (this->time == other.time && this->add < other.add) ||
               (this->time == other.time && this->add < other.add && 
               point(this)>point(&other));
    }
};

int point(const Event* event)
{
    if(event->edge->from == event->time)
        return event->edge->to;
    else
        return event->edge->from;
}

vector<Edge> edges;
vector<Event> events;

int main()
{
    int N, M;
    in >> N >> M;
    for(int i = 0; i < M; i++)
    {
        int x, y;
        in >> x >> y;
        if(x > y)
            swap(x, y);
        Edge e = {x, y, i, i};
        edges.push_back(e);
        events.push_back(Event{x, true, &edges.back()});
        Edge debug = *events.back().edge;
        events.push_back(Event{y, false, &edges.back()});
        debug = *events.back().edge;
    }
    sort(events.begin(), events.end());
    for(Event event : events)
        out << event.edge->from << " " << event.edge->to << "\n";

    return 0;
}

我排除了我编写的与问题无关的代码。

输入: 5 6 1 2 2 5 1 4 3 1 4 3 5 3

第一行是 N(顶点数)和 M(边数)。下一行是所有的边。

输出:

44935712 44896968
1 4
1 3
44935712 44896968
3 1941924608
1 3
3 4
3 5
1 4
3 4
3 1941924608
3 5 

我正在努力制作一本我老师所说的“日记”。对于每条边 (x,y)，我想在 x 阶段将其添加到堆栈中，并在 y 阶段将其删除(连同堆栈中的所有其他元素，直到到达 (x, y))。我想在进行这些操作时按“时间”排序(因此事件结构中的“时间”值)。 “添加”表示这是添加边还是从堆栈中删除边的事件。

出于调试目的，我正在输出“事件” vector 中的边，我注意到这些值变为随机值。有人可以解释为什么会这样吗？

Answer 1

问题就在这里

events.push_back(Event{x, true, &edges.back()});

这里

events.push_back(Event{y, false, &edges.back()});

当您将结构插入 edges vector 时，该 vector 将重新分配存储所包含结构所需的内存。如果发生这样的重定位，则指向 vector 中元素的所有迭代器和指针都会变得无效。

一个简单的解决方案是将指针存储在edges vector 中，然后复制Event 结构的指针。另一种可能的解决方案是进行两次传递。一个创建 edges vector ，然后一个单独的 pass(循环)创建 events vector 。