Element at index in a std::set?

Question

I've stumbled upon this problem: I can't seem to select the item at the index' position in a normal std::set. Is this a bug in STD?

Below a simple example:

#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!
}

Anything I can do to fix the issue?

Answer 1

Try this you will be able to use set in another way namely ordered_set

This is very much used in CP

Hope this is diff from all and will help you/someone!

#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>

Now you can use

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 2

i believe the most optimal way, especially if this indexing happens in a loop, is to convert to a vector.

auto my_vect = std::vector(my_set.begin(), my_set.end()); // O[n]
int output = my_vect[n]; // O[1]

Answer 3

I don't think std::set has any methods of doing this in better than O(n) time, but I recently made this data structure using a set and a Binary Index Tree that can do most things the std::set can do, but it can also get the index of an element in O(log n) time, as well as the element at a specific index in O((log n) * (log n)) time:

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

This set does have some flaws since it marks elements in the Binary Indexed Tree, so the elements cannot be negative or really big without some extra modifications, but it can still be helpful in some cases. Also, using an std::map or some other type of map could make the set work with negative numbers, big numbers, as well as other data types, but this would increase the runtime by a factor of O(log n) and I think you would have to know all the elements that could appear in the set beforehand so that you can store them in the correct order inside of the map.

EDIT: I just realized there is already a policy-based data structure called ordered-set that has the same functions as a set but can do the two operations (get element at index and get index of element) in O(log n). Read more here: https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/. This might not work in all compilers though

Answer 4

There is no way you can access it in constant time.

But you can reach to any element in O(n) time. E.g.

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

Answer 5

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

Edit: Edited code. You can't access set using index but the above method would provide an "index" i if you want to copy the elements from set into an array, provided you have created an array of sufficient size before hand.

Answer 6

Sometimes there's a good reason for needing a set you can index into. I had to implement this functionality recently to support a legacy API which has functions to return the number of items, and the item at an index, so that the caller can enumerate the items.

My way of solving the problem is to use std::vector, and use std::equal_range to find and insert or delete items in the set. For example, inserting a new item into the set looks like this:

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

Deleting is very similar: use equal_range to find the item, and if range.first is not equal to range.second, delete that range.

Answer 7

This is not a bug in the STD. There is no random access in a std::set. If you need random access by index, you can use std::vector

Answer 8

It doesn't cause a crash, it just doesn't compile. set doesn't have access by index.

You can get the nth element like this:

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

Assuming my_set.size() > n, of course. You should be aware that this operation takes time approximately proportional to n. In C++11 there's a nicer way of writing it:

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

Again, you have to know that n is in bounds first.

Answer 9

A usual implementation of std::set is to use binary search trees, notably self-balancing binary search trees such as red-black trees

They don't give you constant time access to the n-th element. However, you seems to want the first. So try in C++11:

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