>обьявлять массив через маллок - это дольше

Дольше в плане написания лишнего десятка символов? Выполняется как раз пошустрее чуть-чуть;).

std::vector
http://www.sgi.com/tech/stl/Vector.html

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

Еще, кстати, элементом списка можно сделать не одно значение, а запись в которой будет место для 100 значений и т.п...

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

Добавлено через 1 минуту и 33 секунды
набросок кода нужен? правда Си я недавно изучаю, и книги щас под рукой нет, но набросок будет правильного направления 

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

Нет, нет и нет. Вы неправильно знаете. Malloc и иже с ним.

Вероятно вы изучаете с++, не называйте его си. Это совсем разные вещи:).

Вот как раз ЭТО проделывается в сях за неимением других методов (тот самый malloc и иже с ними). Есть, конечно, функции изменения размера, но, сколько мне помнится, они работают только с одномерными массивами. А вот в С++ - там да, там уже реализованы шаблоны классов для нормальных изменяющихся массивов. Для С++ применять можно и нужно вектор в данном случае. А для сей вариантов немного - malloc предпочтительнее. Не смешивайте два языка.

>Вот как раз ЭТО проделывается в сях

Вот это как раз проделывается в плюсах за неимением функций изменения размера массива. В плюсах new и delete. И единственный способ изменить этот буфер - создать новый больший (или меньший), скопировать данные и удалить прежний. Сами плюсовые векторы реализуются именно на alloc'ах. Учите матчасть!



>Для С++ применять можно и нужно вектор в данном случае.

Правильно. Только если в задаче не стоит условие использовать "традиционный" массив int*.

>Не смешивайте два языка.

В самом с++ нет механизмов эффективной работы с памятью, поэтому "смешивать два языка" - нередко единственный способ написания эффективного кода.

Я так не думаю. realloc тоже будет перемещать элементы, если места под новый размер не хватит. А вектор мало того, что рабоает с памятью блочно, т.е. выделяет заранее больше, чем требуется, так ещё и имеет метод reserve. Эффективность долдна достигаться за счёт минимизации операций выделения/удаления. Для этого существуют различные техники, та же блочная работа с памятью в stl простейшая из них или хорошая методика описана у Александреску "Размещение в памяти небольших объектов", реализация естьв его библиотеке Loki. Для отдельных случаев существует паттерны, например Flyweight pattern (реализация есть в boost'e). 

А если заранее размер массива неизвестен и не хочется лишний переаллокаций, то можно вначале запихать в стек-очередь, а после, если необходим быстрый произвольный доступ, один раз переместить все в вектор. 
  


имхо редко, чаще самый эффективный метод это правильно выбранный алгоритм.
  


Это сообщение отредактировал(а) mes - 5.12.2009, 17:33

>Я так не думаю. realloc тоже будет перемещать элементы, если места под новый размер не хватит.

Он будет перемещать не элементы, а кусок памяти. В сравнении с копированием элементов это просто реактивно. Справедливости ради замечу, что вектор сделает то же самое.

>А вектор мало того, что рабоает с памятью блочно, т.е. выделяет заранее больше, чем требуется, так ещё и имеет метод reserve.

А malloc'ом выделить сразу побольше религия не позволяет?

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

>чаще самый эффективный метод это правильно выбранный алгоритм

Естественно. Я подразумевал "при прочих равных".

>но как будет правильнее?

Так, как сказано в задании. Если в задании не оговаривается, правильнее в векторе или в chained-vector (хрен знает, как по-русски это правильно назвать, грубо говоря - список векторов. Есть ли он в STL, я не знаю).

Какая разница? Речь о том, что эффективная работа с памятью должна организовываться на более высоком уровне, чем непосредственно allocation функции или оператор new. Как? Я уже пояснил выше. 

Невнимательно прочитал твое сообщение.

>Какая разница? Речь о том, что эффективная работа с памятью должна организовываться на более высоком уровне, чем непосредственно allocation функции или оператор new. Как? Я уже пояснил выше. 

Чувак, я тебе про одно, а ты про другое. Говорить очевидные вещи, когда сказать больше нечего, необязательно. С++ не предоставляет методов для _эффективной_работаты_с_памятью_. Отчасти или полностью потому, что это не его задача. В STL такая работа ведется в рамках задач, которые решает STL, не более. Спор окончен.

Это сообщение отредактировал(а) djamshud - 5.12.2009, 22:32

 дополню, что вектор (и другие стандартные контейнтеры)  выберет максимально эффективный подходящий для хранимого типа. Что из этого следует думаю понятно без объяснения. 


c++ рассматривать отдельно от стл мягко сказать неэтично.. Потому что подходящую типобезопасную и эффективную стратегию реализовывать средствами языка с точки зрения с++ не логично.
  


Да естественно, но не очевидно.. особенно для новичков, и тех кого во время не поправили.   


имеется ввиду страничная тактика ? стл очереди именно ее и реализуют.


добавлю, что в цитате подразумевается эффективная_работа_с_памятью_для_плоских_типов , ну а  С++ просто глядит гораздо шире 

>имеется ввиду страничная тактика ? стл очереди именно ее и реализуют.

Имеется ввиду подобие списка векторов. Компромисс между компактностью и скоростью вектора и фрагментированностью списка. Обычные вектора в т.ч. стл имеют совместимость с традиционными массивами с/с++, поэтому хранятся линейно.

>c++ рассматривать отдельно от стл мягко сказать неэтично..

Я не отрывал плюсы от стл, наоборот я всегда упоминал ее. Смотрите цитируемый абзац до конца;).

