C++23 flat_set 中的元素是排序的还是堆？

Question

我阅读了提案文件p1222r4.pdf，但如您所知，它们有时有点难以阅读。我还找到了社区页面 cppreference 和 boost 文档。

我知道我可以迭代集合中的元素，并且它们按顺序出现：

#include <iostream>
#include <random>
//#include <flat_set>    // no compiler support yet
#include <boost/container/flat_set.hpp>

using namespace std;
default_random_engine engine{};
mt19937 gen{engine()};

int main() {
    uniform_int_distribution<> rand_a(0, 100);
    auto roll_a = [&] { return rand_a(gen); };
    boost::container::flat_set<int> demo{};
    for (int i = 0; i < 30; ++i) {
        demo.insert(roll_a());
    }

    // iterate -- sorted, thats clear.
    for(const auto& elem : demo) {
        cout << elem << " ";
    }
    cout << "\n";
    //= 6 8 16 22 26 27 30 34 36 40 41 45 47 50 52 53 56 61 66 67 ...

    // get to the internals. still sorted? or a heap?
    auto seq = demo.extract_sequence(); // or extract() in the std.
    for(const auto& elem : seq) {
        cout << elem << " ";
    }
    cout << "\n";
    //= 6 8 16 22 26 27 30 34 36 40 41 45 47 50 52 53 56 61 66 67 ...
}

但是还有令人惊奇的

extract

方法（或 boost 中的

extract_sequence

）来了解集合的内部结构。

所以，我似乎记得一些

flat_set

的实现不保持键严格排序，而是作为堆，这样效率更高一些。

但是我在标准文档中没有找到任何提及这一点的内容。找不到它并不能证明，所以，我是否忽略了什么？

问题：

extract

方法是否保证返回排序的容器？

Answer 1

性能规格（插入和擦除是线性）、可用的唯一化行为以及随机访问迭代器将按排序顺序迭代的事实都排除了堆的使用。满足规范所有要求的唯一合理的实现是在引擎盖下排序的

vector

（或您模板化的任何替代

KeyContainer

）。