generic container for sets

[Bruno Haible]

Hi,

In gnulib, so far, we have generic containers for the abstract concepts of
  - list,
  - ordered set.
This proposed series of patches adds a container for
  - set.

The difference between "ordered set" and "set" is that for ordered set,
there is a comparison function that introduces a total order [1], whereas
for set, we only have a comparison for equality.

While the operations for ordered set are:

   Operation                  ARRAY     TREE

   gl_oset_size                O(1)     O(1)
   gl_oset_add                 O(n)   O(log n)
   gl_oset_remove              O(n)   O(log n)
   gl_oset_search            O(log n) O(log n)
   gl_oset_search_atleast    O(log n) O(log n)
   gl_oset_iterator            O(1)   O(log n)
   gl_oset_iterator_next       O(1)   O(log n)

the ones for a set are:

   Operation                  ARRAY   LINKEDHASH
                              LINKED  HASH

   gl_set_size                 O(1)   O(1)
   gl_set_add                  O(n)   O(1)
   gl_set_remove               O(n)   O(1)
   gl_set_search               O(n)   O(1)
   gl_set_iterator             O(1)   O(1)
   gl_set_iterator_next        O(1)   O(1)

Given that the ARRAY and LINKED (= linked-list) implementations of "set"
have the same asymptotic average performance, and LINKED eats more memory
and does more memory allocations than ARRAY, I left out the LINKED
implementation.

This patch series is a preparation for the "map" concept, which I claimed
to be desirable [2].

Review and comments welcome!

Bruno

[1] https://en.wikipedia.org/wiki/Total_order
[2] https://lists.gnu.org/archive/html/bug-gnulib/2018-12/msg00012.html

0001-set-New-module.patch
Description: Text Data

0002-array-set-New-module.patch
Description: Text Data

0003-linkedhash-set-New-module.patch
Description: Text Data

0004-hash-set-New-module.patch
Description: Text Data

0005-xset-New-module.patch
Description: Text Data

0006-array-set-Add-tests.patch
Description: Text Data

0007-linkedhash-set-Add-tests.patch
Description: Text Data

0008-hash-set-Add-tests.patch
Description: Text Data