>добавлю, что в цитате подразумевается эффективная_работа_с_памятью_для_плоских_типов

Поправлю. В цитате подразумевается эффективная_работа_с_памятью_вообще_без_привязки_к_типам, т.е. о блоках памяти как таковых.

Добавлено через 1 минуту и 43 секунды
bsa, есть мнение, что это просто опечатка;).

ну да, очереди так и устроены 


вектора бывают необычными ?  Не вектороми единым сыт стл   скоро еще контейнеров  добавят 

как раз и посмотрел :


имелось ввиду тогда в сторонних библиотеках ? потому как стл - это библиотека.


стл это не только вектор.


Вы в этом уверены ? советую взглянуть на реализацию хотя бы Вашего любимого вектора - никакого си. И самое главное что вектор это не просто оболочка,
А интелектуальная оболочка реализующая наиболее эффективные методы работы с памятью (раз мы о ней говорим), насколько позволяет  тип хранимых объектов. 
при всем вся дополнительная  работа по выбору эффективности происходит на стадии компиляции и не нагружая этими проблемами программиста,
позволяя ему менять тип, незаботясь о том что где то ниже вылерзут боком несовместимые операции .
  

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

Это сообщение отредактировал(а) mes - 6.12.2009, 01:19

>как раз и посмотрел

До конца _абзаца_;). Там про стл, который безусловно вектором не един, просто прицепился, зараза такая.

>имелось ввиду тогда в сторонних библиотеках ? потому как стл - это библиотека.

Тут я, признаю, немного оговорился, но если не отрывать фразу от общего контекста разговора, все станет понятно. Язык не предоставляет _механизма_эффективной_работы_. Ни сам, ни стлем. А внутри (в т.ч. стл) все в меру эффективно.

>Вы в этом уверены ? советую взглянуть на реализацию хотя бы Вашего любимого вектора - никакого си.

Ни чуточку не любимый, просто сабжевый и прицепившийся). Посмотрел. Обнаружил, что используется алокатор. Посмотрел аллокатор - плюсовая оболочка над malloc/realloc/free.

>А интелектуальная оболочка реализующая наиболее эффективные методы работы с памятью (раз мы о ней говорим), насколько позволяет  тип хранимых объектов.

