Re: Library proposal - indexed_array

From: Julien Blanc (julien.blanc_at_[hidden])
Date: 2022-06-24 06:38:11

Le vendredi 24 juin 2022 Ã  06:31 +0200, Richard Hodges via Boost a
écrit :
> On Fri, 24 Jun 2022 at 02:01, Hadriel Kaplan <hadrielk_at_[hidden]>
> wrote:
> 
> I understand that presenting the type with the look and feel of a
> container is somehow pleasing. The ability might be an interesting
> academic goal.
> 
> I am more interested in what real-world use-cases this solves.

Maybe i should have started with some history for what has lead me to
the design of indexed_array.

I've been professionnally working for the past 4 years (and still am)
in the Lift industry. We make heavy use of CANOpen, and especially it's
lift oriented variant, CANOpenLift (DS417). A lift has floors (at least
2) and door faces (usually one or two), which we need to handle in
several places to store characteristic like the type of door, access
controls, etc.

Due to the way CANOpenLift is designed, doors start at zero and goes up
to 3 (4 doors max), but floors start as one (zero indicates the cabin).
And there's a special value, 0xFF, which means all floors. As a
manufacturer extension, we have also a few reserved values (in the
higher range) which indicates specific locations, such as machinery. 

What this means in that in our code base, we have a mix of zero-based
arrays and one-based arrays. This has actually led to some errors when
the highest floor was in use (failure to apply the offset will be
transparent if you do it both when reading and writing unless you go
out of bound). Migrating to an indexed_array-like container (the one we
use in our code base is not the one i'm proposing, but an inferior but
C++11 compatible one) has greatly improved readability and actually
fixed a few bugs.

We also have several places where data is indexed by values coming from
the DS417 specification (eg virtual inputs), and they tend to start at
one, but not always (sometimes the zero value is reserved, sometimes
not). The need to support "holes" in the indexing scheme comes from
there, because you have reserved areas for manufacturer specific
extensions.

The floor / door combination is also what incurs the need to provide a
multidimensional indexing. In our code base, we have a BiIndexedArray,
but i find it more elegant to have it as a generalization of
indexed_array.

> 
> Indexed array still has the maintenance burden of having to maintain
> both the enum and the associative "array" separately.

That is true, but that's actually where the safe initialization feature
can help you. By checking at compile time that you handle all cases,
any change in the enum will be a compile-time break. Especially handy
when the enum is generated from some description file (that is the case
in our code base). You can do that with some switch/case if you don't
need a contiguous storage, but if you do then you're out of solution.

Another place where i plan to use indexed_array in our code base is for
state machines (we use them a lot in our code base). The state is
defined by both an enum value (the enum contains the list of all
possible states) and a corresponding class, which does the logic. A
pointer to each state is stored in an array (a map is not usable as we
are target mcus with around 256k ram, so any dynamic memory management
is forbidden). This array is initialized at startup, and we have to
make sure the initialization (which is usually in the source file)
follows the order of the enum, which is usually defined in the header
file. This as well actually led to some bugs (not production bugs,
they're seen in the development phase), a compile time check here is a
nice addition.

> 
> 
> Perhaps there is a case when seeking to parse a number of flags that
> are presented as text and each flag may not appear more than once?
> 
> enum class NerfEnum : char {
> Â  wounded = 'W',
> Â  buffed = 'B';
> Â  burning = 'N';
> };
> BOOST_DESCRIBE_ENUM(NerfEnum, (wounded, buffed, burning));
> 
> JSON input:
> {
> ...
> Â Â  "nerfs": [wounded, buffed, burning]
> ...
> }
> 
> indexed_array might then be used to efficiently store the set of
> flags associated with this unfortunate character.
> But in this case, am I not better off with an unsigned int, where
> each flag is represented by a bit?
> 
> The "natural code" might be:
> 
> unsigned flags = 0;
> for(auto&& value : nerfsjson.as_array())
> Â  flags |= to_bit(*deserialise<NerfEnum>(value.as_string());
> 
> I could imagine that being able to express this bitset with a
> container-like interface might make my code more intuitive, but I
> don't think that indexed_array addresses this case.
> (I appreciate that such a container would have some of the same
> criticisms of vector<bool>)

This is indeed not the use cases that drove me to design the container.
I don't intend to provide any vector<bool>-like optimization, i don't
think they make a lot of sense (i'm not a big fan of vector<bool>, i
use bitset which i find a lot more convenient).

There surely is some academicity in the design of indexed_array. Its
inspiration came from real world needs, but i have tried to make it
extensible so that it can address more than just my actual needs.
Describe integration was made both because it really simplifies the
usage, and it was a nice stress-test of the design. The same goes for
multidimensional: it was actually a nice way of checking if the design
was general enough.

Last but not least, i'll just add that Ada (yes, Ada!) has had the
following feature for nearly 40 years:

    type Index is range 1 .. 5;
    arr: array (Index) of int;

This kind of thing is especially liked by embedded developers. I'm not
aware of any C++ library that provides the same functionality.
indexed_array does:

    indexed_array<int, interval<1, 5>> arr;

Sure, you may not have a need for this. I guess it depends a lot on the
domain you are working in. Most of the time, an std::map will provide
the abstraction you need, and the additional cost won't be an issue.
But if you don't have any dynamic memory management, then obviously it
can't. indexed_array has been designed with this in mind (that is a
strong requirement in my daily job).

I hope this long reply explains better the motivations behind the
design.

Best regards,

Julien