Как узнать длину динамического массива c

Но в С++ эту проблему решили - там есть класс std::vector. Используйте его там, где хотите "динамические массивы".

длина динамического массива

знаю, что с помощью стандартных способов это невозможно (в c++), но, например, в Java это можно сделать с помощью метода length, а на c++ как это можно реализовать?

Следует учесть, что массивы могут быть и двумерными.

Заранее благодарен за любую помощь!

10 ответов

18 декабря 2006 года
3.0K / / 25.03.2003
Если я правильно понял вопрос, то размер первичного массива (в байтах), можно узнать вот этим:
size_t _msize(void *memblock);

но только, если память была выделена calloc, malloc или realloc.
18 декабря 2006 года
365 / / 19.12.2005

Что-то вроде GetProcessHeaps --> HeapWalk. И смотришь для каждого блока, на случай если он выделен под данный массив.

19 декабря 2006 года
468 / / 19.02.2006

Спасибо, помогло :о)

НО. _msize возвращает значение только для памяти выделенной с помощью malloc(), а как быть с оператором new?

char * s = new char[128];
strcpy(s, "hello, world!");
cout << _msize(s) << endl;

выводит 128. Коллеги, можно ли (поддерживается ли это системой) использовать new и _msize вместе?

20 декабря 2006 года
2.5K / / 14.07.2006

В любом случае - это нелегитимное решение. Зачем тебе узнавать размер памяти по указателю - длину надо хранить всегда.

20 декабря 2006 года
3.0K / / 25.03.2003

.
. _msize возвращает значение только для памяти выделенной с помощью malloc(), а как быть с оператором new?

Насколько я знаю, оператор new работает через malloc, который, в свою очередь через HeapAlloc. Аналогичная схема и с delete: delete -> free -> HeapFree.

Если эта схема правильная, то использование _msize - допустимо.

20 декабря 2006 года
73 / / 05.10.2006

Господа, по-моему гораздо проще и элегантнее использовать схему аналогичную си-строкам - в конце массива хранить специальный элемент-терминатор (в простейшем случае 0), и узнавать размер, прогулявшись по массиву.

ЗЫ : А если код такой

char* p = new char[N]; // массив байт, верна ? 😉
// и если в массиве p заведомо нет нулей, то попросту
unsigned length = strlen(p);

20 декабря 2006 года
3.0K / / 25.03.2003

char* p = new char[N]; // массив байт, верна ? 😉
// и если в массиве p заведомо нет нулей, то попросту
unsigned length = strlen(p);

1. Речь здесь идет совсем о другом.
2. strlen - функция, для работы со строками в стиле С (ASCII(Z)). Название темы внимательно прочитай. 🙂

20 декабря 2006 года
4.8K / / 20.01.2000

Обсасываем проблему высосанную из пальца?
Если сам создал массив, значит должен и длину знать.
Если мучает склероз, сохрани длину в соотв. переменной, рядом с массивом.

Какие проблемы? В чем сложность? Зачем делать простые вещи через задние проходы?

20 декабря 2006 года
2.6K / / 04.11.2006

Если мучает склероз, сохрани длину в соотв. переменной, рядом с массивом.

Тут кстати, поблизости есть тема, о пользе контейнеров:)

20 декабря 2006 года
468 / / 19.02.2006

мне нужно написать одну программку, но в ней массивы вида m[a][c]. причем a,b,c каждый раз разные, и подобных массивов очень много создается по ходу работы программы.

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

Вариант с контейнерами хорош конечно, но мне нужно быстродействие.

Всем спасибо за советы, вопрос исчерпан.

Динамический массив

В [math]i[/math] -ую ячейку массива записывается элемент [math]x[/math] . Время выполнения — [math]O(1)[/math] .

add(x)

Добавление в массив элемента [math]x[/math] . Время выполнения — [math]O(1)[/math] ; в худшем случае, при котором необходимо перенести все элементы из текущего массива во вдвое больший массив — [math]O(n)[/math] ( [math]n[/math] — размер массива).

del()

Удаляет последний элемент массива. В случае, если количество элементов в массиве в [math]C[/math] раз меньше его длины, то происходит сжатие в [math]B[/math] раз. ( [math]C,B[/math] — константы, зависящие от реализации). Время выполнения операции в худшем случае — [math]O(n)[/math] .

size()

Возвращает количество элементов массива. Время выполнения — [math]O(1)[/math] .

Амортизационная стоимость каждой операции

Пусть наш массив расширяется в [math]2[/math] раза, и уменьшается в [math]2[/math] раза, когда длина массива в [math]4[/math] раза больше количества элементов в массиве. В этом случае амортизационная стоимость каждой операции будет [math]O(1)[/math] .

