Мы знаем, что при использовании непрерывного блока памяти мы можем легко получить итератор (здесь &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 в таком массиве?
не точный обман, но есть ответ, пытаясь найти лучшее соответствие: stackoverflow.com/questions/45123882/…
std::sort(arr, arr + len);
ИМХО, для std::sort()
не имеет значения, являются ли начало и конец адресами для стека или кучи. В данном случае важно только непрерывное хранилище.
Некоторая связанная информация здесь: stackoverflow.com/questions/1719607/…
Указатели соответствуют критериям RandomAccessIterator
, которые требуются для std::sort
. Неважно, указывают ли они на память стека или память кучи, если они указывают на один и тот же (непрерывный) массив. Итак, вы можете просто использовать:
std::sort(arr, arr + len);
При этом std::vector
, вероятно, лучший выбор для размещения массива в куче. Это избавит вас от головной боли при самостоятельном управлении памятью.
Указывает ли arr+len на конец массива даже при выделении кучи? У меня сложилось впечатление, что как только вы используете выделение кучи, память больше не является непрерывным блоком, да. Виноват. :П
Я запутался со структурой связанного списка. Извините, я новичок в этом
Не волнуйтесь, все начали с этого :) Да, массив всегда непрерывен, независимо от того, размещаете ли вы его в куче или в стеке. Это гарантируется стандартом. Есть много вещей, которые используют это свойство, например. оператор []
на самом деле не что иное, как сложение указателя, поэтому array[5]
— это точно такая же инструкция, как *(array + 5)
.
Да, вы можете использовать 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
Вы не пробовали?