Re^6: [OT:] Is this Curriculum right?

[Marshall]

I guess that I don't really understand what is meant by a C++ vector. A Perl hash table calculates a "vector" to a short linked list. Perl has an algorithm such that, in general, when these "short linked lists" become too long, Perl doubles the hash size and creates more "vectors". The lists associated with one vector, will become distributed amongst other vectors as more vectors become available. As long as each "vector" just points to a short linked list, this is just fine. You don't need one to one vector to object. You need vector to a few objects.

BTW, if you are writing in Perl, just use the Perl array and use splice to insert or delete if you need to. I personally cannot remember writing Perl code that does that explicitly does that in the past decade. Mileage varies. There is no need for a specific linked list implementation in Perl.

[eyepopslikeamosquito]

... just use the Perl array and use splice to insert or delete if you need to ... there is no need for a specific linked list implementation in Perl

Agreed. I too find Perl's arrays a delight to use. :)

I guess that I don't really understand what is meant by a C++ vector

A C++ vector is similar to a Perl array. Like C arrays, C++ vectors use contiguous storage locations for their elements (great for CPU cache performance), while their size can change dynamically, with storage handled automatically by the container (great for protection from dreaded C memory faults).

A Perl hash table calculates a "vector" to a short linked list. Perl has an algorithm such that, in general, when these "short linked lists" become too long, Perl doubles the hash size and creates more "vectors".

I have not studied how Perl implements its hash tables; I hope to find more time to study them in the future. The standard C++ library equivalent of a Perl hash are the UnorderedAssociativeContainers, especially std::map and std::unordered_map.

Though the C++ standard library is an interface and does not specify implementation (thus allowing library implementations to adapt to new hardware in the future), I believe that std::map is usually implemented using red-black trees, while std::unordered_map (closest to Perl's hashes) is usually implemented, apparently due to a small "oversight" in the specification, by "storing a linked list to external nodes in the array of buckets".

There are a wide variety of associative containers in the C++ standard library, all sharing a similar interface. For example, in High Performance Game of Life:

• I ended up using std::unordered_set with a customized hasher for cell_lookup_type ... after benchmarking different containers (which was very easy due to their consistent interface).
• For cell_list_type, I used std::vector<Cell>.

[ikegami]

I have not studied how Perl implements its hash tables;

Hashes are hash tables. Collisions are handled using linked lists. Perl keeps the number of entries in the linked list small through array-size doublings and hash perturbation. It has optimizations to reuse keys.

[LanX]

> I have not studied how Perl implements its hash tables; I hope to find more time to study them in the future.

see https://st.aticpan.org/source/RURBAN/illguts-0.49/index.html#hv

the collisions for a bucket are stored in a linked list.

> Agreed. I too find Perl's arrays a delight to use. :)

Perl arrays use a doubling trick to ensure that push and unshift are near O(1) like with linked lists.

They allocate more memory than needed, and start and end are given by pointers° inside that area. In the rare cases it's exhausted, twice as much memory is dynamically allocated and the data transferred.

So its space for time and the cost for re-allocation is reduced to a constant on average.

And splice'ing should still be far more expensive than with linked lists.

°) kind of a sliding window

[ikegami]

Perl arrays use a doubling trick to ensure that push and unshift are near O(1) like with linked lists.

Unshifts are O(1).

Unshifts and pushes are amortized O(1) (meaning O(N) to do N of them).