Is this standards compliant?

[ChemicalBliss]

As the title suggests, I would like to know if the following simple linked list sways in any way from the c++ standard. More specifically, if any of this *should* be done a better way to minimise UB or to maximise performance/readability.

Any thoughts would be great!

#include<cassert>

template <class T>
class IMPFixedQueue;
// Minimum Allocator Block Size
template <class T>
class IMPFixedQueueBlock
{
	friend class IMPFixedQueue<T>;
	IMPFixedQueueBlock * next_;
	T * pBlock_;

private:
	IMPFixedQueueBlock();
public:
	IMPFixedQueueBlock(T * t) : pBlock_(t)
	{

	}
	~IMPFixedQueueBlock()
	{
		pBlock_ = nullptr;
	}
};

// Generic fixed-size queue type (pre-allocated singly linked list of T*)
template <class T>
class IMPFixedQueue
{
	public:
	private:
		size_t count_{ 0 };							// Current Queue Size
		size_t max_{ 1 };							// Max Queue Size
		void * pQueuePool_{ nullptr };				// Fixed Queue Pool
		IMPFixedQueueBlock<T> * head_{ nullptr };	// Block to give
		IMPFixedQueueBlock<T> * tail_{ nullptr };	// Block to append to

	public:
		IMPFixedQueue(size_t count) : max_(count)
		{
			pQueuePool_ = std::malloc(sizeof(IMPFixedQueueBlock<T>) * count);
			std::memset(pQueuePool_, 0, sizeof(IMPFixedQueueBlock<T>) * count);
		};
		~IMPFixedQueue()
		{
			free(pQueuePool_);
		}

		// Add item to end (wrap)
		void push(T * t)
		{
			assert(count_<max_);

			uintptr_t nextAddr;
			uintptr_t poolAddr = reinterpret_cast<uintptr_t>(pQueuePool_);

			if (count_ == 0) // First element
			{
				tail_ = head_ = new (reinterpret_cast<void*>(poolAddr)) IMPFixedQueueBlock<T>(t);
			}
			else // another element
			{
				nextAddr = reinterpret_cast<uintptr_t>(tail_) + sizeof(IMPFixedQueueBlock<T>);

				// wrap out of bounds
				if (nextAddr >= poolAddr + (max_ * sizeof(IMPFixedQueueBlock<T>)))
					nextAddr = poolAddr;

				tail_->next_ = new (reinterpret_cast<void*>(nextAddr)) IMPFixedQueueBlock<T>(t); // link tail
				tail_ = tail_->next_; // move tail
			}


			count_++;
		}

		// remove first item
		void pop()
		{
			assert(count_ > 0);
			IMPFixedQueueBlock<T> * oldHead = head_;
			head_ = head_->next_; // (could be null ptr, thats fine)
			oldHead->~IMPFixedQueueBlock<T>();
			count_--;
		}

		T * front()
		{
			assert(count_ > 0);
			return (head_ == nullptr)? nullptr : head_->pBlock_;
		}
	private:
};

Idea/Explanation of prototype:
Simple, preallocate storage for n number of QueueBlock<T>, (I know this doesnt actually allocate space or contain T, only a pointer to a T).
This gives me a simple list of pointers to objects I can manipulate, for ex. a "Free Block" list for an allocator.
Fixed-Size Queue style means I can easily recycle old nodes without compaction or linear iteration (The idea is to keep constant time).

[Duthomhas]

Your code knows too much about the workings of memory management...

The Standard Library uses allocators to manage memory, so you should be writing an allocator and using one of the standard objects (such as a std::queue<T,std::deque<T,my_special_allocator<T>>>).

As for efficiency, without hard profiling data about memory access patterns you are probably wasting your time.

Your code is pleasantly readable.

[ChemicalBliss]

Your code knows too much about the workings of memory management...

I assume this is not good for portability.

The Standard Library uses allocators to manage memory, so you should be writing an allocator and using one of the standard objects (such as a std::queue<T,std::deque<T,my_special_allocator<T>>>).

Nice! I've only recently even seen anything about standard allocators, I'm going to try to research as much as I can, do you have any good on-line material?

As for efficiency, without hard profiling data about memory access patterns you are probably wasting your time.

My idea is to stop calling new for every object, and to prevent re-allocation using standard rage types. Using a Fixed-size queue to allocate the maximum amount of memory my queue will need in my program seemed like the way to go. I guess this ties in with using std allocs.
Is a fixed size allocator possible with a custom std allocator? (might be a silly question)

Your code is pleasantly readable.

Thanks! that means a lot, I'm trying to keep everything I write as consistent and clean, easy to understand as possible without bloating comments or long names.


Could I ask someone their opinion - is there any actual Undefined Behaviour anyone can pick out here?

Thanks!

[ChemicalBliss]

Bump;

I've looked at STL allocators, and to me it seems like to use an STL container with my allocator, I would need to generate the T's (construct) outside of the container, and then "copy/swap/move to the container. This adds the additional overhead of a temporary T object.

My method shows that I construct the T in-place, in the container, it is also destructed inside the container. So now I'm wondering, is this method even possible with STL containers? or a custom STL compatible allocator? Should I write an STL fixed allocator and just roll my own Container(that constructs in-place)?

Thanks!

-footnote- (I'm sure I am going to get some "why, what purpose, have you benchmarked? etc. I just want to know if this is "defined as Undefined behaviour" or some such. I know EA Games has rolled their own STL container/allocator implementations, So it must be ok if you have reason?)

[Cubbi]

My method shows that I construct the T in-place, in the container, it is also destructed inside the container. So now I'm wondering, is this method even possible with STL containers?

All standard C++ containers can construct their elements in-place, in the container (as of C++11), see std::vector::emplace_back for example.

Is a fixed size allocator possible with a custom std allocator?

of course, take a look at some pool or stack allocators for insporation.

[ChemicalBliss]

Oh damn!
I feel so stupid I can't believe I missed that. I'm going to work on making this whole thing properly using STL.

Thanks Cubbi!