Объявление массива размером n

[Константин01]

Как известно объявление массива требует определить границы, например, int array[n], где n - целочисленное значение.

Однако что делать, если требуется указать размер массива в функции, а само значение n будет поступать из стандартного ввода?

Например,

void make_set(int p[n], int x)
{
	p[x] = x;
}

int find_set(int p[n], int x)
{
	return (p[x] == x ? x : find_st(p, p[x]));
}

Программа не компилируется, так как неизвестно значение n. Оно будет известно только в main функции.

	ifstream input;


	input.open("C:\\Users\\1\\Desktop\\input.txt");
	
        int n;
	input >> n;

Как лучше организовать объявлении функции в таком случае?

[p51x]

int p[]
int* p
std::vector& p
...

[_Bers]

Сообщение от p51x

int p[]
int* p
std::vector& p
...

тот случай, когда лучше бы человек вообще ничего не отвечал.

[taras-proger77]

Сообщение от _Bers

тот случай, когда лучше бы человек вообще ничего не отвечал.

Так в чём проблема? Не отвечай и никаких гвоздёв.

[taras-proger77]

Костя, массивы есть: константные, статические, динамические, разреженные, логические и физические. Константным называется массив, у которого не только количество элементов – известная на этапе разработки константа, которой нельзя ничего присвоить, но и сами элементы – константы. И сам массив – одна большая не скалярная константа. Пример:

const int a[4]={0, 1, 3, 7};

.
Статическим называется массив, элементы которого могут менять свои значения, но из количество – константа. Такой массив может быть размещён и на стеке, это не то же самое, что

static int a[4];

, слово «статический» имеет здесь другое значение. Динамический массив – это массив, у которого даже количество элементов – переменная. Синтаксис c не позволяет декларировать такой массив обычным способом. Но статический и константный массивы на c – синонимы указателей на нулевой элемент. Везде, где не значим их размер. Соответственно, можно декларировать указатель на элемент, создать блок данных оператором new, а потом обращаться к этому указателю, как к массиву, а если надо поменять размер, то просто выделяешь память по другому указателю, копируешь те элементы, которые должны остаться, освобождаешь память по старому указателю, потом копируешь в него новый. Для безопасности лучше завернуть всё это в класс и перегрузить конструктор, деструктор, функцию задания размеров и оператор квадратные скобки. Разреженный массив – это массив, у которого количество номинально существующих элементов отличается от количества фактически хранимых. Обычно разрежены гигантские массивы на много гигаэлеметнов, в которых нужно не более нескольких десятков килоэлементов. Логический массив – это массив, которого вообще нет, но который состоит из всех номинально существующих элементов разреженного массива. А физический массив – это то, что реально присутствует в памяти, но не обязано быть массивом и состоит из всех фактически хранимых элементов разреженного массива. И константный, и статический, и динамический, и разреженный массивы могут быть защищёнными. Защищённый массив – это массив, который не позволяет выйти за свои границы. То есть не позволяет обратиться к себе по индексу, выходящему за допустимый диапазон значений индексов.

[taras-proger77]

Статический и физический массивы могут быть зарезервированными. Зарезервированный массив – это массив такого размера, которого должно хватить, когда не известно, какого размера массив нужен. Если в разреженном массиве нужны только нулевой и пятимиллиардный элементы и не допускаются отрицательные индексы и индексы больше пяти миллиардов, то логический массив состоит из пяти миллиардов одного элемента, а физический – не менее, чем из двух элементов. Константный массив целесообразно делать статической величиной, а статический часто является как раз автоматической переменной. Статические у него тип переменной и размер, а не тип памяти.

[Croessmah]

Не претендуя на полноту.

void foo(){
   int arr[5] = {0} ;
   /*
   Это массив. 
   Расположен он будет на стеке функции
   Его размер должен быть известен во время компиляции.
   Если размер неизвестен, то можно воспользоваться следующими вариантами:
   1) Зарезервировать места сразу под большое число элементов, но это приведет либо 
       к большому перерасходу памяти, а ведь стек не резиновый, либо 
       к жесткому ограничению кол-ва элементов, которые можно в этот массив положить
   2) Можно при необходимости запрашивать динамической памяти рюмочку, ну или стаканчик,
       но порой приходится целую бочку памяти просить.
       Причем придется руками следить за выделением/освобождением (без RAII), 
       копированием элементов в новую память, размерами и т.д.
   3) Можно использовать готовые обертки, например, std::vector,
       которые, при правильном использовании берут часть головной боли на себя,
       подставляя под удар своё страшное и хрупкое шаблонное тельце.
   4) Забыть и никогда не вспоминать о c++.
   */
}

