On Wed, Jan 3, 2024 at 3:27 PM organicoman <organicoman_at_[hidden]> wrote:
>
> This data structure has two strong properties:
> 1- guaranteed uniqueness of its elements.
> 2- preservation of insertion order of its elements.

I know what it does. I don't know why you would want that.

> The combination of these properties will allow simplification of a lot of algorithm.
> Expl:
> While creating a dependency graph. You want to memoize the elements of the current branch you are traversing, and at the same time catch cyclic dependency. Very useful.

Is it though? Is it really?

Remember: a stack is a specific data structure that you can only
insert into and remove from the front of. There are no other
operations you can use to act on that stack. If you're trying to
create a dependency graph, the end goal of that is to have... a graph.
A data structure that you're almost certainly going to want to *random
access* at some point.

Whatever it is, it is not a stack.

It seems to me that you would want to explicitly have 2 data
structures: a random-access sequence container of some sort that is
the permanent graph, and a temporary set of some kind that you use to
verify the validity of the graph. The latter will be thrown away after
parsing the data because it is no longer relevant.

> ‐---------
> hashed_stack | depends on
> [main] | fileB , fileC, fileD
> [fileB] | file1 , file2, file3
> [file1] | file# , file@, fileB <-- cyclic dep
>
> Instead of maintaining two data structures, a hash and stack, you have both in the same container.

But... it *is* two data structures. It's still implemented as two data
structures, even if you don't expose that fact. Why does this need to
be part of the standard library?

> And you can adopt this implementation to other ordered containers, like a queue:.
> std::hashed_queue