Массивы — это одна из базовых структур, трудно себе представить сколько-нибудь сложную программу без них. Но что если попробовать реализовать массив самому? В голову сразу приходит список: будем в каждом элементе массива хранить указатель на следующий и хранить эти элементы в динамически выделяемой памяти на куче.
Слишком просто. Давайте обойдемся без кучи. Никаких malloc и new. Можно ли тогда сделать массив?
На одних глобальных переменных мы далеко не уедем. Для того чтобы реализовать идею со списком, нам все-таки нужно выделять память динамически, и если знать, как работают внутренности C на низком уровне, то решение становится понятным.
Где происходит динамическое выделение памяти кроме кучи? На стеке вызовов. Каждая вызванная функция хранит там свои локальные переменные. Вызовем функцию рекурсивно и много выделенного место на стеке. Правда, оно будет размазано по разным вызовам, но можно связать все вместе указателями, которым плевать на
Давайте реализуем эту идею, добавив немного ООП и другого сахара, чтобы массив вел себя, как обычный. В качестве бонуса напишем сортировку пузырьком.
Gist
#include <iostream>
struct Array {
int val;
Array* previous;
Array(int val, Array* previous) : val(val), previous(previous) {}
int& operator[](size_t index) {
if (index == 0) {
return val;
}
return (*previous)[index - 1];
}
};
void generator(size_t n, void(*payload)(Array), Array* previous = 0) {
Array element(0, previous);
if (n == 1) {
payload(element);
} else {
generator(n - 1, payload, &element);
}
}
size_t N;
void test(Array array) {
for (size_t i = 0; i < N; ++i) {
std::cin >> array[i];
}
for(size_t i = 0 ; i < N - 1; ++i) {
for(size_t j = 0 ; j < N - i - 1 ; ++j) {
if(array[j] > array[j+1]) {
int tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
}
}
}
for (size_t i = 0; i < N; ++i) {
std::cout << array[i] << ' ';
}
}
int main() {
std::cin >> N;
generator(N, test);
}
Комментарии (27)
dmandreev
17.09.2021 19:48+3Что это за бред вообще? Проба GPT-3? Надмозг?
DistortNeo
17.09.2021 20:47Меня больше интересует другое: аккаунт создан 3 октября 2012 г., последняя активность 04.06.2021, ни одной публикации или комментария. И тут опа: и публикация. Такое вообще бывает?
Chuvi
17.09.2021 23:42Вопрос в том, как долго статья была в песочнице.
Наткнулся кто-то на эту статью и решил пригласить.
alexprey
17.09.2021 21:42Учитывая что подпись автора говорит, что он разработчик DL и NLP, то вполне вероятно так и есть)
lorc
17.09.2021 20:06+2если знать, как работают внутренности C на низком уровне
... то можно воспользоваться mmap(MAP_ANONYMOUS) или там VirtualAlloc(). malloc же берет память где-то?
Alex_ME
17.09.2021 20:53+1Еще есть
sbrk
oleshii
18.09.2021 11:02Если память не изменяет, сам sbrk ничего не выделяет, а сдвигает границу адресного пространства кучи, доступной процессу. Причём, в теории, может сдвинуть её как вверх, так и вниз. Отсюда и расшифровка первого символа акронима sbrk, [s] - shift.
godzie
18.09.2021 11:30+1сам sbrk ничего не выделяет, а сдвигает границу адресного пространства кучи, доступной процессусам sbrk ничего не выделяет, а сдвигает границу адресного пространства кучи, доступной процессу
... что впринципе и является выделением памяти, ведь мы получаем больше виртуальных адресов для использования.
В линуксе вниз граница не двигается, в этом смысле предпочтительнее ммап- выделенную им память можно отдать обратно ос.
oleshii
18.09.2021 11:38впринципе и является выделением памяти
Скорее резервирование памяти под кучу. Выделение сложный процесс аллокациии из кучи под текущие нужды.
DistortNeo
18.09.2021 12:05Можно рассмотреть вырожденный случай кучи, когда память только выделяется, но не освобождается.
oleshii
18.09.2021 12:13вырожденный случай кучи, когда память только выделяется
В чём практический смысл такой кучи ? В исчерпывании памяти и вызове process killer ?
DistortNeo
18.09.2021 14:11Так речь же о том, что без malloc обойтись. А остальные детали в данном случае не интересны.
Ну то есть вместо выделения куска памяти в куче с помощью malloc (или его собственной реализации) просто инкрементируем указатель на память.
oleshii
18.09.2021 18:26инкрементируем указатель на память
Простого инкремента не буде стандартным ли alloc пользоваться, или своими реализациями. В любом итоге это: списки кусков по размеру, деревья аллоцированных кусков, мьютексы.
thatsme
18.09.2021 09:19Ну аффтар же сказал "без кучи". Без кучи единственный вариант рекурсия. Так себе троллинг впрочем ...
lorc
18.09.2021 16:47Выделение памяти через mmap() не имеет прямого отношения к куче. То есть, конечно, можно в выделенной памяти потом завести heap allocator, но ведь можно и не заводить.
fougasse
17.09.2021 20:26+8Так С или плюсы?
Ничего, что под массивом в мире С/С++ понимается непрерывный участок памяти, а список - это другое? И одно второе не заменяет.
gwg605
18.09.2021 00:15Мда... мне кажется, что автору стоит подучить структуры данных и алгоритмы, хотя бы базовые вещи.
Я тут перед собеседованиями заново проштудировал структуры данных и алгоритмы, и понял, что основательно их подзабыл :(
agmt
18.09.2021 13:27+21. Прочитайте, что такое массив. // Тут не выполняется даже доступа по индексу за O(1).
2. Прочитайте, что происходит со стеком после завершения функции. // Скорее всего, данные там останутся, но вызов функции перетрёт значения.
oleg-m1973
18.09.2021 14:45+1В целом пост, конечно, безграмотный, как и было сказано в предыдущих комментариях. Но есть в нём одна разумная мысль:
Списки, в отличие от массивов, не владеют элементами. Список это, скорее, способ упорядочивания относительно независимых наборов данных. Поэтому элементы списка могут иметь разный размер и выделяться где угодно, в частности, на стеке. Главное - гарантировать удаление элемента из списка до того, как будет удалён "носитель".
Лично я использую выделение отдельных элементов списка на стеке довольно регулярно, особенно в многопоточных алгоритмах.
Chuvi
Что мы получили кроме дикого оверхеда?