Junior C++ developer questions - templates

[deimos]

I'm trying to learn C++ and I'm currently trying to get my head around templates. I'm porting some C code I wrote a while back that handles object pooling and queuing. This is what I have at the moment:

queue.h

#pragma once

#include <exec/types.h>

namespace data_structures {

    // Queue, implemented as a circular buffer.

    template <typename type, UWORD maxLength>
    class Queue {

        public:

            Queue(type * * contents);

            BOOL enqueue(type * element);
            type * dequeue();

        private:

            type * * contents;
            UWORD length;
            UWORD readIndex;
            UWORD writeIndex;

    };

    template <typename type, UWORD maxLength>
    Queue<type, maxLength>::Queue(type * * contents)
        : contents(contents),
          length(0),
          readIndex(0),
          writeIndex(0)
    { }

    template <typename type, UWORD maxLength>
    BOOL Queue<type, maxLength>::enqueue(type * element) {
        if (length > maxLength)
            return FALSE;

        contents[writeIndex] = element;

        length++;

        writeIndex++;
        if (writeIndex == maxLength)
            writeIndex = 0;

        return TRUE;
    }

    template <typename type, UWORD maxLength>
    type * Queue<type, maxLength>::dequeue() {
        if (length == 0)
            return NULL;
        
        type * element = contents[readIndex];

        length--;

        readIndex++;
        if (readIndex == maxLength)
            readIndex = 0;
        
        return element;
    }

}

I'm sure this code will work as it's converted from working C code, but my problem is that I really don't know if what I've done could be considered "good" in the C++ world. Every example I can find online for similar classes uses standard library / STL or Boost stuff, which is not available to me.

If anyone wants to give constructive criticism of my code or my approach I'd really appreciate it. My Pool class, which is what I need for the next step in the actual project I'm working on is just going to be a layer on top of this Queue.

[paraj]

It looks like you have an off-by-one error in your enqueue function (the check should be length >= maxLength, or just length == maxLength).
You may want to write some tests

In C++ you'd normally have the class manage resources (in this case memory). Having to alloc/free memory from the outside is error-prone (you face lifetime issues, possible memory leaks and have to make sure you adjust both the maxLength template argument and allocation size when making changes). I'd just have an array as a data member in the class (or handle allocation in the constructor and freeing in the destructor). You probably also want to prohibit copying of the queue (or make sure you handle it properly).

Your queue type currently only handles pointers, and that's fine. If you want it to be more generic, be aware that there will be some issues with your current interface (namely getting dequeue right), see http://www.gotw.ca/gotw/008.htm. This is the reason std::queue from the standard library splits the operation/check up into three methods: empty/front and pop. Even if you don't care about exception safety, your queue has the (admittedly minor) issue that if you enqueue a "NULL", later on when you dequeue it, you won't know whether it was because you got a NULL or the queue was empty.

[Thomas Richter]

Originally Posted by deimos

I'm trying to learn C++ and I'm currently trying to get my head around templates. I'm porting some C code I wrote a while back that handles object pooling and queuing. I'm sure this code will work as it's converted from working C code, but my problem is that I really don't know if what I've done could be considered "good" in the C++ world. Every example I can find online for similar classes uses standard library / STL or Boost stuff, which is not available to me.

Amiga is not exactly a C++ friendly environment, but those C++ compilers that are full C++ compilers (that is, not SAS/C) come with a STL port. Good C++ style would be to use STL when possible, that is, avoid to reinvent the wheel. You find queue classes there that are ready to use.



If you want advice on how to write C++, then this is not the right forum. I suggest reading some books, or check comp.lang.c++.moderated (the real C++ experts are there). For example, I would recommend "Excepitonal C++" by Herb Sutter as a good collection of exercises and examples.

[deimos]

Originally Posted by paraj

It looks like you have an off-by-one error in your enqueue function (the check should be length >= maxLength, or just length == maxLength).
You may want to write some tests

