fork download
copy 
  1.  
  2. #include <time.h>
  3.  
  4. #include <set>
  5. #include <iostream>
  6. #include <functional>
  7. #include <vector>
  8.  
  9. #include <cstddef>
  10. #include <cstdlib>
  11.  
  12. #include <limits>
  13. #include <new>
  14.  
  15. namespace block_allocator {
  16.  
  17. template <class T, unsigned N = 32>
  18. class block_allocator {
  19.     void** blocks;
  20.     void** free_blocks;
  21.     int allocated;
  22.  
  23. public:
  24.     typedef size_t size_type;
  25.     typedef ptrdiff_t difference_type;
  26.     typedef T* pointer;
  27.     typedef const T* const_pointer;
  28.     typedef T& reference;
  29.     typedef const T& const_reference;
  30.     typedef T value_type;
  31.  
  32.     template <class U>
  33.     struct rebind {
  34.         typedef block_allocator<U, N> other;
  35.     };
  36.  
  37.     block_allocator()
  38.         : blocks()
  39.         , free_blocks()
  40.         , allocated()
  41.     {
  42.     }
  43.  
  44.     template<class U, unsigned M>
  45.     block_allocator(const block_allocator<U, M>&)
  46.         : blocks()
  47.         , free_blocks()
  48.         , allocated()
  49.     {
  50.     }
  51.  
  52.     ~block_allocator()
  53.     {
  54.         while (blocks) {
  55.             void** next = reinterpret_cast<void**>(*blocks);
  56.             free(blocks - block_elements);
  57.             blocks = next;
  58.         }
  59.     }
  60.  
  61.     pointer address(reference x) const
  62.     {
  63.         return &x;
  64.     }
  65.  
  66.     const_pointer address(const_reference x) const
  67.     {
  68.         return &x;
  69.     }
  70.  
  71.     pointer allocate(size_type n, const void* = 0)
  72.     {
  73.         if (n == 1) {
  74.             if (free_blocks) {
  75.                 pointer result = reinterpret_cast<pointer>(free_blocks);
  76.                 free_blocks = reinterpret_cast<void**>(*free_blocks);
  77.                 return result;
  78.             } else {
  79.                 void** new_block = do_alloc<void*>(area_size);
  80.                 new_block[block_elements] = blocks;
  81.                 blocks = &new_block[block_elements];
  82.                 new_block[(N - 1) * multiplier] = 0;
  83.                 for (size_type i = 2; i < N; ++i) {
  84.                     new_block[(i - 1) * multiplier] =
  85.                         &new_block[i * multiplier];
  86.                 }
  87.                 free_blocks = &new_block[multiplier];
  88.                 return reinterpret_cast<pointer>(new_block);
  89.             }
  90.         } else {
  91.             return do_alloc<T>(n * sizeof(T));
  92.         }
  93.     }
  94.  
  95.     void deallocate(pointer p, size_type n)
  96.     {
  97.         if (n == 1) {
  98.             *reinterpret_cast<void**>(p) = free_blocks;
  99.             free_blocks = reinterpret_cast<void**>(p);
  100.         } else {
  101.             free(p);
  102.         }
  103.     }
  104.  
  105.     size_type max_size() const
  106.     {
  107.         return std::numeric_limits<size_type>::max();
  108.     }
  109.  
  110.     void construct(pointer p, const T& val)
  111.     {
  112.         new(p) T(val);
  113.     }
  114.  
  115.     void destroy(pointer p)
  116.     {
  117.         p->~T();
  118.     }
  119.  
  120. private:
  121.     template <class U>
  122.     static U* do_alloc(size_type n) {
  123.         U* result = reinterpret_cast<U*>(malloc(n));
  124.         if (result) {
  125.             return result;
  126.         } else {
  127.             throw std::bad_alloc();
  128.         }
  129.     }
  130.  
  131.     static char check[sizeof(T) % sizeof(void*) == 0 ? 1 : -1];
  132.     static const size_type multiplier = sizeof(T) / sizeof(void*);
  133.     static const size_type block_elements = multiplier * N;
  134.     static const size_type area_size = sizeof(T) * N + sizeof(void*);
  135. };
  136.  
  137. }
  138.  
  139. std::vector<int> input;
  140.  
  141. template <class Cont>
  142. void do_test()
  143. {
  144.     Cont c;
  145.     for (std::vector<int>::const_iterator iter = input.begin(), end = input.end(); iter != end; ++iter) {
  146.         c.insert(*iter);
  147.     }
  148. }
  149.  
  150. int main()
  151. {
  152.     typedef void (*test)();
  153.     test t[] = {
  154.         do_test<std::set<int> >,
  155.         do_test<std::set<int, std::less<int>, block_allocator::block_allocator<int, 1024> > >
  156.     };
  157.     int size = 1000000;
  158.     for (int i = 0; i < size; ++i) {
  159.         input.push_back(i + i % 3);
  160.     }
  161.     size = sizeof t / sizeof t[0];
  162.     for (int i = 0; i < size; ++i) {
  163.         const clock_t begin = clock();
  164.         t[i]();
  165.         std::cout << clock() - begin << std::endl;
  166.     }
  167. }
Success #stdin #stdout 0.69s 3180KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
470000
190000
https://ideone.com/eWMZb
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!