C++ class design: dynamic typing alternative to template argument?

Question

I would like to build a space-efficient modular arithmetic class. The idea is that the modulus M is an immutable attribute that gets fixed during instantiation, so if we have a large array (std::vector or another container) of values with the same M, M only needs to be stored once.

If M can be fixed at compile time, this can be done using templates:

template <typename num, num M> class Mod_template
{
    private:
        num V;
    public:
        Mod_template(num v=0)
        {
            if (M == 0)
                V = v;
            else
            {
                V = v % M;
                if (V < 0)
                    V += M;
            }
        }
        // ...
};

Mod_template<int, 5> m1(2); // 2 mod 5

However, in my application, we should be able to express M runtime. What I have looks like this:

template <typename num> class Mod
{
    private:
        const num M;
        num V;
    public:
        Mod(num m, num v=0): M(abs(m))
        {
            if (M == 0)
                V = v;
            else
            {
                V = v % M;
                if (V < 0)
                    V += M;
            }
        }
        // ...
};

Mod<int> m2(5, 2); // 2 mod 5
Mod<int> m3(3);    // 0 mod 3

This works, but a large vector of mod M values uses 2x the space it needs to.

I think the underlying conceptual problem is that Mod's of different moduli are syntactically of the same type even though they "should" be different types. For example, a statement like

m2 = m3;

should raise a runtime error "naturally" (in my version, it does so "manually": check is built into the copy constructor, as well as every binary operator I implement).

So, is there a way to implement some kind of dynamic typing so that the Mod object's type remembers the modulus? I'd really appreciate any idea how to solve this.

This is a recurring problem for me with various mathematical structures (e.g. storing many permutations on the same set, elements of the same group, etc.)

EDIT: as far as I understand,

• templates are types parametrized by a class or literal.

• what I want: a type parametrized by a const object (const num in this case, const Group& or const Group *const for groups, etc.).

Is this possible?

Answer 1

It will be difficult to do it in zero storage space if the class needs to know what M should be without any outside help. Likely the best you can do is store a pointer to a shared M, which may be a little better depending on how large num is. But it's not as good as free.

It will be easier to design if M is a passed-in value to all the functions that need it. Then you can do things like make a pool of objects that all share the same M (there are plenty of easy ways to design this; e.g. map<num, vector<num> >) and only store M once for the pool. The caller will need to know which pool the Mod object came from, but that's probably something it knows anyway.

It's hard to answer this question perfectly in isolation... knowing more about the calling code would definitely help you get better answers.