Какие контейнеры можно использовать с std::random_shuffle?

Какие контейнеры можно использовать с std::random_shuffle( RandomIt first, RandomIt last )?

В описании API говорится, что два итератора должны быть итераторами с произвольным доступом. Наверное, я не понимаю, что такое итератор с произвольным доступом и, в частности, почему std::vector::begin() и ::end() есть, а то же самое из std::set и std::unordered_set нет.

#include <algorithm>
#include <set>
#include <unordered_set>
#include <vector>

int main( int argc, char* argv[] )
{
  std::set<int> s = { 1, 2, 3, 4, 5 };
  std::unordered_set<int> u = { 1, 2, 3, 4, 5 };
  std::vector<int> v = { 1, 2, 3, 4, 5 };

  std::random_shuffle( s.begin(), s.end() ); // compile error
  std::random_shuffle( u.begin(), u.end() ); // compile error
  std::random_shuffle( v.begin(), v.end() ); // :)

  return 0;
}

c++ containers shuffle stl random-access
person StoneThrow    schedule 11.04.2020    source источник
comment
Не используйте std::random_shuffle. Он устарел в C++14 и удален в C++17. Вместо этого используйте std::shuffle.   -  person BessieTheCookie    schedule 11.04.2020

Ответы (1)


arrow_upward
3
arrow_downward

Если вы посмотрите на set, а затем на член класса iterator, он сообщит вам тип итератора, в данном случае BidirectionalIterator. (Для этой цели бит «устаревший» можно не принимать во внимание).

Для random_shuffle он должен быть RandomAccessIterator, что означает, что итератор можно перемещать скачками любого целочисленного размера (или, другими словами, доступ к элементам контейнера можно получить за постоянное время по целочисленному индексу).

Это возможно для vector (смещение по индексу от начала), но невозможно для set, где единственный способ добраться до N-го элемента - это пройти по элементам по одному шагу за раз (поскольку он хранится в виде дерева) .

Дополнительная информация об итераторах: Типы итераторов : вывод, ввод, перенаправление, итератор с произвольным доступом

Я не смог найти таблицу в стандарте контейнеров и типов итераторов, однако, если вы посмотрите на этой таблице свойств контейнера, то любой контейнер, который поддерживает operator[] для целочисленного индекса, является случайным доступом, в противном случае это не так. Итак, это <array>, <vector> и <deque>. (В maps оператор [] используется по-другому). Также есть <string>, которого нет в этой таблице, плюс любой пользовательский контейнер, который, конечно, предлагает итераторы произвольного доступа.

NB. set — это отсортированный контейнер, поэтому его нельзя перетасовать случайным образом.

person M.M    schedule 11.04.2020