Nested containers with different sizes

[ivan-aksamentov]

I would like nested containers to have different sizes (all known at compile time). Is this possible?

For example, consider this map of sets:

// This dimension is variable           V
using Set = frozen::set<frozen::string, 3>;

constexpr frozen::map<frozen::string, Set, 4> table = {
  {"one", {"A"}},
  {"two", {"B", "C"}},
  {"three", {"D", "E", "F"}},
  {"-", {}},
};

And it's usage:

const auto& two = table.find("two");
// two is {"B", "C"}

const auto& three = table.find("three");
// three is {"D", "E", "F"}

As you see, sets inside the map have different length.

This currently won't compile:

error: no matching constructor for initialization of 'const frozen::map<frozen::string, Set, 4>' (aka 'const map<basic_string<char>, set<basic_string<char>, 3>, 4>')
constexpr frozen::map<frozen::string, Set, 4> table = {
                                              ^       ~
note: candidate constructor not viable: requires 2 arguments, but 4 were provided
  constexpr map(container_type items, Compare const &compare)
            ^
note: candidate constructor not viable: requires 2 arguments, but 4 were provided
  constexpr map(std::initializer_list<value_type> items, Compare const &compare)
            ^
note: candidate constructor not viable: requires single argument 'items', but 4 arguments were provided
  explicit constexpr map(container_type items)
                     ^
note: candidate constructor not viable: requires single argument 'items', but 4 arguments were provided
  constexpr map(std::initializer_list<value_type> items)
            ^
note: candidate constructor (the implicit copy constructor) not viable: requires 1 argument, but 4 were provided
class map {
      ^
note: candidate constructor (the implicit move constructor) not viable: requires 1 argument, but 4 were provided

I thought, if sets really need to be of the same size, then maybe we could fill them with some dummy values, for example "?":

constexpr frozen::map<frozen::string, Set, 4> table = {
  {"one", {"A", "?", "?"}},
  {"two", {"B", "C", "?"}},
  {"three", {"D", "E", "F"}},
  {"-", {"?", "?", "?"}},
};

I can handle these dummy values in userspace and make sure I never search for the "?" in these sets, but from inside the library it can probably be handled more efficiently?

Application: reverse translation in biology. I need a lookup table to find a set of possible triplets (value of the map) for a given aminoacid (key of the map). The sets are at most 6 elements. This table is fundamental to biology and never changes, so runtime initialization would be certainly wasteful.

Sets can also be arrays, I guess. They are very small anyway.

Any other ideas on how this can be implemented without runtime initialization and associated static initialization order fiasco etc.?

[peter-moran]

I think the problem you are having is that the size of the container is a template parameter, which makes it part of the type information. The map has to use the same type for all values however.

So you either need a different container that does not have the size data in its type or I think you’ll need to do something like your dummy data idea.

[peter-moran]

Or, like you said, this library could allow you to have a map of size n but allow you to provide less than n keys in the constructor.

[ivan-aksamentov]

@peter-moran Thanks Peter,

Yes, this is how I understand it.

Interestingly, we can have a frozen::string of an arbitrary length as a map value, but, let's say, not an array of arbitrary length (or a set for that matter). Even though a string is basically an array.

This looks like a (historical) limitation of C++ type system and/or of the established constructor function signatures in the standard library (which frozen is mimicking). I am wondering if this can be workaround.

It might be a fun exercise to try to use for map values a frozen::string<T> as if it was an array, and which element type is not a character, but an arbitrary type (also string in my case):

frozen::string<frozen::string> string_of_strings = 
	{"ABC", "DEF", "GHI"};

Alternatively, could the map store an unsized base type, while accepting a sized derived type during initialization, which would be then converted to base?

namespace frozen {
  template <typename Key, size_t Size>
  class set<Key, Size>: public unsized_set<Key> {};
}

frozen::map<frozen::string, frozen::unsized_set<frozen::string>, 2> = {
  {"one", frozen::set<frozen::string, 1>{"A"}},
  {"two", frozen::set<frozen::string, 2>{"B", "C"}},
};

[0x8000-0000]

Consider this:

#include <frozen/string.h>
#include <frozen/unordered_map.h>

#include <fmt/format.h>

#include <array>
#include <span>
#include <string>

static constexpr auto setOne   = std::to_array({'A'});
static constexpr auto setTwo   = std::to_array({'B', 'C'});
static constexpr auto setThree = std::to_array({'D', 'E', 'F'});

static constexpr std::pair<frozen::string, std::span<const char>> tableData[] = {
   {"one", setOne},
   {"two", setTwo},
   {"three", setThree},
};

static constexpr auto lookupTable = frozen::make_unordered_map(tableData);

int main(int /* argc */, char* argv[])
{
   const auto iter = lookupTable.find(frozen::string{argv[1]});
   if (iter != lookupTable.end())
   {
      fmt::print("{} has {} elements, first is {}\n", argv[1], iter->second.size(), iter->second[0]);
   }

   return 0;
}

Note: your spans are so small, that linear search inside is faster than anything else.

[muggenhor]

FYI: this looks like a more generic problem of a part that I'm trying to address with my feat/zero-reloc-string-containers branch (for which #158 is preparation).

I.e. I'm dealing with strings of different lengths which are essentially "containers" (arrays) of different sizes with a specific value_type that have zero as the last element.

I'm storing two things there to store a two-level array of arrays {T[N_0], ..., T[N_m]}:

1. Flatten it into a single "storage" array: T storage[sum(N...)]
2. Keep a separate "index" array of {starting_index, size (N_i)}.

When sorting only the elements in the "index" array are swapped. Iterators are proxy iterators that, when dereferenced, return a non-reference frozen::string/std::string_view. I.e. the string_view is constructed on-demand, so also cannot be modified in the container.

In principal the same is possible to generalize away from strings by making the zero-termination optional and providing a conversion to span<T> (or span<const T>) instead.

Your example however isn't just storing plain arrays but nesting frozen data structures inside others. While probably possible, that would definitely require some more invasive changes than my implementation for the simple CharT[varying N] case does.