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

StackOverflow https://stackoverflow.com/questions/239588

  •  04-07-2019
  •  | 
  •  

Вопрос

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

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

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

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

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

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

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

Есть какие-нибудь идеи?

Спасибо,

Джон

Это было полезно?

Решение

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

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

Так что это делает вред.

Другие советы

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

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

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

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

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

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

 orig.swap(tmp);

Это приведет к замене внутренних элементов наборов.

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

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

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

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

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

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

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

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

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

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

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;
}

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

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

Во время выполнения этого кода библиотеки отладки Visual Studio C начали выдавать исключения, жалуясь на то, что "<"оператор был недействителен.

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

1) Вредный - нет.Привести к сбоям - нет.Худшее - это действительно несортированный набор.

2) "Обновление" в любом случае было бы таким же, как повторное добавление!

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top