Создан стек (4 стр)

/*----------------------------------------------------------------------------*/
/*                                 6y6yka Engine                              */
/*----------------------------------------------------------------------------*/
#ifndef _B_STACK_H_
#define _B_STACK_H_
/*----------------------------------------------------------------------------*/
#include <cstdlib>
#include <cassert>
/*----------------------------------------------------------------------------*/
/* класс bStack                                                               */
/* описание:                                                                  */
/*     реализация структуры типа стек                                         */
/* методы:                                                                    */
/*     Push    помещает данные в стек                                         */
/*     Pop     удаляет верхний элемент                                        */
/*     Top     возвращает ссылку на верхний элемент                           */
/*     Length  возвращает количество элементов                                */
/*     Size    возвращает объем занимаемой памяти                             */
/*     Resize  резервирует память для будущих действий                        */
/*----------------------------------------------------------------------------*/
template <typename bStackType>
class bStack
{
public:
  bStack();
  ~bStack();

  void Push(const bStackType &item);
  void Pop();
  bStackType &Top() const;

  int Length()      const;
  int Size()        const;
  int Resize(unsigned int new_size);
private:
  struct data_pool;

  data_pool *pool; // список пулов
  data_pool *old_pool;
  int allocated;   // всего выделено памяти(в итемах)
  int length;      // количество использующихся итемов

  static const int defsize = 10;

  bStack(const bStack &);
  bStack &operator =(const bStack &);
};
/*----------------------------------------------------------------------------*/
/* bStack<bStackType>::bStack                                                 */
/*----------------------------------------------------------------------------*/
template <typename bStackType>
inline bStack<bStackType>::bStack()
{
  pool      = old_pool = 0;
  allocated = length   = 0;
}
/*----------------------------------------------------------------------------*/
/* bStack<bStackType>::~bStack                                                */
/*----------------------------------------------------------------------------*/
template <typename bStackType>
inline bStack<bStackType>::~bStack()
{
  free(old_pool);

  if(pool)
    pool->size -= allocated - length; // вычитаем число пустых ячеек

  while(pool)
  {
    for(int i = 0; i < pool->size; i++)
      pool->data[i].~bStackType();

    old_pool = pool;
    pool = pool->next;
    free(old_pool);
  }
}
/*----------------------------------------------------------------------------*/
/* bStack<bStackType>::Push                                                   */
/* описание:                                                                  */
/*     помещает новый элемент в стек                                          */
/* аргументы:                                                                 */
/*     item    ссылка на новый элемент                                        */
/*----------------------------------------------------------------------------*/
template <typename bStackType>
inline void bStack<bStackType>::Push(const bStackType &item)
{
  if(allocated == length) // если стек полон или совсем пуст
  {
    if(!old_pool)
      Resize(allocated * 2);

    old_pool->next = pool;
    pool = old_pool;
    old_pool = 0;
    allocated += pool->size;
  }

  new(&pool->data[pool->size - (allocated - length++)]) bStackType(item);
}
/*----------------------------------------------------------------------------*/
/* bStack<bStackType>::Pop                                                    */
/* описание:                                                                  */
/*     удаляет элемент с верхушки стека                                       */
/*----------------------------------------------------------------------------*/
template <typename bStackType>
inline void bStack<bStackType>::Pop()
{
  int i = pool->size - (allocated - --length);
  assert(!(i < 0));             // недопущение противоправных действий.

  pool->data[i].~bStackType();

  if(!i && pool->next)
  {
    if(old_pool)
      free(old_pool);

    allocated -= pool->size;
    old_pool = pool;
    pool = pool->next;
  }
}
/*----------------------------------------------------------------------------*/
/* bStack<bStackType>::Top                                                    */
/* описание:                                                                  */
/*     возвращает ссылку на верхний элемент                                   */
/*----------------------------------------------------------------------------*/
template <typename bStackType>
inline bStackType &bStack<bStackType>::Top() const
{
  return pool->data[pool->size - (allocated - (length - 1))];
}
/*----------------------------------------------------------------------------*/
/* bStack<bStackType>::Leangth                                                */
/* описание:                                                                  */
/*     возвращает количество элементов в стеке                                */
/*----------------------------------------------------------------------------*/
template <typename bStackType>
inline int bStack<bStackType>::Length() const
{
  return length;
}
/*----------------------------------------------------------------------------*/
/* bStack<bStackType>::Size                                                   */
/* описание:                                                                  */
/*     возвращает максимальное количество элементов.                          */
/*----------------------------------------------------------------------------*/
template <typename bStackType>
inline int bStack<bStackType>::Size() const
{
  return allocated;
}
/*----------------------------------------------------------------------------*/
/* bStack<bStackType>::Resize                                                 */
/* описание:                                                                  */
/*     увеличивает максимально колличество элементов                          */
/* аргументы:                                                                 */
/*     new_size    новый размер в итемах                                      */
/* возвращает:                                                                */
/*     полный размер стека в итемах                                           */
/*----------------------------------------------------------------------------*/
template <typename bStackType>
inline int bStack<bStackType>::Resize(unsigned int new_size)
{
  free(old_pool);

  old_pool = static_cast<data_pool *>(
           malloc(sizeof(data_pool) + sizeof(bStackType) * 
               (new_size ? new_size : new_size = defsize)));
  old_pool->size = new_size;
  old_pool->data = reinterpret_cast<bStackType *>(
                 reinterpret_cast<size_t *>(&old_pool->data) + 1);

  return allocated;
}
/*----------------------------------------------------------------------------*/
/* bStack<bStackType>::data_pool                                              */
/* описание:                                                                  */
/*     структура для организации списка                                       */
/*----------------------------------------------------------------------------*/
template <typename bStackType>
struct bStack<bStackType>::data_pool
{
  int size;         // размер куска в итемах
  data_pool *next;  // указатель на предыдущий пулл
  bStackType *data; // указатель на начало данных
};
/*----------------------------------------------------------------------------*/
#endif /* _B_STACK_H_ */

#include <string>
#include <iostream>
#include <stack>
#include <windows.h>
#include "b_stack.h"

int main()
{
  bStack<std::string> bstack;
  std::stack<std::string> sstack;
  LARGE_INTEGER b_1, b_2, s_1, s_2, freq;
  double br, sr;

  std::string test = "Medved";
  std::string result;

  QueryPerformanceFrequency(&freq);

  QueryPerformanceCounter(&b_1);

  for(int i = 0; i < 1000000; i++)
    bstack.Push(test);
  for(int i = 0; i < 1000000; i++)
  {
    result = bstack.Top();
    bstack.Pop();
  }
  for(int i = 0; i < 1000000; i++)
  {
    bstack.Push(test);
    result = bstack.Top();
    bstack.Pop();
  }
  QueryPerformanceCounter(&b_2);
  br = (double)(b_2.QuadPart - b_1.QuadPart)/freq.QuadPart;

  QueryPerformanceCounter(&s_1);
  for(int i = 0; i < 1000000; i++)
    sstack.push(test);
  for(int i = 0; i < 1000000; i++)
  {
    result = sstack.top();
    sstack.pop();
  }
  for(int i = 0; i < 1000000; i++)
  {
    sstack.push(test);
    result = sstack.top();
    sstack.pop();
  }
  QueryPerformanceCounter(&s_2);
  sr = (double)(s_2.QuadPart - s_1.QuadPart)/freq.QuadPart;

  std::cout << "bstack result: " << br << std::endl;
  std::cout << "std::stack result: " << sr << std::endl;
  system("pause");

  return 0;
}