Index: include/algorithm
===================================================================
--- include/algorithm
+++ include/algorithm
@@ -3088,7 +3088,7 @@
     {
         _Dp __uid;
         __rs_default __g = __rs_get();
-        for (--__last, --__d; __first < __last; ++__first, --__d)
+        for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
         {
             difference_type __i = __uid(__g, _Pp(0, __d));
             if (__i != difference_type(0))
@@ -3110,7 +3110,7 @@
     difference_type __d = __last - __first;
     if (__d > 1)
     {
-        for (--__last; __first < __last; ++__first, --__d)
+        for (--__last; __first < __last; ++__first, (void) --__d)
         {
             difference_type __i = __rand(__d);
             swap(*__first, *(__first + __i));
Index: test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle.pass.cpp
===================================================================
--- test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle.pass.cpp
+++ test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle.pass.cpp
@@ -17,14 +17,44 @@
 #include <algorithm>
 #include <cassert>
 
-int main()
+#include "test_iterators.h"
+
+void test_initial_sequence()
 {
     int ia[] = {1, 2, 3, 4};
     int ia1[] = {1, 4, 3, 2};
     int ia2[] = {4, 1, 2, 3};
     const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+
     std::random_shuffle(ia, ia+sa);
     assert(std::equal(ia, ia+sa, ia1));
+
     std::random_shuffle(ia, ia+sa);
     assert(std::equal(ia, ia+sa, ia2));
 }
+
+template <class Iter>
+void
+test_with_iterator()
+{
+    int empty[] = {};
+    std::random_shuffle(Iter(empty), Iter(empty));
+
+    int all_elements[] = {1, 2, 3, 4};
+    int shuffled[] = {1, 2, 3, 4};
+    const unsigned size = sizeof(all_elements)/sizeof(all_elements[0]);
+
+    std::random_shuffle(Iter(shuffled), Iter(shuffled+size));
+    assert(std::is_permutation(shuffled, shuffled+size, all_elements));
+
+    std::random_shuffle(Iter(shuffled), Iter(shuffled+size));
+    assert(std::is_permutation(shuffled, shuffled+size, all_elements));
+}
+
+int main()
+{
+    test_initial_sequence();
+    test_with_iterator<random_access_iterator<int*> >();
+    test_with_iterator<int*>();
+}
+
Index: test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle_rand.pass.cpp
===================================================================
--- test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle_rand.pass.cpp
+++ test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle_rand.pass.cpp
@@ -18,20 +18,87 @@
 #include <algorithm>
 #include <cassert>
 
+#include "test_iterators.h"
+
+struct min_swappable {
+    int value;
+    min_swappable(int value) : value(value) {}
+    min_swappable(const min_swappable&) = delete;
+    void operator=(const min_swappable&) = delete;
+
+    static int swaps;
+};
+
+int min_swappable::swaps = 0;
+
+void swap(min_swappable& lhs, min_swappable& rhs)
+{
+    std::swap(lhs.value, rhs.value);
+    ++min_swappable::swaps;
+}
+
+bool operator==(const min_swappable& lhs, const min_swappable& rhs)
+{
+    return lhs.value == rhs.value;
+}
+
+struct init_gen {};
+
 struct gen
 {
+    gen(init_gen) {}
+
+    gen(const gen&) = delete;
+    void operator=(const gen&) = delete;
+
+    static int calls;
+
     int operator()(int n)
     {
+        ++calls;
         return n-1;
     }
 };
 
+int gen::calls = 0;
+
+template <class Iter, class ValueType>
+void
+test_with_iterator()
+{
+    gen::calls = 0;
+
+    ValueType empty[] = {};
+    std::random_shuffle(Iter(empty), Iter(empty));
+    assert(gen::calls == 0);
+
+    ValueType shuffled[] = {{1}, {2}, {3}, {4}};
+    ValueType shuffled1[] = {{4}, {1}, {2}, {3}};
+    ValueType shuffled2[] = {{3}, {4}, {1}, {2}};
+    const unsigned size = sizeof(shuffled)/sizeof(shuffled[0]);
+    gen r(init_gen{});
+
+    std::random_shuffle(Iter(shuffled), Iter(shuffled+size), r);
+    assert(std::equal(shuffled, shuffled+size, shuffled1));
+    assert(gen::calls == 3);
+
+    std::random_shuffle(Iter(shuffled), Iter(shuffled+size), r);
+    assert(std::equal(shuffled, shuffled+size, shuffled2));
+    assert(gen::calls == 6);
+}
+
 int main()
 {
-    int ia[] = {1, 2, 3, 4};
-    int ia1[] = {4, 1, 2, 3};
-    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
-    gen r;
-    std::random_shuffle(ia, ia+sa, r);
-    assert(std::equal(ia, ia+sa, ia1));
+    min_swappable::swaps = 0;
+    test_with_iterator<random_access_iterator<min_swappable*>, min_swappable >();
+    assert(min_swappable::swaps == 6);
+
+    test_with_iterator<random_access_iterator<int*>, int >();
+
+    min_swappable::swaps = 0;
+    test_with_iterator<min_swappable*, min_swappable>();
+    assert(min_swappable::swaps == 6);
+
+    test_with_iterator<int*, int>();
 }
+