|
From: | Bruno Haible |
Subject: | generic container for sets |
Date: | Tue, 04 Dec 2018 01:14:44 +0100 |
User-agent: | KMail/5.1.3 (Linux/4.4.0-138-generic; KDE/5.18.0; x86_64; ; ) |
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
[Prev in Thread] | Current Thread | [Next in Thread] |