c++ - 如何更新指针集 C++？

Question

我需要一组 TVertex 对象来访问它们按不同参数(id 和流)的排序。在 O(1) 时间内找到第 k 个元素并在 o(log2(N)) 时间内更新它们的属性。

为此，我使用了 TComparatorF 和 TComparatorI 类。

它们都有指向 TVertex 的指针和运算符 > 和 <

TComparatorF比较流量

TComparatorI 比较id

TVertex() 将指向自身的指针指向比较器。然后将比较器放入一组比较器中。

但是当我更新 TVertex 对象的属性时，相对于它的比较器的位置不会改变。

有没有办法强制我的集合更新或存储多个排序的更好主意？

代码:

#include<stdio.h>
#include<set>
#include<stdlib.h>
using namespace std;
const int N=300000;

struct TVertex;
struct TComparatorF
{
    TVertex *cmp;
    bool operator >(const TComparatorF &other) const;
    bool operator <(const TComparatorF &other) const;  
};
struct TComparatorI
{
    TVertex *cmp;
    bool operator >(const TComparatorI &other) const;
    bool operator <(const TComparatorI &other) const;  
};
set <TComparatorF> flowset;
set <TComparatorI> idset;
struct TVertex
{
    int flow,id;  
    TVertex();
};
bool TComparatorF::operator >(const TComparatorF &other) const
{
    return !(*cmp).flow>(*(other.cmp)).flow;   
}
bool TComparatorF::operator <(const TComparatorF &other) const
{
    return !(*cmp).flow<(*(other.cmp)).flow;
}
bool TComparatorI::operator >(const TComparatorI &other) const
{
    return !(*cmp).id>(*(other.cmp)).id;   
}
bool TComparatorI::operator <(const TComparatorI &other) const
{
    return !(*cmp).id<(*(other.cmp)).id;
}
TVertex::TVertex()
{
    flow=0;
    TComparatorF comp;
    comp.cmp=this;    
    flowset.insert(comp);
    TComparatorI comp2;
    comp2.cmp=this;
    idset.insert(comp2);
}
TVertex ver[N];

int main()
{
    ver[0].flow=17;
    ver[0].id=6;
    ver[1].flow=100;
    ver[1].id=5;
    ver[2].flow=5798;
    ver[2].id=40;
    TComparatorF comp=*(flowset.begin());
    TComparatorI comp2=*(idset.begin());
    printf("%d %d\n",(*(comp.cmp)).flow,(*(comp2.cmp)).id);
    system("PAUSE");
    return 0;
}

我明白了

17 6

代替

5798 40

Answer 1

回答“是否有办法强制我的集合更新或存储多个排序的更好主意？”

容器不会根据其条目的更改自行更新，这就是设置条目和映射键保持不变的原因。您可以对手动完成更新(删除/插入)的集合进行包装，或者您可以使用提升 multi index containers已经有了这个(参见 modifiers )