0

我需要一组 TVertex 对象才能通过不同的参数（id 和 flow）访问它们的排序。在 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

4

1 回答 1

1

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

容器不会在其条目更改时更新自己，这就是为什么设置条目和映射键是恒定的。您可以对手动完成更新的集合进行包装（删除/插入），或者您可以使用已经具有此功能的 boosts多索引容器（请参阅修饰符）

于 2013-10-18T11:22:46.643 回答