Звучит очень красиво. Беглый осмотр не дал подтверждения вашим словам. Можете ткнуть носом, где именно это происходит?

>стл это не только вектор.

Да. Вместо "вектор" можно подставить любую стлеву структуру данных, истинность предложения сохранится. Стл весь из себя набор специфичных приблуд.

>да в сам каркас языка не включены высокоуровневые абстракции, как в других языках,

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

>однако он позволяет написать библиотеку этих абстракций, что дает большую свободу,

За что я его и люблю.

Добавлено через 11 минут и 35 секунд
Metalex, используйте вектор. Он как раз то, что вам нужно. Пример я где-то выше привел, для ваших целей он в самый раз: добавить и взять. Другие функции вроде как не нужны?..

new и delete предназначены для другого..  для работы с памятью смотрите уже упомяннутые Вами стл-аллокаторы.


для того что массив не плоских объектов создавать логично именно таким способом. 


Ну это смотря откуда смотреть. 



В процессе удаления происходит поочередное удаление всех объектов входящих в состав массива.
delete - удалить один, delete [] удалить много - все логично.


из за незнания средств и политики c++.



И за это же  ненавидят многие другие.. 


чуть позже - сейчас времени нет..

>для того что массив не плоских объектов создавать логично именно таким способом.

Ну так создать и удалить - это маловато;).

>delete - удалить один, delete [] удалить много - все логично.

Логично delete на все. И пусть сам разбирается, объект там или массив объектов. Ну зачем приделали эти две чертовые скобочки?:). Мне, когда я освобождаю память, в общем-то уже наплевать, что там, и как оно удалится. Вся механика внутри.

>из за незнания средств и политики c++

И из-за отсутствия в нем казалось бы очевидной фичи.

я не против .


у gcc например в файле <bits/stl_uninitialized.h> представлен типоориентированный выбор способа копирования массива (memmove или цикл)


причины две :
1. необходимость универсального доступа посредством указателя, в связи с чем отсуствуют статическая информация о типе
(в противном случае можно было сделать разницу между  int *p и int[] p и общий delete)
2. позиционирование c++ как языка без ненужных оверхедов, в связи с чем необходимая информация, которая могла бы присутствовать в рантайм, также отсуствует. 
(хоть некоторые реализации и идут на встречу пользователю, но это не в счет).


Это сообщение отредактировал(а) mes - 6.12.2009, 21:22

bsa, да мы наверное почти закончили:).

>у gcc например в файле <bits/stl_uninitialized.h> представлен типоориентированный выбор способа копирования массива (memmove или цикл)

А сначала звучало все более многообещающе и фундаментально. Впрочем и то неплохо. Надеюсь, существует возможность и ручной настройки, потому как многие простые классы поддаются memcpy/memmove.

>причины две :

Я так и думал, что это единственные причины. Но что malloc, что new кроме того, что выделяют память и отдают указатель на нее, еще и создают структуры, ассоциированные с этим указателем, в которых описано как минимум, сколько памяти выделено, чтобы потом не оттяпать лишнего. New, видимо, еще хранит какую-то ассоциацию с типом или деструктором типа. Очевидно, что new[] в довесок еще пишет, сколько элементов он создал, а delete[] эту информацию читает. Так почему было не научить обычный delete пользоваться этой информацией? В таком случае при каждом обычном new в эту структуру добавлялся еще один член - длина массива, равная единице. А вот допустим ли оверхед в несколько байт на каждый new, я не знаю. Казалось бы на одни выравнивания вылетает гораздо больше, но они то отключабельны.

Добавлено через 1 минуту и 17 секунд
bsa, ох, я успел сюда ответить. Перенесите это сообщение пожалуйста.

что значит _эффективная_работа_с_памятью_? почему в С++ она не эффективная?


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

>что значит _эффективная_работа_с_памятью_? почему в С++ она не эффективная?

Не предоставляет _методов_. Плюсовые методы неэффективны, потому как например копирование/перемещение/изменение размера блока делается через одно место. Это было хорошо видно из комментариев в начале топика, откуда нас выгнали.

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

