Могу ли я использовать 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, что требуется для std::sort.Не имеет значения, указывают ли они на стековую или кучную память, если они указывают на один и тот же (непрерывный) массив.Таким образом, вы можете просто использовать:

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

При этом, std::vector, вероятно, является лучшим выбором для размещения массива в куче.Это избавит вас от головной боли при самостоятельном управлении памятью.

Answer 2

Да, вы можете использовать std::sort одинаково в обоих случаях, std::sort не знает или не заботится о том, как была выделена память.

Answer 3

В библиотеке C ++ итераторы - это в основном причудливые указатели.Таким образом, стандартно просто увеличивать указатель на конец массива, чтобы получить указатель «конца»:

#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) распознают, что такого родакода по своей сути небезопасен, потому что вы должны вручную указать длину массива.В результате они вызовут (подавляется с помощью флага компилятора, если вам нужно) ошибку времени компиляции, если вы попытаетесь сделать это, и посоветуют вам использовать вместо этого предоставленную компилятором утилиту:

#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

Answer 4

Могу ли я использовать std :: sort для выделенных в куче сырых массивов?

Да.

Не знаю, смогу ли я получить итератор для этого массива

Можно.

Указатель на элемент является итератором произвольного доступа для массивов. В случае автоматического массива имя массива неявно превращается в указатель, который можно использовать в качестве итератора для начала массива. В случае динамического массива результат new[] уже является указателем, т.е. итератором на начало массива. Вы можете получить указатель до конца, используя арифметику указателя, как в вашем примере.

Единственное существенное отличие между переменной массива и указателем на динамический массив в отношении использования std::sort заключается в том, что вы не можете использовать std::end или std::size с указателем, как вы могли бы использовать с переменной массива. Вместо этого вам нужно отдельно знать размер массива. В этом случае вы сохранили длину в переменной len.