How do I declare an arbitrary depth of pair of pairs?

Question

A pair of pair of ints can be declared as: std::pair<int, std::pair<int, int> > A; Similarly a pair of pair of pair of ints as std::pair<int, std::pair<int, std::pair<int, int> > >A; I want to declare an arbitrary "pair of pairs" in my code. i.e., Depending on some value (known only at runtime), I want to have either a pair of pair of ints (n = 1) or pair of pair of pair of ints (n = 2) and so on. Was wondering how do I do it efficiently in C++?

Below is a snippet code in Python:

import numpy as np

n = 4 # a value known at runtime
m = 2 # a value known at runtime
def PP(A, j):
    A_s = []
    if j == n-1:
        for i in range(1, m):
            A_s.append((i, A[i]))
    else:
        for i in range(1, m):
            A_c = A[i]
            A_s.append((i, PP(A_c, j+1)))
    return A_s

j = 0
# The dimension of A is known at runtime.
# Will have to create np.ones((m, m, m, m, m)) if n = 5
A = np.ones((m, m, m, m))
B = PP(A, 0)

A pair of pair of ints would have four ints total, but `std::pair >` is only three :) — Jonathan Potter, Oct 29 '20 at 04:40
You can't really decide the type of something at run time. Can you show a tiny example of how you would use this? — cigien, Oct 29 '20 at 04:52
I have updated the question with a python snippet. Sorry for being unclear before. — Andrew Mathews, Oct 29 '20 at 05:17
What is your actual real life problem? What kind of code are you writing? Please provide some [mre] in C++ (not Python) in your question. — Basile Starynkevitch, Oct 29 '20 at 06:21
Just a hint where you don't need to look: Templates. They provide a compile-time mechanism for code generation, they can't process runtime values. — Ulrich Eckhardt, Oct 29 '20 at 07:42

score 2 · Answer 1 · answered Oct 29 '20 at 05:53

Unlike Python, C++ is a statically-typed language. So if the structure or size of what you want to store isn't known until run time, you can't use the type itself, like nested pairs, to describe the specific structure. Instead what you do is use C++ types that can resize dynamically. Namely, std::vector<int> is an idiomatic and efficient way to store a dynamic number of ints in C++.

If you really want a tree-like structure as in your Python example ([(1, [(1, [(1, [(1, 1.0)])])])]), this is possible in C++, too. But it's a bit more work. See for instance Binary Trees in C++: Part 1.

Basile Starynkevitch · Answer 2 · 2020-10-29T06:32:38.747

C++ (see this website and n3337, the C++11 draft standard) has both std::variant and std::optional (in C++17). It seems that you want have some tagged union (like the abstract syntax trees inside C++ compilers) and smart pointers (e.g. std::unique_ptr).

Maybe you want something like

class Foo; // forward declaration
class Foo {
  std::variant<std::unique_ptr<Foo>, std::pair<int,int>> fields;
  /// many other things, in particular for the C++ rule of five
};

In contrast to Python, each C++ value has a known type.

You could combine both cleverly, and you might be interested by other standard containers (in particular std::vector). Please read a good C++ programming book and be aware of the rule of five.

Take inspiration from existing open source software on github or gitlab (such as Qt, RefPerSys, Wt, Fish, Clang static analyzer, GCC, and many others)

Read also the documentation of your C++ compiler (e.g. GCC) and of your debugger (e.g. GDB). If you use a recent GCC, compile with all warnings and debug info, e.g. g++ -Wall -Wextra -g. Document by writing your coding conventions, and for a large enough codebase, consider writing your GCC plugin to enforce them. A recent GCC (so GCC 10 in October 2020) has interesting static analysis options, that you could try.

Consider using the Clang static analyzer (see also this draft report, and the DECODER and CHARIOT European projects, and MILEPOST GCC) on your C++ code base.

Read also papers about C++ in recent ACM SIGPLAN conferences.

You could also define your class Matrix, or use existing libraries providing them (e.g. boost), perhaps adapting this answer to C++.

Remember that the sizeof every C++ type is known at compile time. AFAIK, C++ don't have any flexible array members (like C does).

Enlico · Answer 3 · 2020-10-29T07:40:22.090

As others have already said, you cannot do it. Not at runtime, at least.

However it seems also not useful in general. Let's say you have the following type (like yours, but with a know level of nesting at compile time) and you declare an object of that type

using your_type = std::pair<int, std::pair<int, std::pair<int, int>>>
your_type obj1{1,{2,{3,4}}};

This no different from

std::array<int,4> obj2{1,2,3,4};

where you have this correspondence:

obj1.first == obj2[0]
obj1.second.first == obj2[1]
obj1.second.second.first == obj2[2]
obj1.second.second.second == obj2[3]

And to stress that they are actually the same thing, think about how you would implement a size function for such a type; it could be a metafunction like this (probably there are better ways to do it):

template<typename T, typename Ts>
constexpr int size(std::pair<T,Ts>) {
    if constexpr (std::is_same_v<T,Ts>)
        return 2;
    else
        return 1 + size(Ts{});
}

In other words they are isomorphic.

Now your requirement is to write your_type in such a way that the level of nesting is known at run time. As already said, that's not possible, but guess what is isomorphic to the type you imagine? std::vector<int>!

So my answer is: you don't need that; just use std::vector instead.

As a final comment, based on my answer it seems reasonable that, if you really want a type which behaves like an arbitrarily nested pair, you can just write a wrapper around std::vector. But I don't see why you might really need to do it.

How do I declare an arbitrary depth of pair of pairs?

3 Answers3

In contrast to Python, each C++ value has a known type.