You are correct on both points, particularly about testig. My original C code was:

    if (queue->length == queue->_maxLength)
        return FALSE;

So I must have mistyped when porting it.

In C++ you'd normally have the class manage resources (in this case memory). Having to alloc/free memory from the outside is error-prone (you face lifetime issues, possible memory leaks and have to make sure you adjust both the maxLength template argument and allocation size when making changes). I'd just have an array as a data member in the class (or handle allocation in the constructor and freeing in the destructor). You probably also want to prohibit copying of the queue (or make sure you handle it properly).

My intention was to have classes for specific cases, either through inheritance or composition, that would handle the memory allocation and initialisation of the objects. Mainly because the initialisation will be different in each case. Currently I have:

    class SpanPool : public Pool<Span, spanPoolSize> {

        public:

            SpanPool();

        protected:

            Span * * createContents();

    };

    SpanPool::SpanPool() : Pool(createContents()) { }

    Span * * SpanPool::createContents() {
        Span * spans = new Span[spanPoolSize];
        Span * * spanPoolContents = new Span * [spanPoolSize];
        for (UWORD i = 0; i < spanPoolSize; i++)
            spanPoolContents[i] = &spans[i];

        return spanPoolContents;
    }

I think this achieves most of what you're suggesting, but I don't know if it's the cleanest way.

As for prohibiting copying of the queue, I guess you mean deleting the default copy constructors? I know of that, but not quite enough to implement it yet.

Your queue type currently only handles pointers, and that's fine. If you want it to be more generic, be aware that there will be some issues with your current interface (namely getting dequeue right), see http://www.gotw.ca/gotw/008.htm. This is the reason std::queue from the standard library splits the operation/check up into three methods: empty/front and pop. Even if you don't care about exception safety, your queue has the (admittedly minor) issue that if you enqueue a "NULL", later on when you dequeue it, you won't know whether it was because you got a NULL or the queue was empty.

I can now see that I should be queueing things, and not pointers to things, so that I can queue pointers to things just as another kind of thing. Thanks.

I'll read that link properly. I don't have exceptions enabled, but I might learn something in any case.

[deimos]

Originally Posted by Thomas Richter

If you want advice on how to write C++, then this is not the right forum. I suggest reading some books

You sure do know how to make someone feel welcome.

[Thomas Richter]

Sorry, but this doesn't make things less true, and I surely didn't want to upset you. There are really many better places to collect advice for C++, from people with a much stronger background in C++. I provided links to at least two resources where you find more professional advice than here.

[jotd]

there is stackoverflow but you need to focus on your exact problem. you cannot just dump your code and expect people to debug it.

[deimos]

Originally Posted by Thomas Richter

Sorry, but this doesn't make things less true, and I surely didn't want to upset you. There are really many better places to collect advice for C++, from people with a much stronger background in C++. I provided links to at least two resources where you find more professional advice than here.

I said that STL wasn't available for me, you said "use STL". How did you think you were helping?

[deimos]

Originally Posted by jotd

there is stackoverflow but you need to focus on your exact problem. you cannot just dump your code and expect people to debug it.

Did I ask for debugging? No I didn't, I asked for constructive criticism.

[jotd]

in that case you can submit your code to https://codereview.stackexchange.com/

