суббота, 2 мая 2009 г.

FastArray

Сейчас очень много сделано в движке. Есть некоторые недоделанные реализации чего либо.
К примеру 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

Такая реализация обеспечивает быстрое добавление в конец и очистку массива, так-же работу с итераторами. Единственным минусом является небезопасное добавление, если число элементов превышает длину массива.