std::random_shuffle 可以使用哪些容器？

Question

哪些容器可以与 std::random_shuffle( RandomIt first, RandomIt last ) 一起使用？

API description 说这两个迭代器需要是随机访问迭代器——我想我不清楚随机访问迭代器是什么，具体来说，为什么 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 class 成员，它将告诉您迭代器类型，在本例中为 BidirectionalIterator。（为此可以忽略 "legacy" 位）。

对于 random_shuffle 它需要是 RandomAccessIterator 这意味着迭代器可以在任何整数大小的跳跃中移动（或者换句话说，容器元素可以在恒定时间内通过整数索引）。

这对于 vector 是可能的（从开始处偏移一个索引），但对于 set 是不可能的，因为到达第 N 个元素的唯一方法是遍历元素一次一步（因为它存储为一棵树）。

关于迭代器的更多信息：Types of iterator : Output vs. Input vs. Forward vs. Random Access Iterator

我在容器标准与迭代器类型中找不到 table，但是如果您查看 this container property table 那么任何支持 operator[] 整数索引的容器是随机访问，否则不是。那就是 <array>、<vector> 和 <deque>。（map 以不同的方式使用 operator[]）。还有 <string> 没有出现在 table 中，当然还有任何提供随机访问迭代器的用户定义容器。

注意。 set 是一个已排序的容器，所以无论如何都不能随机洗牌。

std::random_shuffle 可以使用哪些容器？

What containers are valid to use with std::random_shuffle?

c++

containers

stl

shuffle

random-access