Что делает STL быстро? [закрытый]
6 ответов
Алгоритмы в STL изучаются годами всеми уровнями математиков и компьютерщиков, и они обычно используют абсолютные наиболее эффективные алгоритмы, которые ваша реализация может не использовать. Общая реализация, вероятно, не самая быстрая, но легче всего понять; возможно, STL использует более оптимизированную реализацию.
-121--3842515- NSOutlineView наследует от NSTableView , поэтому получаются хорошие методы, такие как selectedRow :
id selectedItem = [outlineView itemAtRow:[outlineView selectedRow]];
STL алгоритмы, такие как , для _ каждого берут объекты функций, которые могут быть C, с другой стороны, использует указатели функций, которые гораздо сложнее оптимизировать компилятору.
Это делает большую разницу в некоторых алгоритмах, таких как сортировка, в которых функция компаратора должна вызываться много раз.
Википедия имеет дополнительную информацию на случай, если вы заинтересованы.
EDIT:
Что касается класса векторов STL, я не думаю, что это обязательно быстрее, чем то, что вы можете найти в, скажем, glibc.
Стандартная библиотека использует хорошие алгоритмы, например, в случае с массивом (std :: vector) она обычно удваивает объем хранилища каждый раз, когда у вас заканчивается пространства, в то время как наивная реализация может каждый раз увеличивать объем памяти на один элемент. Поскольку увеличение объема хранилища происходит очень медленно (все существующие данные необходимо скопировать из старого распределения в новое распределение), это может иметь огромное значение.
Точно так же все остальные алгоритмы реализованы довольно оптимальным образом. Стандартная библиотека обычно не использует никаких циклов развертывания или других подобных оптимизаций на уровне исходного кода. Это просто обычный хороший и простой код (с ужасными именами переменных и множеством шаблонов), который затем оптимизирует компилятор.
То, что я сказал, не определено стандартом C ++, но это обычная практика в существующих реализациях.
Большинство классов массивов увеличивают размер на постоянное приращение, а не на постоянный коэффициент (как того требует стандартная библиотека). Это означает, что вставка элемента занимает примерно линейное время, а не амортизированное постоянное время для стандартной библиотеки.
Помимо хороших общих алгоритмов (как отмечали другие), STL также довольно эффективен из-за интенсивного использования шаблонов.
У метапрограмм шаблонов есть замечательная особенность, заключающаяся в том, что компилятор их агрессивно оптимизирует. Некоторые компиляторы очень хороши в этом и сокращают шаблоны до наименьшего, наиболее эффективного, необходимого кода для данной задачи. И в целом это означает, что функции встраиваются, когда это возможно, а код для взаимодействия с конкретным типом сводится к его простейшей форме. Большинство реализаций STL (и большая часть Boost), конечно, в полной мере используют это преимущество.
код написан в дружественной компилятору манере, например, с инлайнингом и т.д.
конечно, алгоритмы, которые они используют, являются самыми современными.
Алгоритмы в STL изучались годами математиками и компьютерщиками всех уровней, и они обычно используют абсолютные наиболее эффективные алгоритмы, которые ваша реализация может не использовать. Обычная реализация - это та, которая, вероятно, не самая быстрая, но самая простая для понимания; STL, вероятно, использует более оптимизированную реализацию.