(and cut the aggressivity, really, people here are trying to help, maybe they read too quickly but they're not trying to talk down to you)

[deimos]

Originally Posted by jotd

in that case you can submit your code to https://codereview.stackexchange.com/

(and cut the aggressivity, really, people here are trying to help, maybe they read too quickly but they're not trying to talk down to you)

Not trying to talk down to me? How would you interpret "you cannot just dump your code and expect people to debug it" in any other way?

[Jobbo]

Deimos
Your code looks perfectly reasonable as a use of templates and classes to generalize the code and give it a nicer interface than straight C.
There’s really no other magic C++ or the standard libraries have that you’re missing out on.
Most games are written in C with some C++ features and almost never using the standard libraries.
Tools can blur the line and use the standard libraries where tightly controlling performance and resources are less important.
You’ll hear a lot of dogma about how you are supposed to use C++ but you can safely ignore all that and just use what features are actually helpful as you already have!

[deimos]

Originally Posted by Jobbo

Deimos
Your code looks perfectly reasonable as a use of templates and classes to generalize the code and give it a nicer interface than straight C.
There’s really no other magic C++ or the standard libraries have that you’re missing out on.
Most games are written in C with some C++ features and almost never using the standard libraries.
Tools can blur the line and use the standard libraries where tightly controlling performance and resources are less important.
You’ll hear a lot of dogma about how you are supposed to use C++ but you can safely ignore all that and just use what features are actually helpful as you already have!

Thank you Jobbo.

I've made some of the changes suggested by paraj and I'm going to write a few tests. This code should help me progress my span buffer experiments.

[Jobbo]

One thing that occurs to me is that if you are implementing a pool of objects then a potentially better approach would be a free list. Since only free objects need to be in the list you can just overlay a next pointer or index. Meaning you won’t waste space. You can maybe use a Union or just some casts to access the next pointer. I can dig up an example later if you like.

[Thomas Richter]

Originally Posted by deimos

I said that STL wasn't available for me, you said "use STL". How did you think you were helping?

The STL is a part of C++, really, so please use it if you only need a queue, I'm serious, and I'm not saying this to set you up.

Concerning your code, your queue only stores pointers, not arbitrary types, which is a restriction, and instead of returning booleans as success indicators, a C++-ish way of doing such things is to throw exceptions in exceptional situations. Concerning learning material, I didn't mention "Exceptional C++" out of nowhere. It is really a good book, and while it does not discuss a queue class, it has a lengthly and very instructive discussion of a stack class by one of the best C++ insiders, with many of the pitfalls one can trap into.

Thus, I'm sorry, but I can only repeat myself. If you want to learn some serious C++, please check some of the sources I provided. This is really not quite the right place.

If you don't, and only need a queue, well, as said, the STL works perfectly fine for such cases, it's made for exactly that. It is part of any C++ compiler I know of, as it is also part of the C++ ISO standard (for exactly that purpose).

[Jobbo]

Just to add more game developer perspective. Almost no games use exceptions either. They add a global performance cost not worth paying. Also in a game you don’t really want to handle problems afterward. You want to anticipate them ahead of time and avoid them.

[deimos]

Originally Posted by Thomas Richter

The STL is a part of C++, really, so please use it if you only need a queue, I'm serious, and I'm not saying this to set you up.

This C++ environment does not come with a standard library. There is no STL.

Concerning your code, your queue only stores pointers, not arbitrary types, which is a restriction, and instead of returning booleans as success indicators, a C++-ish way of doing such things is to throw exceptions in exceptional situations.

These points were raised by paraj, and I've already addressed the pointer issue, and added isEmpty and isFull methods to replace returning success indicators. This is fine to me as it is my job to ensure these situations never happen.

Exceptions are not enabled for me.

Concerning learning material, I didn't mention "Exceptional C++" out of nowhere. It is really a good book, and while it does not discuss a queue class, it has a lengthly and very instructive discussion of a stack class by one of the best C++ insiders, with many of the pitfalls one can trap into.

Does it cover how to code for a 35 year old system using an environment that doesn't support the entire C++ standard?

Thus, I'm sorry, but I can only repeat myself. If you want to learn some serious C++, please check some of the sources I provided. This is really not quite the right place.

I wonder, do the AMOS or Blitz Basic sub forums turn away people who want to learn those languages?

If you don't, and only need a queue, well, as said, the STL works perfectly fine for such cases, it's made for exactly that. It is part of any C++ compiler I know of, as it is also part of the C++ ISO standard (for exactly that purpose).

[Thomas Richter]

Originally Posted by deimos

This C++ environment does not come with a standard library. There is no STL.

Then probably either use a C++ compiler that supports C++, or check for another language. The STL is part of C++ since a long time.

Originally Posted by deimos

Exceptions are not enabled for me.

Exceptions are also part of C++ since a long time.

Originally Posted by deimos

Does it cover how to code for a 35 year old system using an environment that doesn't support the entire C++ standard?

It is about style, design and C++. If you don't have a C++ compiler, but some other language, it's not quite appropriate, of course, but you can still learn a lot from it.

Originally Posted by deimos

I wonder, do the AMOS or Blitz Basic sub forums turn away people who want to learn those languages?

I wonder if you want a language whether it wouldn't be better to get a compiler that supports the language. On Amiga, the GNU compiler comes to my mind, it does support C++. For example unlike SAS/C, which does not support C++ (but only some very incomplete pre-cursor of it that is not useful for all-day purpose, and was never meant to be).



You also asked for critique, and here is mine. If you don't want to listen, and don't want to learn C++, then please don't shoot the messenger. Your class is not quite "up to style", and not quite the way how a C++ is generally understood to be used.

[paraj]

First let me say that experimenting and reinventing the wheel is a great way to learn, so definitely keep doing that! Since I don't know what you're trying to achieve it's hard to give specific recommendations, but I think you may be too trying to go too generic too soon. You probably don't need to actually support arbitrary allocation strategies for example like the standard library (tries) to support via it's Allocator type parameter to containers.
It also seems like you're making quite a number of dynamic memory allocations, maybe that's necessary for what you're doing, but it's something I'd consider reviewing.

My general recommendation would be to start by creating concrete classes (i.e. not specialized) that do what you actually need in your program, and only start templating once the need arises. Say a Span* fixed size queue that holds 512 elements. When it turns out you need more than one of those and it needs another size: That's when you convert your class to a templated one. Later on you might (or not and you've saved a bunch of work and debugging) need a fixed size queue of chars, and you add the type as a template parameter and consolidate.
Of course feel free to skip a step or two if you know in advance that you actually need the flexibility, but be careful in jumping directly to a full generic solution. YAGNI.
You can always refactor your code later on to avoid code duplication.

A fixed sized queue is BTW a great example of something the standard library doesn't supply, and where it can make sense to roll your own (or use someone else's work). Also consider if you can use something like EASTL (https://github.com/electronicarts/EA.../include/EASTL).

As for prohibiting copying of the queue, I guess you mean deleting the default copy constructors? I know of that, but not quite enough to implement it yet.

No need to worry about it too much, but yes. You can do (C++11 and onwards):

public:
    Queue(const Queue&) = delete;            // No copy
    Queue& operator=(const Queue&) = delete; // No assignment

Or old-school:

private:
    // Never define these so you will get a linker error if someone tries to use them
    Queue(const Queue&);            // No copy
    Queue& operator=(const Queue&); // No assignment

(rule of 3/rule of 5 is something you may way to look into at some point).

BTW Thomas' suggestion of "Exceptional C++" is indeed good along with the followup. The recommendations in it are relevant even (or especially) if you're using a compiler from the 90ies. The GOTW article I linked (that Thomas also references) forms the basis for one of the chapters in the book.

[jotd]

Originally Posted by deimos

Not trying to talk down to me? How would you interpret "you cannot just dump your code and expect people to debug it" in any other way?

not trying to talk down to you. Really.


At stackoverflow, a lot of people misunderstand how the platform work and dump their code without trying to create a minimal example.


On EAB, among fellow amigans, there is no such rule, and people CAN debug your code dump without complaining, it happens all the time with asm tricky issues and such. But as said somewhere else you'd be better off somewhere where people know C++, not amiga.


I see there are already good suggestions. I'm off now.