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

Мы знаем, что при использовании непрерывного блока памяти мы можем легко получить итератор (здесь &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 в таком массиве?

Вы не пробовали?

NathanOliver 13.05.2019 17:58

не точный обман, но есть ответ, пытаясь найти лучшее соответствие: stackoverflow.com/questions/45123882/…

NathanOliver 13.05.2019 18:00
std::sort(arr, arr + len); ИМХО, для std::sort() не имеет значения, являются ли начало и конец адресами для стека или кучи. В данном случае важно только непрерывное хранилище.
Scheff's Cat 13.05.2019 18:00

Некоторая связанная информация здесь: stackoverflow.com/questions/1719607/…

Damien 13.05.2019 18:02
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
2
4
853
4
Перейти к ответу Данный вопрос помечен как решенный

Ответы 4

Ответ принят как подходящий

Указатели соответствуют критериям RandomAccessIterator, которые требуются для std::sort. Неважно, указывают ли они на память стека или память кучи, если они указывают на один и тот же (непрерывный) массив. Итак, вы можете просто использовать:

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

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

Указывает ли arr+len на конец массива даже при выделении кучи? У меня сложилось впечатление, что как только вы используете выделение кучи, память больше не является непрерывным блоком, да. Виноват. :П

Shriram 13.05.2019 18:18

Я запутался со структурой связанного списка. Извините, я новичок в этом

Shriram 13.05.2019 18:20

Не волнуйтесь, все начали с этого :) Да, массив всегда непрерывен, независимо от того, размещаете ли вы его в куче или в стеке. Это гарантируется стандартом. Есть много вещей, которые используют это свойство, например. оператор [] на самом деле не что иное, как сложение указателя, поэтому array[5] — это точно такая же инструкция, как *(array + 5).

Yksisarvinen 13.05.2019 22:10

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

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.

В библиотеке 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

Другие вопросы по теме