STL отсортированный набор, где условия заказа могут измениться

Question

У меня установлен C ++ STL с определенным пользовательским порядком.

Идея заключалась в том, что когда предметы добавляются в набор, они естественным образом упорядочиваются так, как я хочу.

Однако я только что понял, что предикат упорядочения может меняться со временем.

Предположительно, предметы в наборе перестанут быть в порядке.

Итак, два вопроса на самом деле:

1. Вредно ли, что предметы будут тогда не в порядке? Прав ли я, говоря, что худшее, что может случиться, - это то, что новые записи могут быть помещены в неправильное место (с которым я действительно могу жить) Или это может вызвать сбои, потерянные записи и т. Д.

2. Есть ли способ «обновить» порядок набора? Вы не можете использовать std :: sort () для набора. Лучшее, что я могу придумать, - выгрузить содержимое во временный контейнер и заново добавить его.

Есть идеи?

Спасибо,

John

Answer 1

set использует порядок для поиска предметов. Если вы вставите N элементов в соответствии с order1 и вставите элемент в соответствии с order2, набор не сможет определить, находится ли элемент в списке.

Это нарушит инвариант класса, что каждый элемент находится там только один раз.

Так что наносит вред.

Answer 2

Единственный безопасный способ сделать это с помощью STL - создать новый набор с измененным предикатом. Например, вы можете сделать что-то подобное, когда вам нужно отсортировать набор с новым предикатом:

std::set<int> newset( oldset.begin(), oldset.end(), NewPred() );

Answer 3

Хотя это не дает вам именно то, что вы хотите, boost :: multi_index предоставляет вам аналогичную функциональность. Благодаря тому, как работают шаблоны, вы никогда не сможете «изменить» предикат порядка для контейнера, он устанавливается в камне во время компиляции, если вы не используете отсортированный вектор или что-то подобное, где you - это тот, кто поддерживает инвариант, и вы можете отсортировать его по своему усмотрению в любой момент времени.

Multi_index, однако, позволяет упорядочить набор элементов на основе нескольких предикатов упорядочения одновременно. Затем вы можете выбрать представления контейнера, которые ведут себя как std :: set, упорядоченные по предикату, который вам небезразличен в то время.

Answer 4

Если вы можете жить с неупорядоченным набором, то почему вы сначала добавляете их в набор?

Единственный случай, о котором я могу подумать, это когда вы просто хотите убедиться, что список уникален, когда вы добавляете их. Если это так, то вы можете использовать временный набор для защиты дополнений:

if (ts.insert (value).second) {
    // insertion took place
    realContainer.push_back (value);
}

Альтернативой является то, что в зависимости от того, как часто вы будете изменять записи в наборе, вы, вероятно, можете проверить, будет ли запись находиться в другом месте (с помощью функции сравнения набора) и где позиция переместится, затем удалите старую запись и заново добавьте новую.

Как и все остальные отмечали - неупорядоченный набор действительно пахнет плохо - и я бы также предположил, что его возможное получило неопределенное поведение согласно стандарту

Answer 5

Я согласен с другими ответами, что это сломается некоторыми странными и трудными для отладки способами. Если вы идете по пути обновления, вам нужно сделать копию только один раз. Создайте набор tmp с новой стратегией сортировки, добавьте каждый элемент из исходного набора в набор tmp, затем выполните

 orig.swap(tmp);

Это поменяет местами наборы.

Если бы это был я, я бы обернул это в новый класс, который обрабатывает все детали, чтобы вы могли изменять реализации по мере необходимости. В зависимости от ваших шаблонов доступа и количества изменений порядка сортировки, может быть предпочтительнее упомянутое ранее векторное решение, сортировка с нижним пределом.

Answer 6

Это на самом деле зависит от реализации.
Реализация STL может и обычно предполагает, что предикат, используемый для сортировки, стабилен (в противном случае «отсортированный» не будет определен) По крайней мере возможно создать допустимую реализацию STL, которая форматирует ваш жесткий диск, когда вы изменяете поведение экземпляра предиката.

Итак, да, вам нужно заново вставить предметы в новый набор.

Кроме того, вы можете создать свой собственный контейнер, например, вектор + сортировка + нижняя граница для бинарного поиска. Затем вы можете выполнить повторную сортировку при изменении поведения предикатов.

Answer 7

Это может привести к потере записей, когда при поиске элемента в set используется оператор упорядочения, это означает, что если элемент был размещен слева от корня, а теперь оператор упорядочения говорит, что справа, то элемент больше не будет найден.

Answer 8

Просто продолжение:

Во время выполнения этого кода библиотеки отладки Visual Studio C начали выдавать исключения, сообщающие, что оператор «<» недопустим. </p>

Итак, похоже, что изменение порядка сортировки - это плохо. Спасибо всем!

Answer 9

Вот простой тест для вас:

struct comparer : public std::binary_function<int, int, bool>
{
  static enum CompareType {CT_LESS, CT_GREATER} CompareMode;
  bool operator()(int lhs, int rhs) const
  {
    if(CompareMode == CT_LESS)
    {
      return lhs < rhs;
    }
    else
    {
      return lhs > rhs;
    }
  }
};

comparer::CompareType comparer::CompareMode = comparer::CT_LESS;

typedef std::set<int, comparer> is_compare_t;

void check(const is_compare_t &is, int v)
{
  is_compare_t::const_iterator it = is.find(v);
  if(it != is.end())
  {
    std::cout << "HAS " << v << std::endl;
  }
  else
  {
    std::cout << "ERROR NO " << v << std::endl;
  }
}

int main()
{
  is_compare_t is;
  is.insert(20);
  is.insert(5);
  check(is, 5);
  comparer::CompareMode = comparer::CT_GREATER;
  check(is, 5);
  is.insert(27);
  check(is, 27);
  comparer::CompareMode = comparer::CT_LESS;
  check(is, 5);
  check(is, 27);
  return 0;
}

Итак, если вы намереваетесь найти элементы, которые вы вставили, вы не должны изменять предикат, используемый для вставок, и находить.

Answer 10

1) Вредно - нет. Результата аварий - нет. Худшее действительно несортированное множество.

2) «Обновление» будет таким же, как и повторное добавление!