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

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

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, используйте вектор. Он как раз то, что вам нужно. Пример я где-то выше привел, для ваших целей он в самый раз: добавить и взять. Другие функции вроде как не нужны?..