STL排序集，其中订单的条件可能会发生变化

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

  •  04-07-2019
  •  | 
  •  

题

我有一个定义了自定义排序的C ++ STL集。

这个想法是，当项目被添加到集合中时，它们会按照我的要求自然排序。

但是，我刚刚意识到，排序谓词可以随着时间的推移而改变。

据推测，集合中的项目将不再有序。

真的有两个问题：

  1. 这些物品会出现故障是否有害？我是否正确地说，可能发生的最坏情况是新条目可能被放入错误的地方（实际上我可以忍受）。或者，这会导致崩溃，丢失条目等吗？

  2. 有没有办法<！>“刷新<！>”;集合的顺序？您似乎无法在集合上使用std :: sort（）。我能想到的最好的方法是将内容转储到临时容器中并重新添加。

    3. 有什么想法吗？

    谢谢，

    约翰

有帮助吗？

解决方案

set使用排序来查找项目。如果您根据ordering1插入N个项目并根据orders2插入项目，则该集合无法确定该项目是否已经存在。

它会违反每个项目只存在一次的类不变量。

所以它 伤害。

其他提示

使用STL执行此操作的唯一安全方法是使用更改的谓词创建新集。例如，当您需要使用新谓词对集合进行排序时，您可以执行类似的操作：

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

这实际上取决于实现。
STL实现可以并且通常将假设用于排序的谓词是稳定的（否则，<！>“排序的<！>”将不被定义）。至少可以构建一个有效的STL实现，在您更改谓词实例的行为时格式化硬盘驱动器。

所以，是的，你需要将这些项重新插入一个新的集合中。

或者，您可以构建自己的容器，例如二进制搜索的向量+ sort + lower_bound。然后，您可以在谓词行为发生变化时重新排序。

我同意其他答案，这将在一些奇怪且难以调试的方式中突破。如果你去刷新路线，你只需要复制一次。使用新的排序策略创建tmp集，将原始集中的每个元素添加到tmp集，然后执行

 orig.swap(tmp);

这将交换集合的内部。

如果这是我，我会将其包装在一个处理所有细节的新类中，以便您可以根据需要更改实现。根据您的访问模式和排序顺序更改的次数，前面提到的矢量，排序，下限解决方案可能更合适。

如果您可以使用无序集合，那么为什么要将它们添加到集合中呢？

我能想到的唯一情况是，您只想在添加列表时确保列表是唯一的。如果是这种情况，那么您可以使用临时集来保护添加内容：

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

另一种方法是，根据您修改集合中条目的频率，您可以测试以查看条目是否位于不同的位置（通过使用设置比较功能）和位置将移动然后删除旧条目并重新添加新条目。

正如其他人所指出的那样 - 让无序的集合真的闻起来很糟糕 - 而且我也猜测它可能会根据标准获得未定义的行为。

虽然这并不能完全满足您的需求，但 boost :: multi_index 为您提供类似的功能。由于模板的工作方式，您永远无法<！>更改<！>一个容器的排序谓词，它在编译时设置，除非你使用一个排序的向量或类似的东西，你是维护不变量的那个，你可以对它进行排序你想要在任何特定的时间。

然而，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调试库开始抛出异常，抱怨<！>“<！> lt; <！>”;运营商无效。

所以，似乎改变排序顺序似乎是件坏事。谢谢大家！

1）有害 - 没有。导致崩溃 - 没有。最糟糕的确是一个未排序的集合。

2）<！>“;刷新<！>”;无论如何都会像重新添加一样！

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top