c++ - 使用结构指针的 std::priority_queue 时出现意外结果

Question

我敢肯定这段代码是不言自明的，所以我直奔主题。如果代码不清楚，请询问更多详细信息。

Foo.h
=====

#include <iostream>

class Foo
{
public:
    virtual ~Foo(){};
    Foo();
    Foo(const int b);
    bool operator<(const Foo&) const;
    friend std::ostream& operator<<(std::ostream&, const Foo&);

    int b;
};

Foo.cpp
=======

#include "Foo.h"

Foo::Foo()
{
}

Foo::Foo(const int b)
{
    this->b = b;
}

bool Foo::operator<(const Foo& other) const
{
    return b < other.b;
}

std::ostream& operator<<(std::ostream& os, const Foo& f)
{
    os << '{' << f.b << '}';
    return os;
}

Bar.h
=====

#include <vector>
#include <queue>
#include "Foo.h"

class Bar
{
    struct FooPp
    {
        Foo f;
        int a;

        FooPp(const Foo&);
        bool operator<(const FooPp&) const;
        friend std::ostream& operator<<(std::ostream& os, const FooPp& fpp)
        {
            os << '[' << fpp.a << "]," << fpp.f;
            return os;
        }
    };

    struct foopp_compare
    {
        bool operator()(const FooPp* pA, const FooPp* pB ) const 
        {
            return *pA < *pB;
        }
    };

public:
    virtual ~Bar(){};
    Bar(const std::vector<Foo>&);

    std::vector<FooPp> vf;
    std::priority_queue<FooPp*, std::vector<FooPp*>, foopp_compare> fq;
};

Bar.cpp
=======

#include "Bar.h"

Bar::FooPp::FooPp(const Foo& f)
{
    this->f = f;
    a = f.b;
}

bool Bar::FooPp::operator<(const FooPp& other) const
{
    return f < other.f;
}

Bar::Bar(const std::vector<Foo>& vf)
{
    for (std::vector<Foo>::const_iterator f = vf.begin();
            f != vf.end();
                ++f)
    {
        this->vf.push_back(*f);
        fq.push(&(this->vf.back()));
    }
}

main.cpp
========

#include <iostream>
#include "Bar.h"

int main()
{
    // Foo
    Foo f1(1);
    Foo f2(6);
    std::vector<Foo> vf;
    vf.push_back(f1);
    vf.push_back(f2);
    // Bar
    Bar b(vf);
    // print b.vf: [1]{1}, [6],{6};
    std::cout << b.vf[0] << '\n';
    std::cout << b.vf[1] << '\n';
    // print the top of the prio_q: [6],{6};
    std::cout << *(b.fq.top()) << '\n';
    // change "a" in b.vf[1] -> [-12],{6}
    b.vf[1].a = -12;
    // print b.vf[1]: [-12],{6};
    std::cout << b.vf[1] << '\n';
    // print the top of the prio_q: [-12],{6};
    std::cout << *(b.fq.top()) << '\n';
    return 0;
}

这就是我得到的:

./example 
[1],{1}            // OK
[6],{6}            // OK
[1],{135704652}    // ??
[-12],{6}          // OK
[1],{135704652}    // ??

似乎 std::vector<FooPp>已正确初始化，但我不明白 std::priority_queue 发生了什么，它应该用指向 std::vector<FooPp> 元素的指针初始化.怎么了？

顺便说一下..这是为你们这些使用 Unix 机器的人准备的 makefile

Makefile
========

CXX      := g++
LD       := g++
CXXFLAGS := -Wall -g -O0 --std=c++0x -I.

SRC := $(shell ls *.cpp)
OBJ := ${SRC:%.cpp=%.o}

.PHONY: clean

example: $(OBJ)
    $(LD) $^ -o $@

clean:
    rm -rf $(OBJ) *~ example

Answer 1

每次推送都会修改底层 vector vf，并在该过程中使所有迭代器(以及从中获取的地址)无效。

我认为解决此问题的最快方法是修改 Bar 的构造函数:

Bar::Bar(const std::vector<Foo>& vf)
    : vf(vf.begin(), vf.end())
{
    for (std::vector<FooPp>::iterator f = this->vf.begin();
         f != this->vf.end();
         ++f)
    {
        fq.push(&(*f));
    }
}

输出

[1],{1}
[6],{6}
[6],{6}
[-12],{6}
[-12],{6}

主机 我会用这段代码做其他事情(使用初始化列表等)，但这是我能想到的最小的代码更改，它将为您提供一些东西有效。