В данный момент нас интересует вариант №2.
Ну что же, можно познакомиться и с динамическим выделением памяти.
Итак, если Вашему приложению понадобилась динамическая память,
то можно запросить себе еще некоторое количество памяти во время выполнения.
При этом нужно внимательно следить за тем, чтобы не произошло утечки памяти.
Дело в том, что то, что мы выделили динамически,
мы должны сами же и освободить, когда оно нам больше не нужно.


В C для выделения памяти есть функции malloc, calloc, realloc, но это в C.
Эти функции ничего не знают о устройстве C++
и просто выделяют (точнее, просят у системы) "сырой" непрерывный кусок памяти
заданного размера (в байтах), и возвращают при этом указатель на "нечто" (void*).
Причем, если память выделить не удалось, то вернется "NULL".
Для освобождения памяти используется функция free, она также ничего не знает о C++.


В C++ для выделения такой же "сырой" памяти имеется operator new (и operator new[]).
Отличие operator new от operator new[] - фактически в том,
что можно более эффективнее реализовать собственные версии этих операторов.
Так что всё, что сказано про operator new, относится и к operator new[].
Конечно, если где-то есть разница, я укажу.
operator new так же запрашивает непрерывный кусок памяти,
и возвращает указатель на "нечто" (void*).
Никакие конструкторы эта штуковина тоже не вызывает,
но уже знает о исключениях и если выделение зафейлится,
то, кинет исключение, а не вернет nullptr. На самом деле,
сначала еще попытает счастье с new_handler, но мы опустим этот момент.
Также есть версия, которая не кидает исключение,
а возвращает nullptr в случае неудачи
и версия, которая совсем не выделяет память,
а просто параметр-указатель проходит там "транзитом",
причем можно еще и перегружать operator new, но сейчас не об этом.
Для освобождения памяти, выделенной с помощью operator new используется operator delete.
Для освобождения памяти, выделенной с помощью operator new[] используется operator delete[].


В C++ чаще для выделения памяти используется new-expression (не путать с operator new ).
Имеются две версии new-expression - new и new[].
Первая версия выделяет количество памяти,
достаточное для хранения одного элемента заданного типа
и применяет соответствующий тип инициализации,
например, вызывает конструктор без параметров.

Вторая версия выделяет количество памяти,
достаточное для хранения переданного количества элементов заданного типа
и применяет соответствующий тип инициализации,
например, вызывает конструкторы без параметров.

new-expression фактически работает в два этапа:
1) Запрашивает память, вызывая operator new (вторая версия вызывает operator new[]),
причем количество байт рассчитывает самостоятельно,
основываясь на размере типа и количестве необходимых элементов (для первой версии это один элемент).
Плюс может приписать некоторое количество байт для собственных нужд,
например, для хранения количества элементов под которые выделена память.
2) Затем производит инициализацию элемента (вторая версия производит инициализацию всех элементов).
Если инициализатор не указан, то будет использована default-initialization,
если указан - direct-initialization.
Ситуацию, когда при инициализации вылетает исключение пока не будем рассматривать.

Если из new-expression не вылетит исключение,
то вернется указатель на выделенный кусок памяти,
либо будет возвращен nullptr, если была использована версия operator new,
которая не выкидывает исключение в случае неудачи.
Для освобождения памяти, выделенной с помощью new-expression, используется delete-expression.
delete-expression также имеет две версии: delete и delete[]
Соответственно, для освобождения памяти,
выделенной с помощью new используется delete,
а для памяти, выделенной с помощью new[] - delete[]

delete-expression фактически, также работает в два этапа:
1) Вызывает деструктор объекта (delete[] вызывает деструкторы объектов).
2) Освобождает память, вызывая operator delete (delete[] вызывает operator delete[]).
Пока мы не освободим память, она так и будет считаться занятой.

Важно!
Если мы потеряем последний указатель на выделенную память,
и более никак не сможем добраться до адреса,
который вернула соответствующая функция выделения,
то, соответственно, мы не сможем освободить
эту память и она так и будет висеть занятой
до самого конца работы приложения.
То есть память эту мы не сможем использовать (т.к. у нас нет её адреса),
но при этом она будет помечена как "занятая", т.е. будет бесполезная трата памяти.
Такая ситуация называется "утечка памяти".
И за этими утечками не так просто уследить,
если использовать "голые" указатели.

[Croessmah]

И в одно сообщение всё не уместилось, так что продолжим.
Напишем несколько примеров и посмотрим на результат:

