9

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

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

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

据推测，集合中的项目将不再按顺序排列。

所以真的有两个问题：

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

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

有任何想法吗？

谢谢，

约翰

4

10 回答 10

7

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

它将违反类不变量，即每个项目仅存在一次。

所以它是有害的。

于 2008-10-27T11:38:55.203 回答
4

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

std::set<int> newset( oldset.begin(), oldset.end(), NewPred() );
于 2008-10-27T16:10:02.690 回答
2

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

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

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

于 2008-10-27T11:41:18.257 回答
2

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

 orig.swap(tmp);

这将交换集合的内部结构。

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

于 2008-10-27T12:25:27.060 回答
2

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

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

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

另一种选择是，根据您修改集合中条目的频率，您可能可以测试该条目是否位于不同的位置（通过使用集合比较功能）以及该位置将移动到哪里删除旧条目并重新添加新条目。

正如其他人所指出的那样——无序的集合真的很难闻——而且我也猜想它可能会根据标准得到未定义的行为。

于 2008-10-27T12:30:15.163 回答
2

虽然这并不能完全满足您的需求，但boost::multi_index为您提供了类似的功能。由于模板的工作方式，您将永远无法“更改”容器的排序谓词，它在编译时是一成不变的，除非您使用排序向量或类似的东西，您是维护者不变量，您可以在任何给定时间随意排序。

然而，Multi_index 为您提供了一种同时基于多个排序谓词对一组元素进行排序的方法。然后，您可以选择容器的视图，这些视图的行为类似于您当时关心的谓词排序的 std::set。

于 2008-10-27T13:07:52.887 回答
1

这可能会导致条目丢失，当在排序运算符中搜索元素时，set这意味着如果一个元素被放置在根的左侧，而现在排序运算符说它在右侧，那么将不再找到该元素.

于 2008-10-27T11:36:34.083 回答
0

这是一个简单的测试：

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

因此，基本上，如果您打算能够找到曾经插入的元素，则不应更改用于插入和查找的谓词。

于 2008-10-27T13:48:58.967 回答
0

只是一个跟进：

运行此代码时，Visual Studio C 调试库开始抛出异常，抱怨“<”运算符无效。

因此，更改排序顺序似乎是一件坏事。谢谢大家！

于 2008-10-31T09:53:35.290 回答
-3

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

2）无论如何，“刷新”与重新添加相同！

于 2008-10-27T11:20:05.477 回答