Есть вопрос - насколько медленными являются операции malloc и free?
Медленнее ли new/delete, чем malloc/free?

Я к чему это спрашиваю-то...

Мне нужно реализовать некую динамическую (а может и нет) структуру данных, в которую бы упорядоченно добавлялись целые числа и в ней поизводить поиск заданных чисел.
Конечно же хочется чтоб всё это(добавление и поиск) делалось как можно быстрее и отсюда возникают вопросы:

 - оправдано ли использование дерева поиска в качестве этой ДСД, ведь элементы и так добавляются УПОРЯДОЧЕННО, а ещё на построение дерева уходит относительно много времени(именно здесь возникает вопрос о malloc/free, приведённый в начале). 

 - Так же по-моему не совсем рационально использовать список - во-первых поиск в нём - только последовательный(а элементы как вы помните добавляются упорядоченно), и тоже нужно время на формирование списка(т.е. опять malloc/free).

И я думаю - может и не нужны в моём случае такие "простые ДСД", может лучше использовать - "комбинированнные"?

Т.е. например ускорить поиск, зная, что элементы, добавляющиеся в мою ДСД - уже упорядочены, можно только используя 1-мерн. массив (т.е. вектор) некой размерности (например 10 или 100) для хренения эл-тов (или ещё как-то?).

Ну естественно, что простой статический массив тут не подойдёт. Тогда возникает идея использовать список, эл-тами которого являются массивы(векторы), и тогда действительно можно значительно ускорить поиск, используя бинарный или однородный бинарный поиски, и так же уменьшить время на формирование такой ДСД - ведь память выделяется и освобождается значительно реже - в моём случае в 10 или 100 раз. Но тогда уже велика вероятность выделения лишней памяти - ведь кол-во добавляемых элементов неизвестно и врядли оно будет кратно 10 или 100, но это уже отдельная история.

И собственно вопросы - верны ли мои рассуждения? - Принимается абсолютно любая критика.
И второй - какую структуру данных предложите мне вы?

new\delete (стандартные) обычно реализуются через malloc\free.
Работают действительно относительно медленно. C++ дает возможность кастомизировать выделение памяти.
Если речь идет о небольших данных стандартного размера, обычно идут по пути выделения заранее (стандартными средствами) пула, с возможностью расширения, а потом оттуда можно быстро добывать память (своими средствами). 
Велосипед еще тот, в общем-то. Читай, вроде у Мейерса в советах про выделение памяти неплохо написано.


Доморощенное дерево, может и будет тормозить, ежели под каждый элемент из хипа память выковыривать. Так ведь на то stl есть - там и память рапределяется довольно оптимально, и деревья поиска есть.


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

Городить дерево ради выделения памяти, ИМХО, бессмысленно. Смешивать задачу распределения памяти и сортировки (поиска) чисел - идеологически неправильно. 

Модератор, и что все это в Алгоритмах делает?

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

хотя, если автор выразит желание - можно перенести в C++




по теме:
если числа из не очень большого диапазона, можно рассмотреть ещё такой враиант
(к примеру числа 0..255)
делаем массив с ячейкой для каждого возможного значения
и при получении числа записываем его порядковый номер в соответствующую ячейку
занесение очередного числа - константа
поиск позиции заданного числа - тоже константа
короче всё это будет ОЧЕНЬ быстро

некоторое развитие для этого подхода: хешированные контейнеры
тут не каждому числу даётся ячейка, а группе чисел
например, считаем остаток от деления на 100 и раскидываем числа на 100 ячеек
в каждой ячейке - упорядоченный массив пар <число,позиция>
по скорости - что-то среднее между предыдущим вариантом и динамическим массивом

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