I need a group of TVertex objects to have an access to their sortings by diffrent parameters (id and flow). To find the kth element in O(1) time and to update their properties in o(log2(N)) time.
To do this I use TComparatorF and TComparatorI classes.
They both have a pointer to TVertex and operators > and <
TComparatorF compares flows
TComparatorI compares ids
TVertex() puts a pointer to itself to a comparator. And then puts the comparator to a set of comparators.
But when I update properties of TVertex object, position of relative to it comparator doesn't change.
Is there a way to force my sets to update or a better idea for storing multiple sortings?
Code:
#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;
}
I get
17 6
instead of
5798 40