Метод предоплаты

Стоимость операции add(x)

Иллюстрация

Пусть у нас единицей стоимости операции является одна монетка. Тогда при каждой операции add(x), при которой нам не требуется копирование, мы будем использовать три монетки. Из них одна пойдёт на стоимость самой этой операции, а две будут в резерве (пусть, если мы добавили [math]i[/math] -ый элемент, мы будем класть по одной монетке к элементам с номерами [math]i[/math] и [math]i-\frac[/math] ). В итоге, к тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которую мы и можем использовать на его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции add(x) — [math]3[/math] , и среднее время её работы — [math]O(1)[/math] .

Стоимость операции del()

При каждой операции будем использовать две монетки. Одну из них потратим на само удаление элемента, другую на элемент, стоящий на позиции [math]i \bmod \dfrac[/math] . Тогда даже в самом худшем случае (только что расширились, а потом [math]\dfrac[/math] удалили) у каждого элемента из первых [math]\dfrac[/math] будет по монете и на удаление надо будет потратить только [math]1[/math] монету.

Метод потенциалов

За потенциал примем число: [math]\Phi(c, s) = \begin 2s-c, & \text s\geqslant\fracc \\ \fracc-s, & \text s\lt \fracc \end[/math] , где [math]c[/math] — размер массива, [math]s[/math] — число элементов массива.

Стоимость операции add(x)

• [math]\frac= 1[/math] , массив расширяется: [math] a_i = t_i + \Phi(2c, s + 1) - \Phi(c, s) = (s + 1) + (2(s+1)-2c)-(2s-c) = 3 [/math]

• [math]1\gt \frac\geqslant\frac[/math] , массив не расширяется: [math]a_i=t_i+\Phi(c,s+1)-\Phi(c,s)=1+(2(s+1)-c)-(2s-c)=3[/math]

• [math]\frac\lt \frac, \frac\geqslant\frac[/math] , массив не расширяется:

[math]a_i = t_i + \Phi(c, s+1)-\Phi(c, s)= 1 +(2(s+1)-c)-(\fracc - s)= 3+3s-\fracc= 3 + \frac3c-\fracc \lt 3+\fracc-\fracc=3[/math]

• [math]\frac\lt \frac, \frac\lt \frac[/math] , массив не расширяется: [math]a_i = t_i + \Phi(c, s + 1) - \Phi(c, s) = 1 + (\fracc - (s + 1)) - (\fracc - s) = 0[/math]

В итоге, средняя стоимость операции — [math]3[/math] , а среднее время работы — [math]O(1)[/math] .

Стоимость операции del()

• [math]\frac=\frac[/math] , массив сужается: [math]a_i = t_i + \Phi(\frac, s - 1) - \Phi(c, s) = s + (\frac\cdot\fracc-(s-1)) - (\fracc-s) = 1-\fracc+s=1[/math]
• [math]\frac\lt \frac\lt \frac[/math] , массив не сужается: [math]a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (\fracc-(s-1))-(\fracc-s)= 2[/math]
• [math]\frac\geqslant\frac, \frac\lt \frac\Rightarrow s=\fracc[/math] , массив не сужается: [math]a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) =1 +(\fracc-(s-1))-(2s-c)=2+\fracc-3s = 2[/math]
• [math]\frac\gt \frac[/math] , массив не сужается: [math]a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (2(s-1)-c)-(2s-c)=0[/math]

Средняя стоимость операции — [math]2[/math] , а среднее время работы — [math]O(1)[/math] .

Динамические массивы в современных языках программирования

Динамические массивы широко применяются во многих языках программирования. Рассмотрим, как эта структура данных реализуется в С++ и Java.

С++ — vector

В С++ динамический массив используется в структуре vector, она описана в STL(). Стратегия расширения проста: при попытке записи в массив нового элемента в момент полного заполнения памяти происходит увеличение размера в [math]2[/math] раза при компиляции GNU C++ и в [math]1.5[/math] раза при компиляции Microsoft Visual C++. При удалении элементов уменьшение размера массива никогда не происходит. При инициализации vector по-умолчанию начальный размер равен [math]0[/math] .

Java — ArrayList

В Java структура ArrayList основана на динамическом массиве. При превышении максимального на данный момент размера происходит увеличение в [math]1.5[/math] раза. Причем начальный размер равен [math]10[/math] . Как и в vector, в ArrayList не предусмотрено изменение размера при удалении элементов. Для принудительного изменения размера следует использовать метод trimToSize().

Источники информации

• Wikipedia — Dynamic array
• Wikipedia — Динамический массив

• Дискретная математика и алгоритмы
• Амортизационный анализ