std :: set中索引处的元素？

Question

我偶然发现了这个问题:我似乎无法在正常的索引位置选择项目std::set.这是性病的一个错误吗？

下面一个简单的例子:

#include <iostream>
#include <set>

int main()
{
    std::set<int> my_set;
    my_set.insert(0x4A);
    my_set.insert(0x4F);
    my_set.insert(0x4B);
    my_set.insert(0x45);

    for (std::set<int>::iterator it=my_set.begin(); it!=my_set.end(); ++it)
        std::cout << ' ' << char(*it);  // ups the ordering

    //int x = my_set[0]; // this causes a crash!
}

我能做些什么来解决这个问题？

Answer 1

它不会导致崩溃,它只是不编译.set没有索引访问权限.

你可以得到这样的第n个元素:

std::set<int>::iterator it = my_set.begin();
std::advance(it, n);
int x = *it;

my_set.size() > n当然,假设.您应该知道此操作需要的时间大致成比例n.在C++ 11中有一种更好的编写方式:

int x = *std::next(my_set.begin(), n);

同样,你必须首先知道它n是在界限内.

Answer 2

尝试一下，您将能够以另一种方式使用集合，即ordered_set

这个CP用得非常多

希望这与所有人不同，并对您/某人有所帮助！

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>

现在你可以使用

order_of_key (k) : Number of items strictly smaller than k .
find_by_order(k) : K-th element in a set (counting from zero). //This is what you need 


[https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/][1]

Answer 3

您无法在恒定时间内访问它。

但你可以在 O(n) 时间内到达任何元素。例如

std::set<int>::iterator it;
it=my_set.begin();
advance(it,n);
cout<<*it;

Answer 4

std :: set的通常实现是使用二叉搜索树,特别是自平衡二叉搜索树,例如红黑树

他们没有给你恒定的时间访问第n个元素.但是,你似乎想要第一个.所以在C++ 11中尝试:

auto it = my_set.begin();
int first=0;
if (it != my_set.end()) first = *it;