VPF::расширение динамического массива

zkv

Дата 28.12.2007, 14:47 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Участник Клуба
Сообщений: 2133
Регистрация: 23.7.2006
Где: Санкт-Петербург

Репутация: нет
Всего: 92

Цитата

При разделении темы произошли неполадки, поэтому теперь представлена в таком виде. Извините.

Neytral

Интересует задача создания функции расширяющей динамический массив (функция должна вызываться последовательно несколько раз, т.е. к примеру расширить массив от 0 до 99999 шагом 1), передаваемый ей через список параметров. Собственно это первый пример, который к сожалению выдаёт ошибку.

Код


#include <iostream>
using namespace std;

void func (int *a, int &num)//функция за один вызов увеличивает размер массива на 1
{
    delete [] a;
    num=num+1;//если эту строку убрать - то программа работает!!!! Правда смысл функции при этом теряется :(
    a=new int [num];
}

void main()
{
    int num=0;//содержит текущий размер массива
    int *a=new int [num];//переменная обязательно создаётся вне тела функции
    
    for (int i=0;i<99999;i++)//если количество итераций
                            //цикла ограничить до 3 - работает!!!
        func(a,num);    
    delete[] a;
}

Тот же пример, только без функции - всё работает замечательно!

Код


#include <iostream>
using namespace std;

void main()
{
    int num=0;
    int *a=new int [num];
    
    for (int i=0;i<2007;i++)
    {
        func(a,num);    
        delete [] a;
        num=num+1;
        a=new int [num];    
    }
    delete[] a;
}

У меня Visual C++ 6.0, ставил сервиспаки 1, 2, 4, 5 (ставил все по порядку).

bsa

Код


#include <iostream>
using namespace std;

void func (int *&a, int &num)//обрати внимание на ссылку
{
    delete [] a;
    num=num+1;
    a=new int [num];
}

void main()
{
    int num=0;//содержит текущий размер массива
    int *a=new int [num];//переменная обязательно создаётся вне тела функции
    
    for (int i=0;i<99999;i++)//если количество итераций
                            //цикла ограничить до 3 - работает!!!
        func(a,num);    
    delete[] a;

}

А лучше это делать через realloc. Хоть и сишная функция, зато меньше гимору.

JackYF
имхо, лучше это делать через std::vector - это его штатное поведение, - (причем он будет вести себя в этом случае оптимальнее, чем реаллок и такая самописная функция) и не изобретать велосипед.

bsa

логично, и как я сам про него забыл...  smile

bsa

ты еще и про std::vector почитай. Может он тебе лучше подойдет.

UnrealMan

Цитата(JackYF @  6.9.2007,  22:53 Найти цитируемый пост)

Цитата

причем он будет вести себя в этом случае оптимальнее, чем реаллок

Оптимальнее по скорости в случае POD-типов - это вряд ли.

JackYF

я про другое.

Если я последовательно увеличиваю размер массива от 1 до N, то реаллок сделает N перевыделений памяти, а вектор - около log2(N). Так что не согласен.

UnrealMan

Ну так зачем же каждый раз-то realloc вызывать? Кстати, перевыделений, скорее всего, будет меньше - как раз тем realloc и хорош, в отличие от operator new + operator delete.

JackYF

а что делается в примере кода выше?

Цитата(UnrealMan @  9.9.2007,  22:08 Найти цитируемый пост)

Цитата

Кстати, перевыделений, скорее всего, будет меньше - как раз тем realloc и хорош, в отличие от operator new + operator delete.

А std::vector - наверняка еще меньше, причем прозрачно для тебя.

UnrealMan

Цитата(JackYF @  10.9.2007,  00:22 Найти цитируемый пост)

Цитата

а что делается в примере кода выше?

Да какая разница? Может, ты скажешь, что такое расширение вектора v

Код


std::vector<Type> tmp(v.size()+1);
std::copy(v.begin(), v.end(), tmp.begin());
v.swap(tmp);

будет быстро работать?

Цитата(JackYF @ 10.9.2007, 00:22 Найти цитируемый пост)

Цитата

А std::vector - наверняка еще меньше, причем прозрачно для тебя.

Меньше за счёт чего?

Любитель

Уже много раз спорили на эту тему. Вердикт однозначен - в плюсах в 99% случаев использование сишного управления памятью есть зло. Идеологическое зло smile

UnrealMan

Так-то оно так, но по эффективности realloc (там, где его можно применять именно как средство перераспределения памяти) всё-таки лучше smile

Любитель

Вряд ли лучше. Но даже если так, то эти накладные расходы относительно размера вектора можно считать постоянными и достаточно малыми. Ими стоит пренебречь в 99% случаев smile Поверь, все реализации СТЛ очень нехило оптимизированны.

JackYF

Цитата

Цитата(UnrealMan @ 9.9.2007, 23:43 Найти цитируемый пост)
Да какая разница? Может, ты скажешь, что такое расширение вектора v

std::vector<Type> tmp(v.size()+1);
std::copy(v.begin(), v.end(), tmp.begin());
v.swap(tmp);

будет быстро работать?

Ужас какой... tmp.reserve(v.size()+1);
tmp.push_back(что_надо);

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

Любитель

Тут не в этом дело smile Тут молотком, но только держат его наоборот и забивают не касаясь гвоздя - воздушными волнами.

UnrealMan

Цитата

Цитата(JackYF @ 10.9.2007, 01:50 Найти цитируемый пост)
Конечно, если так расширять, как ты показал... ну так блин, я тоже могу микроскопом гвозди забивать... пока микроскоп не развалится

Ну так и не надо realloc каждый раз вызывать. При его использовании тоже можно резервировать память. Однако, при вызове realloc полного перераспределения памяти может и не происходить.

Любитель

Цитата(UnrealMan @  10.9.2007,  01:28 Найти цитируемый пост)
Ну так и не надо realloc каждый раз вызывать. При его использовании тоже можно резервировать память. Однако, при вызове realloc полного перераспределения памяти может и не происходить.

При расщирении вектора тоже.

UnrealMan

Цитата(Любитель @  10.9.2007,  02:48 Найти цитируемый пост)
При расщирении вектора тоже.

Покажи мне хоть одну такую распространённую реализацию вектора, где при расширении вектора в случае нехватки capacity полного перераспределения памяти не происходит.

JackYF

Цитата

Цитата(UnrealMan @ 10.9.2007, 10:10 Найти цитируемый пост)
Покажи мне хоть одну такую распространённую реализацию вектора, где при расширении вектора в случае нехватки capacity полного перераспределения памяти не происходит.

Может, и не покажем.

Зато можно создать вектор не POD-объектов, а realloc про new/delete не знает ничего.

UnrealMan

Цитата

Цитата(JackYF @ 10.9.2007, 15:24 Найти цитируемый пост)
Зато можно создать вектор не POD-объектов, а realloc про new/delete не знает ничего.

Об этом речи не идёт. Кроме того, даже с не POD-объектами вектор работает неэффективно. Более эффективная реализация подразумевает использование move-конструкторов для перемещения элементов на новый участок памяти, вместо того чтобы всюду тупо вызывать для них copy-конструкторы. Для того же вектора конструктор перемещения можно реализовать гораздо эффективнее копирующего конструктора.

Цитата

Цитата(JackYF @ 10.9.2007, 15:24 Найти цитируемый пост)
Может, и не покажем.

Значит, realloc всё-таки эффективней smile

Это сообщение отредактировал(а) zkv - 28.12.2007, 16:02

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »