我可以在堆分配的原始数组上使用 std::sort 吗？

Question

我们知道，当使用连续的内存块时，我们可以很容易地得到一个迭代器（这里是&arra[0]或arra）并将迭代器传递给std::sort。

例如：

int arra[100];
    for (int i = 0; i < 100; i++) {
        arra[i] = rand() % 32000;
    }
    for (int i = 0; i < len; i++)std::cout << arra[i]<<" ";
    std::sort(arra,arra+100);

现在如果我有一个分配给堆的数组，比如 arr 这里：

int len;
    len = 100;
    int* arr = new int[len];
    for (int i = 0; i < len; i++) {
        arr[i] = rand() % 32000;
    }

我不知道我是否可以获得这个数组的迭代器，所以我可以对这个数组使用 std::sort 吗？如果没有，是否有任何解决方法可以在这样的数组上使用 std::sort？

Answer 1

指针确实符合 RandomAccessIterator which is required by std::sort 的标准。它们指向栈内存还是堆内存并不重要，只要它们指向同一个（连续的）数组即可。所以你可以简单地使用：

std::sort(arr, arr + len);

也就是说，std::vector 可能是在堆上分配数组的更好选择。它会让您免去自己管理内存的麻烦。

Answer 2

是的，您可以在两种情况下以相同的方式使用 std::sort，std::sort 不知道也不关心内存是如何分配的。

Answer 3

Can I use std::sort on heap allocated raw arrays?

是的。

I don't know whether I can get an iterator for this array

可以。

指向元素的指针是数组的随机访问迭代器。在自动数组的情况下，数组名称隐式衰减为一个指针，您可以将其用作指向数组开头的迭代器。在动态数组的情况下，new[] 的结果已经是一个指针，即指向数组开头的迭代器。您可以像示例中一样使用指针运算获取指向末尾的指针。

关于 std::sort 的使用，数组变量和指向动态数组的指针之间的唯一显着区别是您不能将 std::end 或 std::size 与类似的指针一起使用你可以用一个数组变量。相反，您需要单独知道数组的大小。在这种情况下，您已将长度存储在变量 len.

中

Answer 4

在 C++ 库中，迭代器基本上就是花式指针。因此，standard-compliant 只是将指针递增到数组的末尾以获得 "end" 指针：

#include<algorithm>
#include<iostream>

int main() {
    int len;
    len = 100;
    int* arr = new int[len];
    for (int i = 0; i < len; i++) {
        arr[i] = rand() % 32000;
    }
    //Valid, Defined Behavior that works as expected
    std::sort(arr, arr + len);
    //alternative, to make the code easier to read:
    //auto begin = arr;
    //auto end = arr + len;
    //std::sort(begin, end);
    for(int i = 0; i < len; i++)
        std::cout << arr[i] << std::endl;
}

但是，一些编译器（如 Visual Studio 的编译器）认识到这种代码本质上是不安全的，因为您需要手动提供数组的长度。因此，如果您尝试这样做，它们将导致（如果需要，可以使用编译器标志来抑制）Compile-time 错误，建议您改用 compiler-provided 实用程序：

#include<algorithm>
#include<iostream>

int main() {
    int len;
    len = 100;
    int* arr = new int[len];
    for (int i = 0; i < len; i++) {
        arr[i] = rand() % 32000;
    }

    //MSVC Specific Code!
    auto begin = stdext::make_checked_array_iterator(arr, len);
    auto end = arr + len;
    std::sort(begin, end);
    for(int i = 0; i < len; i++)
        std::cout << arr[i] << std::endl;
}

有关 Visual Studio 编译器这一特殊快速的更多信息，请参见此处：https://docs.microsoft.com/en-us/cpp/standard-library/checked-iterators?view=vs-2019

我可以在堆分配的原始数组上使用 std::sort 吗？

Can I use std::sort on heap allocated raw arrays?

c++

sorting

memory-management

heap-memory

dynamic-arrays