fork(2) download 
  1. #include <functional>
  2. #include <memory>
  3. #include <vector>
  4. #include <iostream>
  5. #include <cassert>
  6.  
  7.  template <class T, std::size_t N, class Allocator = std::allocator<T>>
  8.  class stack_allocator
  9.  {
  10.  	public:
  11.  
  12.  	typedef typename std::allocator_traits<Allocator>::value_type value_type;
  13.  	typedef typename std::allocator_traits<Allocator>::pointer pointer;
  14.  	typedef typename std::allocator_traits<Allocator>::const_pointer const_pointer;
  15.  	typedef typename Allocator::reference reference;
  16.  	typedef typename Allocator::const_reference const_reference;
  17.  	typedef typename std::allocator_traits<Allocator>::size_type size_type;
  18.  	typedef typename std::allocator_traits<Allocator>::difference_type difference_type;
  19.  
  20.  	typedef typename std::allocator_traits<Allocator>::const_void_pointer const_void_pointer;
  21.  	typedef Allocator allocator_type;
  22.  
  23.  	public:
  24.  
  25.  	explicit stack_allocator(const allocator_type& alloc = allocator_type()) 
  26.  		: m_allocator(alloc), m_begin(nullptr), m_end(nullptr), m_stack_pointer(nullptr)
  27.  	{ }
  28.  
  29.  	explicit stack_allocator(pointer buffer, const allocator_type& alloc = allocator_type())
  30.  		: m_allocator(alloc), m_begin(buffer), m_end(buffer + N), 
  31.  			m_stack_pointer(buffer)
  32.  	{ }
  33.  
  34.  	template <class U>
  35.  	stack_allocator(const stack_allocator<U, N, Allocator>& other)
  36.  		: m_allocator(other.m_allocator), m_begin(other.m_begin), m_end(other.m_end),
  37.  			m_stack_pointer(other.m_stack_pointer)
  38.  	{ }
  39.  
  40.  	constexpr static size_type capacity()
  41.  	{
  42.  		return N;
  43.  	}
  44.  
  45.  	pointer allocate(size_type n, const_void_pointer hint = const_void_pointer())
  46.  	{
  47.  		if (n <= std::distance(m_stack_pointer, m_end))
  48.  		{
  49.  			pointer result = m_stack_pointer;
  50.  			m_stack_pointer += n;
  51.  			return result;
  52.  		}
  53.  
  54.  		return m_allocator.allocate(n, hint);
  55.  	}
  56.  
  57.  	void deallocate(value_type* p, size_type n)
  58.  	{
  59.  		if (pointer_to_internal_buffer(p))
  60.  		{
  61.  			m_stack_pointer -= n;
  62.  		}
  63.  		else m_allocator.deallocate(p, n);	
  64.  	}
  65.  
  66.  	size_type max_size() const noexcept
  67.  	{
  68.  		return m_allocator.max_size();
  69.  	}
  70.  
  71.  	template <class U, class... Args>
  72.  	void construct(U* p, Args&&... args)
  73.  	{
  74.  		m_allocator.construct(p, std::forward<Args>(args)...);
  75.  	}
  76.  
  77.  	template <class U>
  78.  	void destroy(U* p)
  79.  	{
  80.  		m_allocator.destroy(p);
  81.  	}
  82.  
  83.  	pointer address(reference x) const
  84.  	{
  85.  		if (pointer_to_internal_buffer(std::addressof(x)))
  86.  		{
  87.  			return std::addressof(x);
  88.  		}
  89.  
  90.  		return m_allocator.address(x);
  91.  	}
  92.  
  93.  	const_pointer address(const_reference x) const
  94.  	{
  95.  		if (pointer_to_internal_buffer(std::addressof(x)))
  96.  		{
  97.  			return std::addressof(x);
  98.  		}
  99.  
  100.  		return m_allocator.address(x);
  101.  	}
  102.  
  103.  	template <class U>
  104.  	struct rebind { typedef stack_allocator<U, N, allocator_type> other; };
  105.  
  106.  	pointer buffer() const noexcept
  107.  	{
  108.  		return m_begin;
  109.  	}
  110.  
  111.  	private:
  112.  
  113.  	template <class U>
  114.  	bool pointer_to_internal_buffer(U* p) const
  115.  	{
  116.  		return (!(std::less<T*>()(p, m_begin)) && (std::less<T*>()(p, m_end)));
  117.  	}
  118.  
  119.  	pointer m_begin;
  120.  	pointer m_end;
  121.  	pointer m_stack_pointer;
  122.  	allocator_type m_allocator;
  123.  };
  124.  
  125.  template <class T1, std::size_t N, class Allocator, class T2>
  126.  bool operator == (const stack_allocator<T1, N, Allocator>& lhs, 
  127.  	const stack_allocator<T2, N, Allocator>& rhs) noexcept
  128.  {
  129.  	return lhs.buffer() == rhs.buffer();
  130.  }
  131.  
  132.  template <class T1, std::size_t N, class Allocator, class T2>
  133.  bool operator != (const stack_allocator<T1, N, Allocator>& lhs, 
  134.  	const stack_allocator<T2, N, Allocator>& rhs) noexcept
  135.  {
  136.  	return !(lhs == rhs);
  137.  }
  138.  
  139. int main()
  140. {
  141.  
  142.     const static std::size_t stack_size = 4;
  143.     int buffer[stack_size];
  144.  
  145.     typedef stack_allocator<int, stack_size> allocator_type;
  146.  
  147.     std::vector<int, allocator_type> vec((allocator_type(buffer))); // double parenthesis here for "most vexing parse" nonsense
  148.     vec.reserve(stack_size); // attempt to reserve space for 4 elements
  149.  
  150.     std::cout << vec.capacity() << std::endl;
  151.  
  152.     vec.push_back(10);
  153.     vec.push_back(20);
  154.     vec.push_back(30);
  155.     vec.push_back(40);
  156.  
  157.     // Assert that the vector is actually using our stack
  158.     //
  159.     assert(
  160.     	std::equal(
  161.     		vec.begin(), 
  162.     		vec.end(), 
  163.     		buffer, 
  164.     		[](const int& v1, const int& v2) {
  165.     			return &v1 == &v2;
  166.     		}
  167.     	)
  168.     );
  169.  
  170.     // Output some values in the stack, we see it is the same values we
  171.     // inserted in our vector.
  172.     //
  173.     std::cout << buffer[0] << std::endl;
  174.     std::cout << buffer[1] << std::endl;
  175.     std::cout << buffer[2] << std::endl;
  176.     std::cout << buffer[3] << std::endl;
  177.  
  178.     // Attempt to push back some more values.  Since our stack allocator only has 
  179. 	 // room for 4 elements, we cannot satisfy the request for an 8 element buffer.  
  180. 	 // So, the allocator quietly falls back on using std::allocator.
  181.     //
  182.     // Alternatively, you could modify the stack_allocator implementation
  183.     // to throw std::bad_alloc
  184.     //
  185.     vec.push_back(50);
  186.     vec.push_back(60);
  187.     vec.push_back(70);
  188.     vec.push_back(80);
  189.  
  190.     // Assert that we are no longer using the stack buffer
  191.     //
  192.     assert(
  193.     	!std::equal(
  194.     		vec.begin(), 
  195.     		vec.end(), 
  196.     		buffer, 
  197.     		[](const int& v1, const int& v2) {
  198.     			return &v1 == &v2;
  199.     		}
  200.     	)
  201.     );
  202.  
  203.     // Print out all the values in our vector just to make sure 
  204.     // everything is sane.
  205.     //
  206.     for (auto v : vec) std::cout << v << ", ";
  207.     std::cout << std::endl;
  208. }
Success #stdin #stdout 0s 3228KB
comments (?)
stdin 
Standard input is empty
stdout 
4
10
20
30
40
10, 20, 30, 40, 50, 60, 70, 80,
https://ideone.com/YhMZxt
language:
C++14 (gcc 8.3)
created:
9 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!