К примеру Hierarchy Occlusion Culling, обход SceneGraph для поиска объектов являющихся RenderTarget'ами вода, зеркала и т.д. Постепенно проводиться оптимизация движка. В частности замер профайлером работу отдельных функций. На данный момент есть частое добавление объектов в динамический массив в каждом кадре. Как для от рисовки в текстуру теней так и для поиска видимых объектов. Для этого использовался ранее обычный std::vector с заранее вызванным std::vector::reserve. Почитав пост известного всем IronPeter'а Банановые шкурки, я подумал что сам метод std::vector::push_back уж очень универсален, там есть проверка на текущий размер с выделением памяти при необходимости и много других вызовов. К примеру std::vector::operator [] очень быстрый, но лишен универсальности, к примеру проверка выхода за диапазон, для этого есть std::vector::at. Иногда возникает вопрос, почему разработчик STL Александр Степанов не добавил быструю реализацию push_back, назвав ее к примеру fast_push_back?
Для некоторых частных специфических задач, требующих минимальной загрузки CPU, проверять выход за пределы не нужно вообще, к примеру как в этом случае - быстрое добавление данных с инкрементом указателя, который смещается к концу масса, причем размер массива уже известен.
Поэтому я написал свою довольно простую реализацию FastArray унаследовав с защищенным доступом от std::vector. Реализация выглядит так:
#ifndef __FASTARRAY_H__ #define __FASTARRAY_H__ #include "exceptions.h" #include <cassert> #include <vector> // Fast Dynamic Array template<typename T> class FastArray : protected std::vector<T> { private: typedef std::vector<T> BaseClass; T* last; public: typedef T* iterator; typedef const T* const_iterator; void resize(size_t count) { BaseClass::resize(count); last = &*BaseClass::end(); } void reserve(size_t count) { BaseClass::reserve(count); last = &*BaseClass::end(); } const_iterator end() const { return last; } iterator end() { return last; } const_iterator begin() const { return &*BaseClass::begin(); } iterator begin() { return &*BaseClass::begin(); } T& back() { assert(last && "NULL Pointer"); assert(!empty() && "Empty Array"); return *(last - 1); } const T& back() const { assert(last && "NULL Pointer"); assert(!empty() && "Empty Array"); return *(last - 1); } T& front() { assert(!empty() && "Empty Array"); BaseClass::front(); } const T& front() const { assert(!empty() && "Empty Array"); return BaseClass::front(); } bool empty() const { return &BaseClass::front() == last; } size_t size() const { assert(last >= &*begin() && "Out of Range"); return static_cast<size_t>(last - &*begin()); } size_t capacity() const { return BaseClass::capacity(); } void pop_back() { assert(last && "NULL Pointer"); assert(last >= &*begin() && "Out of Range"); --last; } void push_back(const T& val) { assert(last && "NULL Pointer"); *(last++) = val; } T& operator [] (size_t index) { assert(&*begin() + index < last && "Out of Range"); return *(begin() + index); } const T& operator [] (size_t index) const { assert(&*begin() + index < last && "Out of Range"); return *(begin() + index); } void clear() { last = &*begin(); } FastArray(size_t count, const T& val = T()) : BaseClass(count, val), last(&BaseClass::back()) { } FastArray() : last(&BaseClass::back()) { } ~FastArray() { } }; #endif |
Такая реализация обеспечивает быстрое добавление в конец и очистку массива, так-же работу с итераторами. Единственным минусом является небезопасное добавление, если число элементов превышает длину массива.