|
From: | Bruno Haible |
Subject: | generic container for ordered maps |
Date: | Mon, 10 Dec 2018 02:10:36 +0100 |
User-agent: | KMail/5.1.3 (Linux/4.4.0-138-generic; KDE/5.18.0; x86_64; ; ) |
Hi, Gnulib should have generic containers of types - list - ordered set - set - ordered map - map The first three are already implemented. Here comes the implementation for ordered maps. An "ordered map" is a set of key -> value mappings which is sorted according to the keys. It is not frequently needed, but when you need it, it's better to have a direct implementation than to have to emulate it (by combining an ordered set with a list). The operations are: Operation ARRAY TREE gl_omap_size O(1) O(1) gl_omap_get O(log n) O(log n) gl_omap_put O(n) O(log n) gl_omap_remove O(n) O(log n) gl_omap_search O(log n) O(log n) gl_omap_search_atleast O(log n) O(log n) gl_omap_iterator O(1) O(log n) gl_omap_iterator_next O(1) O(log n) Review and comments welcome! Bruno
0001-omap-New-module.patch
Description: Text Data
0002-array-omap-New-module.patch
Description: Text Data
0003-avltree-omap-New-module.patch
Description: Text Data
0004-rbtree-omap-New-module.patch
Description: Text Data
0005-xomap-New-module.patch
Description: Text Data
0006-array-omap-Add-tests.patch
Description: Text Data
0007-avltree-omap-Add-tests.patch
Description: Text Data
0008-rbtree-omap-Add-tests.patch
Description: Text Data
[Prev in Thread] | Current Thread | [Next in Thread] |