当前位置：文江博客话题详情

STL排序集，其中顺序条件可能会改变

发布于 2024-07-08 23:35:57 字数 410 浏览 2 评论 0原文

我有一个 C++ STL 集，其中定义了自定义顺序。

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

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

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

所以有两个问题：

物品出现故障是否有害？我是否正确地说，可能发生的最糟糕的情况是新条目可能会被放入错误的位置（实际上我可以忍受）。或者，这会导致崩溃、丢失条目等吗？
有没有办法“刷新”集合的顺序？您似乎无法在集合上使用 std::sort() 。我能想到的最好办法是将内容转储到临时容器中并重新添加它们。

有任何想法吗？

谢谢，

约翰

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

对不⑦ 2024-07-15 23:35:57

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

这将违反每个项目仅在其中一次的类不变量。

所以它确实有害。

回复收藏 0 原文

口干舌燥 2024-07-15 23:35:57

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

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

The only safe way to do this with the STL is to create a new set with the changed predicate. For example you could do something like this when you needed to sort the set with a new predicate:

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

回复收藏 0 原文

舞袖。长 2024-07-15 23:35:57

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

所以，是的，您需要将项目重新插入到新集合中。

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

回复收藏 0 原文

╭⌒浅淡时光〆 2024-07-15 23:35:57

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

 orig.swap(tmp);

此操作，这将交换集合的内部结构。

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

I agree with the other answers, that this is going to break in some strange and hard to debug ways. If you go the refresh route, you only need to do the copy once. Create a tmp set with the new sorting strategy, add each element from the original set to the tmp set, then do

 orig.swap(tmp);

This will swap the internals of the sets.

If this were me, I would wrap this up in a new class that handles all of the details, so that you can change implementations as needed. Depending on your access patterns and the number of times the sort order changes, the previously mentioned vector, sort, lowerbound solution may be preferable.

回复收藏 0 原文

梦里寻她 2024-07-15 23:35:57

如果您可以接受无序的集合，那么为什么首先要将它们添加到集合中呢？

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

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

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

正如其他人所指出的那样 - 让集合无序确实很难闻 - 而且我也猜测根据标准，它可能会出现未定义的行为。

If you can live with an unordered set, then why are you adding them into a set in the first place?

The only case I can think of is where you just want to make sure the list is unique when you add them. If that's the case then you could use a temporary set to protect additions:

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

An alternative, is that depending on how frequently you'll be modifying the entries in the set, you can probably test to see if the entry will be in a different location (by using the set compare functionality) and where the position will move then remove the old entry and re-add the new one.

As everyone else has pointed out - having the set unordered really smells bad - and I would also guess that its possible got undefined behaviour according to the std.

回复收藏 0 原文

爱*していゐ 2024-07-15 23:35:57

虽然这并不能完全满足您的需求， boost::multi_index 为您提供类似的功能。由于模板的工作方式，您将永远无法“更改”容器的排序谓词，它在编译时就已确定，除非您使用排序向量或类似的东西，您< /em> 是保持不变的，您可以在任何给定时间对它进行排序。

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

回复收藏 0 原文

情话墙 2024-07-15 23:35:57

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

回复收藏 0 原文

小瓶盖 2024-07-15 23:35:57

这是一个简单的测试：

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

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

Here's a simple test for you:

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

So, basically if you intend to be able to find the elements you once inserted you should not change the predicate used for insertions and find.

回复收藏 0 原文