const and O(N^2), non-const, or mutable?

[Malcolm McLean]

I've got a JSON parser.
The JSON is turned into a linked list. Then there's a nice C++ interface built on top. Arrays can be accessed via an overloaded [] operator.

Now Most of the time, callers are likely to iterate through an array from the
first index to the last. Currently this is O(N^2), because the parser starts
from the first array position and walks until it finds the right index. It
could be made O(1) by storing the last access. But that means that
array access is no longer const. This sounds like a prime candidate
for "mutable". However I don't really like the idea of "mutable" on
principle.

So what would you opt for?

[Juha Nieminen]

Is the data being stored in a linked list non-negotiable?

If it were stored in an array (or even a std::deque) it would solve the
problem nicely (and make it efficient regardless of how the calling code
wants to access the contents).

If the data being in a linked list is non-negotiable, then the second best
option would be to create an array with pointers to each list element, and
then you index this array, rather than traverse the list. (Although if the
calling code can add and remove elements from the list, you need to be
careful about that.)

[Bo Persson]

How about an iterator interface instead of operator[] ? The iterator
knows its current position and can be incremented cheaply.

[Malcolm McLean]

On Monday, 16 May 2022 at 12:58:15 UTC+1, Juha Nieminen wrote:
> Malcolm McLean <malcolm.ar...@gmail.com> wrote:
> > I've got a JSON parser.
> > The JSON is turned into a linked list. Then there's a nice C++ interface built on top. Arrays can be accessed via an overloaded [] operator.
> >
> > Now Most of the time, callers are likely to iterate through an array from the
> > first index to the last. Currently this is O(N^2), because the parser starts
> > from the first array position and walks until it finds the right index. It
> > could be made O(1) by storing the last access. But that means that
> > array access is no longer const. This sounds like a prime candidate
> > for "mutable". However I don't really like the idea of "mutable" on
> > principle.
> >
> > So what would you opt for?
> Is the data being stored in a linked list non-negotiable?
>

It would entail a complete refactor of code which works and does its job in
shipped applications.

>
> If it were stored in an array (or even a std::deque) it would solve the
> problem nicely (and make it efficient regardless of how the calling code
> wants to access the contents).
>
> If the data being in a linked list is non-negotiable, then the second best
> option would be to create an array with pointers to each list element, and
> then you index this array, rather than traverse the list. (Although if the
> calling code can add and remove elements from the list, you need to be
> careful about that.)
>

The calling code cannot alter the array. It's a parser, not an object.
(In fact it's quite easy to generate JSON from C++ structures, the hard part
is going in the reverse direction).
An array of pointers is quite a good idea, and would allow random access.
However, as I said, I expect random access to be rare. The design pattern
is that data is saved and loaded as a JSON string at comparatively rare
intervals, then converted to C++ for processing. So mostly people will
iterate throuhg the array, pushing the contents to a vector.

[Juha Nieminen]

Malcolm McLean <malcolm.ar...@gmail.com> wrote:
> An array of pointers is quite a good idea, and would allow random access.
> However, as I said, I expect random access to be rare. The design pattern
> is that data is saved and loaded as a JSON string at comparatively rare
> intervals, then converted to C++ for processing. So mostly people will
> iterate throuhg the array, pushing the contents to a vector.

Does the user need to access the elements via indexing? Would a forward
iterator be enough? (Or a two-way iterator if it's a doubly-linked list.)

At a minimum provide an iterator so the user can efficiently traverse
the list. (With the proper begin() and end() functions they can even
use a range-based for.)

[Malcolm McLean]

The whole point of the C++ parser is that it's nice to use. It sits on top
of a C JSON parser written by someone else.

It's nicer to access an array via indexing than via an iterator. Also, JSON
allows mixed type arrays, which causes problems when trying to create
STL-like iterators. In reality mixed-type arrays will be rare, but you can't overload
C++ by return type.

However the usual use pattern will be to pass through the array once, extracting
the data and pushing to an STL vector. So iterators would work.

[Juha Nieminen]

Malcolm McLean <malcolm.ar...@gmail.com> wrote:
> It's nicer to access an array via indexing than via an iterator.

Not if indexing is a linear-time operation.
(There's a reason std::list and std::set don't provide indexing.
(std::map kind of does, but it's not really the same thing.))

> Also, JSON
> allows mixed type arrays, which causes problems when trying to create
> STL-like iterators. In reality mixed-type arrays will be rare, but you can't overload
> C++ by return type.

How does indexed access solve that problem any better?