Equivalent to python's set.pop() for C++'s unordered sets

Question

Does C++ have an equivalent to python's set.pop()? I've been looking at the documentation for unordered_sets here, but there doesn't seem to be a way to 1. Access an arbitrary element, and/or 2. Access + remove an arbitrary element (popping).

Donne

Since it is unordered, isn't begin() and end() "arbitrary" by definition? Python is probably doing something similar under the covers. – Myocardium

True... I might just stick with that implementation of my program. – Donne

Answer 1

You can either pop the first element

auto i = *set.begin();
set.erase(set.begin());

or if you're overly concerned about the implementation-defined internal ordering of the buckets (hint: you probably shouldn't be), you could remove a random element with something like

#include <unordered_set>
#include <iostream>
#include <random>

int main()
{
  std::unordered_set<int> set{0, 1, 2, 3, 4, 5};
  std::default_random_engine ran{std::random_device{}()};

  auto it = set.begin();
  std::advance(it, std::uniform_int_distribution<>{0, set.size() - 1}(ran));

  std::cout << *it << '\n';
  set.erase(it);
}

The above isn't particularly efficient however and you might be better off by filling a std::vector, removing the duplicates, randomizing the order and then just pop_backing the elements.

#include <algorithm>
#include <vector>
#include <iostream>
#include <random>

int main()
{
  std::vector<int> vec{0, 1, 2, 3, 3, 4, 5, 5};
  std::sort(vec.begin(), vec.end());
  vec.erase(std::unique(vec.begin(), vec.end()), vec.end());

  std::shuffle(
    vec.begin(), 
    vec.end(), 
    std::default_random_engine{std::random_device{}()}
  );

  while (!vec.empty()) {
    std::cout << vec.back() << '\n';
    vec.pop_back();
  }
}

(n.b. depending on your platform random_device may not be a very good seed).

Arrow

Answer 2

Note that the C++ standard library is intentionally designed so that the various container specifications do not include a "get and remove" function: e.g. for vector, you have back() which returns the value at the end, and you have pop_back() which removes the value at the end, but does not return it.

The reasons for this could well be the content of a separate question.

So what you actually want is a method to obtain an element (e.g. begin() as suggested in the comments), and then to remove it once you've gotten it (e.g. erase(iterator) as mentioned in the other answer).

Facetiae

any reference to reasons of that intention by the standard? – Gatto

Answer 3

The equivalent is unordered_set.erase I think. http://www.cplusplus.com/reference/unordered_set/unordered_set/erase/

Footstalk