struct Test
{
    Test() { std::cout << "ctor. address: " << this << std::endl; }
    Test(const Test& src) { std::cout << "cctor. address: " << this << "; source address: " << &src << std::endl; }
    Test& operator=(const Test& src) { std::cout << "assign. address: " << this << "; source address: " << &src << std::endl; return *this; }
    ~Test() { std::cout << "dtor. address: " << this << std::endl; }
    double x;//Не будем его использовать, просто чтобы место занимало
};
 
 
 
int main()
{
    size_t count = 0 ;
    std::cout << "input count-> " ;
    std::cout.flush();
    std::cin >> count ;
    if(count==0){
        std::cerr << "\nerror: invalid count\n";
        return -1;
    }
    //////////////////////////////////////////////
    std::cout << "\nTest malloc for " << count << " elements:\n" ;
    //выделяем память в количестве, достаточном для хранения введенного числа элементов
    Test * test_ptr = (Test*)malloc(sizeof(Test)*count);//Требуется явный каст к Test*, т.к. в c++ запрещен неявный каст от void*.
    std::cout << "memory address: " << test_ptr << std::endl;
    //освобождаем память:
    free(test_ptr);
    //////////////////////////////////////////////
    test_ptr = nullptr;//возьмите за правило обнулять указатели, которые больше не валидны.
    std::cout << "end of main" << std::endl;
}

http://rextester.com/VAIF67989
Как видим, память выделилась, но конструкторы не вызывались.

operator new тоже ничего не будет вызывать,
а также выделит кусок памяти, поэтому пропустим его,
перейдем сразу к new-expression:

    //////////////////////////////////////////////
    std::cout << "\nTest new:\n" ;
    //выделяем память в количестве, достаточном для хранения одного элемента
    Test * test_ptr = new Test();
    std::cout << "memory address: " << test_ptr << std::endl;
    //освобождаем память:
    delete test_ptr;//Выделялось с помощью new, поэтому здесь delete
    test_ptr = nullptr;
    std::cout << "\nTest new[] for " << count << " elements:\n" ;
    //выделяем память в количестве, достаточном для хранения введенного числа элемента
    test_ptr = new Test[count];//Указываем уже не число байт, а количество элементов
    std::cout << "memory address: " << test_ptr << std::endl;
    //освобождаем память:
    delete[] test_ptr;//Выделялось с помощью new[], поэтому здесь delete[]
    //////////////////////////////////////////////

http://rextester.com/YVNMB97286

как видим, помимо того, что произошло выделение памяти,
также вызвались конструкторы объектов,
а при уничтожении вызвались деструкторы.

int main()
{
    std::cout << "\nTest reallocate memory:\n" ;
    //Значения могут быть вычеслены в рантайме, но чтобын е городить огород я задам их прямо в коде
    //Выделяем память в количестве, достаточном для хранения трех элементов
    Test * test_ptr = new Test[3];
    std::cout << "memory address: " << test_ptr << std::endl;
 
    //А теперь нам вдруг потребовалось "расширить" этот "массив" еще на один элемент.
    //Необходимо выделить память под 4 элемента:
    Test * test_ptr_temp = new Test[4];
    //И скопировать в новую память старые элементы:
    for(size_t i = 0 ; i < 3; ++i){
        test_ptr_temp[i] = test_ptr[i];
    }
    //Теперь, память, занимаемая массивом из трех элементов нам более не нужна.
    //Освобождаем её:
    delete[] test_ptr;//Выделялось с помощью new[], поэтому здесь delete[]
    test_ptr = test_ptr_temp; //Всё, теперь у нас по адресу, который содержится в test_ptr лежит 4 элемента
    test_ptr_temp = nullptr;
    //Поработали
    std::cout << "big work" << std::endl;
    //Теперь освобождаем память:
    delete[] test_ptr;//Выделялось с помощью new[], поэтому здесь delete[]
    test_ptr = nullptr;
    std::cout << "end of main" << std::endl;
}

http://rextester.com/DPE96044

В этом примере показано как можно "расширить" выделенный кусок памяти.
Конечно, выделять память и копировать элементы при каждом чихе не очень эффективно,
но это лишь пример.
Например, std::vector работает по такому же принципу,
только там память выделяется сразу с запасом и используется placement new
для создания элементов (конечно, всё немного сложнее и вся эта фигня завернута в аллокатор).
если нужно, могу подробнее описать, но не думаю,
что на данном этапе обучения это будет очень понятно,
собственно, поэтому и в этом посте содержатся некоторые допущения,
и нет сложных примеров, а также placement new, перегрузок операторов new/delete и т.д.