Мне нужна группа объектов TVertex, чтобы иметь доступ к их сортировкам по различным параметрам (id и flow). Найти k-й элемент в O (1) раз и обновить их свойства в o (log2 (N)) времени.
Для этого я использую классы TComparatorF и TComparatorI.
Оба они имеют указатель на TVertex и операторы> и <
TComparatorF сравнивает потоки
TComparatorI сравнивает идентификаторы
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
Отвечая на вопрос "Есть ли способ заставить мои наборы обновиться или лучше создать память для нескольких сортировок?"
Контейнеры не обновляют себя при изменении своих записей, поэтому заданные записи и ключи карты являются постоянными. Вы можете сделать оболочку наборов, где обновление выполняется вручную (удалить/вставить), или вы можете использовать контейнеры с несколькими индексами, которые уже есть (см. Модификаторы)