STL集合是否可以强制重新评估谓词？

Question

考虑以下数据结构和代码。

struct Sentence {
    std::string words;
    int frequency;
    Sentence(std::string words, int frequency) : words(words), frequency(frequency) {}
};
struct SentencePCompare {
    bool operator() (const Sentence* lhs, const Sentence* rhs) const {
        if (lhs->frequency != rhs->frequency) {
            return lhs->frequency > rhs->frequency;
        }
        return lhs->words.compare(rhs->words) < 0;
    }
};
std::set<Sentence*, SentencePCompare> sentencesByFrequency;

int main(){
    Sentence* foo = new Sentence("foo", 1);
    Sentence* bar = new Sentence("bar", 2);
    sentencesByFrequency.insert(foo);
    sentencesByFrequency.insert(bar);
    for (Sentence* sp : sentencesByFrequency) {
        std::cout << sp->words << std::endl;
    }
    foo->frequency = 5;
    for (Sentence* sp : sentencesByFrequency) {
        std::cout << sp->words << std::endl;
    }
}

以上代码的输出结果如下。

bar
foo
bar
foo

正如我们所预期的那样，当集合中指向指针的对象被更新时，即使谓词根据它们所指向的对象对指针进行排序，集合也不会自动重新评估谓词。

有没有一种方法可以强制 std::set 重新评估谓词，以便顺序再次正确？

- merlin2011

---

也许 std::set 并不是适合你使用情况的容器类型？因为键（keys）应该是常量，所以没有必要进行重新排序。 - Some programmer dude

如果集合很少被访问，或者即使修改稍后可能再次发生，但它们与读取相当分离，那么将其保持无序并由例如vector表示可能是有意义的，然后在每次使用之前立即对其进行排序。 - Alex Celeste

@Someprogrammerdude，你有没有另一种数据结构的建议？ - merlin2011

另外，“SentencePCompare”不是一个正确的顺序。将“compare”的返回类型强制转换为“bool”是代码异味。 - Yakk - Adam Nevraumont

@Yakk-AdamNevraumont，那其实是我刚刚发现的一个bug。我已经在上面的代码中修复了它。 - merlin2011

Answer 1

不行。

这就是为什么set只允许对其元素进行const访问的原因。如果您通过使用浅层次的const指针和自定义谓词绕过此限制，然后通过以影响排序的方式修改指针来破坏不变量，您将付出被鼻子恶魔侵扰的代价。

在C++17之前，您需要erase并再次insert，这会导致键复制加上节点释放和分配。在C++17之后，您可以extract节点，修改它，并重新插入它，这是免费的。

- T.C.

---

你可以直接使用 extract 函数进行提取。 - T.C.

并不是真正的自由，它避免了重新分配节点的成本，但仍需要重新计算新节点应该在哪里，这需要大约对数时间。 - user202729

是的，如果你想要一个连贯的数据结构，那么维护不变量的基本成本就是你无论做什么都需要支付的。 - T.C.