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

Question

Какие контейнеры допустимы для использования с 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;
}

Answer 1

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

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

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

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

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

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