我遇到了这个问题：在普通的std::set中，我似乎无法选择索引位置上的项。这是STD的错误吗？
以下是一个简单的示例：
#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!
}
有什么我可以做来解决这个问题吗？
它不会导致崩溃，只是无法编译。 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是否在范围内。
my_set[0]返回0x4A，这仍然不能达到预期的效果。 - Useless尝试一下，你将能够以另一种方式使用 set，即 ordered_set
这在竞赛编程中非常常见
希望这对所有人都有所帮助！
#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]
你无法以常数时间访问它。
但是你可以在O(n)时间内访问任何元素。 例如：
std::set<int>::iterator it;
it=my_set.begin();
advance(it,n);
cout<<*it;
我认为std::set没有比O(n)更好的方法来实现这个功能，但是最近我使用了一个集合和一棵二进制索引树来创建这个数据结构。它可以完成std::set能做的大多数事情，而且可以在O(log n)时间内获取元素的索引，以及在O((log n) * (log n))时间内获取特定索引处的元素：
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define max(n, m) ((n>m)?n:m)
#define min(n, m) ((n<m)?n:m)
#define f first
#define s second
struct ss
{
// binary index tree (to mark elements)
int bit[1000010]; // set this number to the max you will use
// set (to store the numbers in order)
set<int> nums;
// the maximum element in the set (NOTE: this data structure works with marking in the BIT array, but you can make this better by using an unordered set to store all values that could appear inside of the set, but this will increase runtime by a high constant factor)
int mx;
// constructor
ss(int maxEl)
{
mx = maxEl + 5;
}
int sum(int arr[], int idx)
{
int ans = 0;
idx ++;
if(idx > mx + 5) return -1;
while(idx > 0)
{
ans += arr[idx];
idx -= idx & (-idx);
}
return ans;
}
void update(int arr[], int idx, int val, int size)
{
idx ++;
while(idx <= size)
{
arr[idx] += val;
idx += idx & (-idx);
}
}
int bs(int l, int r, int idx)
{
int mid = (l + r) / 2;
if(l == r) return mid + 1;
if(l == r - 1)
{
if(sum(bit, r) == idx) return r + 1;
return r;
}
if(sum(bit, mid) <= idx) return bs(mid, r, idx);
return bs(l, mid - 1, idx);
}
// regular set functions
set<int>::iterator find(int num) { return nums.find(num); }
set<int>::iterator lower_bound(int num) { return nums.lower_bound(num); }
set<int>::iterator upper_bound(int num) { return nums.upper_bound(num); }
int size() { return (int)nums.size(); }
set<int>::iterator begin() { return nums.begin(); }
set<int>::iterator end() { return nums.end(); }
bool empty() { return nums.empty(); }
// slightly modified insert and erase functions to also mark stuff in BIT (still O(log n) though)
void insert(int num)
{
if(nums.find(num) == nums.end())
update(bit, num, 1, mx); // marks the element in the BIT if it doesn't already exist
nums.insert(num);
}
void erase(int num)
{
if(nums.find(num) != nums.end())
update(bit, num, -1, mx); // unmarks the element in the BIT if it exists in the set
nums.erase(num);
}
// gets index (0-indexed) of a specific element in O(log n), returns -1 if element not in set
int idx(int num)
{
if(nums.find(num) == nums.end())
return -1;
return sum(bit, num - 1);
}
// gets the iterator of the element at a specific index (0-indexed) in O((log n) * (log n)), returns end of set if idx is invalid
set<int>::iterator at(int idx)
{
if(idx < 0 || idx >= nums.size())
return nums.end();
return nums.find(bs(0, mx, idx));
}
};
int main()
{
ss test = ss(1000);
test.insert(1);
test.insert(3);
test.insert(5);
test.insert(1);
test.insert(9);
test.insert(1000);
cout << *test.at(1) << "\n";
test.erase(3);
cout << *test.at(1) << "\n";
cout << test.idx(1) << "\n";
cout << *test.at(-1) << "\n";
}
std :: map或某种其他类型的映射可以使该集合与负数、大数以及其他数据类型一起工作，但这将使运行时间增加一个O(log n)的因子，而且您必须预先知道可能出现在集合中的所有元素，以便可以按正确的顺序将它们存储在映射内。O(log n)的时间内执行两个操作（获取索引处的元素和获取元素的索引）。在此处阅读更多信息：https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/。但这可能不适用于所有编译器。std::less 来排序。 - chrisstd::unordered_set。已经修改过了。 - José D.std::less，除非另有说明，在int的情况下只是一种花哨的方式来表示<。 - Steve Jessopauto my_vect = std::vector(my_set.begin(), my_set.end()); // O[n]
int output = my_vect[n]; // O[1]
std:vector<std::string> my_set;
...
std::string new_item("test");
auto range = std::equal_range(my_set.begin(),my_set.end(),new_item);
if (range.first == range.second)
my_set.insert(range.first,new_item);
删除操作与插入操作十分相似：使用 equal_range 找到目标项，如果 range.first 不等于 range.second，则删除此范围。
std::set<int> my_set;
my_set.insert(0x4A);
my_set.insert(0x4F);
my_set.insert(0x4B);
my_set.insert(0x45);
int arr[my_set.size()];
set<int>::iterator it = my_set.begin();
for (int i = 0; i < my_set.size(); i++) {
arr[i] = *it;
it++;
}
cout << arr[0];
编辑：已编辑代码。您无法使用索引访问集合，但上述方法将提供一个“索引”i，如果您想将元素从集合复制到数组中，前提是您事先创建了足够大小的数组。
my_set[0]不应该被编译。 - chris