Может быть, но по стандарту нужно delete[], а мне кажется, что это лишнее. А если поведение отличается от стандарта, значит остается уповать на реализацию delete в конкретной системе и в случае непредвиденного поведения пинать лишь себя. Valgrind например детектит ошибку в себе:





Хотя память таки освобождается

а через какое место, оно должно делаться?
нужно понимать, что просто взять и скопировав память не POD объекта в принципе нельзя, так-как там могут быть указатели/ссылки на другие объекты, если нужно свободно перемещать/копировать/изменять размер/освобождать участки памяти, то можно ограничиться POD объектами, или в некоторых случаях можно использовать аллокатор для не POD объектов

допустим, есть у нас какой либо алгоритм, который требует для своей работы создания какого-либо набора объектов(не плоских, а содержащих внутри себя ссылки на другие объекты), можно выделить один большой кусок памяти, за один вызов, затем все объекты создать в нем используя алокатор, а затем, когда результат работы алгоритма получен, просто освободить весь участок памяти, (сейчас в меня полетят тухлые яйца) даже не вызывая деструкторы   правда, для этого, деструкторы не должны иметь сайд эффектов, а все объекты должны использовать аллокаторы, для выделения/освобождения памяти, а так-же для конструирования и удаления объектов

еще, следует помнить, что С++, это не Си, программа на Си, по сути описывает работу с памятью, программа на С++, описывает типы, описывающие объекты, размещаемые в памяти и их семантику, то-есть, работа с памятью как в Си, по сути - хак, позволяющий обойти любые правила  

а собственно, почему бы и нет   

Lazin, вы конечно все правильно говорите, но не договариваете. И ни единого тухлого яйца не получите. Даже надгрызанного:).

Смотрите, создаем массив. Вдруг нам не хватает памяти (да, это очень низко; скажем на языке более высокого уровня - не хватает места в массиве), хотим его расширить. Через какое место? Через то самое: создаем новый массив, копируем (естественно поэлементно, ибо кусками копировать - это низко и по-сишному), удаляем старый. Захотели скопировать массив? Проделали все операции кроме последней. Почему нельзя было ввести более широкий арсенал действий, который кроме всего прочего еще и применяли бы оптимизированные техники при работе с простыми типами и "плоскими" объектами. Вот это была бы красота.

Вы можете возразить, что это все есть в стл векторе. Но раз уж есть кошерный вектор, нахрена вообще было new[] и delete[] создавать? Наверное на момент их создания вектора еще не было, но тогда опять исходный вопрос:).

MAKCim, суть кода - показать, что можно напрямую вызвать деструктор? Да, здорово;). Имхо из сообщения Lazin'а не следует обратного.

а кто мешает работать с массивом POD типа как одним большим куском памяти?


сначала хотел что-нибудь возразить, из принципа , но потом подумал, что и сам редко пользуюсь этими операторами, как правило тогда, когда нужно использовать массив фиксированного размера

>а кто мешает работать с массивом POD типа как одним большим куском памяти?

Скопировать/переместить можно. Но опять malloc + memчто-то. Ну так это геморно и по-сишному. Хочу, грубо говоря, так: 


Вот это по-плюсовому было бы. И опять же нафиг изначально использовать new[], если потом все равно придется пускаться в низкоуровневый пляс?

А расширить блок нормально вообще никак. Realloc по идее плюнется на указатель, созданный new[]. А хочется что-то вроде


Вот такие они, мои эротические фантазии.

Пока писал, проверил. Не плюнулся. Может быть просто из-за минималистичности примера, а может и более или менее нормально сработало. Хотя valgrind опять хорошенько проматерился. Тут опять видимо тонкости реализации, на которые нельзя полагаться: new и malloc, с которым работает realloc, создают "разные" указатели.

нет, мне просто в тот момент нечего было делать ;) код бессмысленен