infoarena.ro刷题时vector元素值随机变更问题求助

嘿，这个问题我太熟了——你踩了C++ vector的经典陷阱：扩容导致野指针失效。

让我给你拆解一下问题出在哪：

• 你在循环里每次调用edges.push_back(e)后，立刻把&edges.back()（也就是刚添加的Edge元素的地址）存到了Event的edge指针里。
• 但vector的工作机制是这样的：当它当前的容量不够装下新元素时，会自动重新分配一块更大的内存空间，把原来的所有元素复制/移动过去，然后释放旧的内存。这时候，原来存在Event里的那些Edge指针就指向了已经被释放的内存——也就是所谓的「野指针」。
• 后续你对events排序、遍历输出时，访问event.edge->from和event.edge->to都是在访问野指针指向的内存，自然会读出随机的垃圾值。

解决方法有几种，按推荐程度排序： #

1. 提前给vector预留足够容量

既然你提前知道要添加M个Edge元素，直接在main开头给edges预留足够的空间，这样push_back就不会触发扩容，指针就一直有效：

int main() {
 int N, M;
 in >> N >> M;
 edges.reserve(M); // 关键：提前分配能装下M个元素的容量
 events.reserve(2*M); // 事件数量是2*M，也可以提前预留避免扩容
 // ... 后面的代码不变
}

2. 用下标代替指针

放弃保存指针，改成保存Edge在vector里的下标（int类型）。这样不管vector怎么扩容，下标都是有效的，访问时直接用edges[下标]获取元素就行：

// 修改Event结构体
struct Event {
 int time;
 bool add;
 int edge_idx; // 替换指针为下标
 bool operator < (const Event other) const {
     const Edge& e1 = edges[edge_idx];
     const Edge& e2 = edges[other.edge_idx];
     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));
 }
};

// 修改point函数
int point(const Event* event) {
 const Edge& e = edges[event->edge_idx];
 return (e.from == event->time) ? e.to : e.from;
}

// 循环里的修改
for(int i = 0; i < M; i++) {
 // ... 读取x,y的代码不变
 edges.push_back(e);
 int idx = edges.size() - 1; // 获取刚添加元素的下标
 events.push_back(Event{x, true, idx});
 events.push_back(Event{y, false, idx});
}

// 输出时的修改
for(Event event : events) {
 const Edge& e = edges[event.edge_idx];
 out << e.from << " " << e.to << "\n";
}

3. 动态分配Edge（不推荐）

用new Edge来创建元素，把指针存在vector里，这样元素不会因为vector扩容而移动。但这种方式需要手动管理内存，容易出现内存泄漏，除非你用智能指针，否则不建议这么做。

最后提醒 #

记住C++容器的这个特性：当vector、string这些容器发生扩容时，所有指向其元素的指针、引用、迭代器都会失效。所以如果要保存元素的引用或指针，要么提前预留足够容量，要么用下标这种不会失效的方式。

内容的提问来源于stack exchange，提问作者Alexandru-Andrei Bosinta