doc/containers.texi

   1 @node Container data types
   2 @section Container data types
   3
   4 @c Copyright (C) 2019--2020 Free Software Foundation, Inc.
   5
   6 @c Permission is granted to copy, distribute and/or modify this document
   7 @c under the terms of the GNU Free Documentation License, Version 1.3 or
   8 @c any later version published by the Free Software Foundation; with no
   9 @c Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.  A
  10 @c copy of the license is at <https://www.gnu.org/licenses/fdl-1.3.en.html>.
  11
  12 @c Written by Bruno Haible.
  13
  14 @c This macro expands to \log in TeX mode, but just 'log' in HTML and info
  15 @c modes.
  16 @ifnottex
  17 @macro log
  18 log
  19 @end macro
  20 @end ifnottex
  21
  22 @c This macro expands to \mathopsup in TeX mode, to a superscript in HTML
  23 @c mode, and to ^ without braces in info mode.
  24 @ifhtml
  25 @macro mathopsup {EXP}
  26 @sup{\EXP\}
  27 @end macro
  28 @end ifhtml
  29 @ifinfo
  30 @macro mathopsup {EXP}
  31 ^\EXP\
  32 @end macro
  33 @end ifinfo
  34
  35 Gnulib provides several generic container data types.  They can be used
  36 to organize collections of application-defined objects.
  37
  38 @multitable @columnfractions .15 .5 .1 .1 .15
  39 @headitem Data type
  40 @tab Details
  41 @tab Module
  42 @tab Main include file
  43 @tab Include file for operations with out-of-memory checking
  44 @item Sequential list
  45 @tab Can contain any number of objects in any given order.
  46      Duplicates are allowed, but can optionally be forbidden.
  47 @tab @code{list}
  48 @tab @code{"gl_list.h"}
  49 @tab @code{"gl_xlist.h"}
  50 @item Set
  51 @tab Can contain any number of objects; the order does not matter.
  52      Duplicates (in the sense of the comparator) are forbidden.
  53 @tab @code{set}
  54 @tab @code{"gl_set.h"}
  55 @tab @code{"gl_xset.h"}
  56 @item Ordered set
  57 @tab Can contain any number of objects in the order of a given comparator
  58      function.
  59      Duplicates (in the sense of the comparator) are forbidden.
  60 @tab @code{oset}
  61 @tab @code{"gl_oset.h"}
  62 @tab @code{"gl_xoset.h"}
  63 @item Map
  64 @tab Can contain any number of (key, value) pairs, where keys and values
  65      are objects;
  66      there are no (key, value1) and (key, value2) pairs with the same key
  67      (in the sense of a given comparator function).
  68 @tab @code{map}
  69 @tab @code{"gl_map.h"}
  70 @tab @code{"gl_xmap.h"}
  71 @item Ordered map
  72 @tab Can contain any number of (key, value) pairs, where keys and values
  73      are objects;
  74      the (key, value) pairs are ordered by the key, in the order of a given
  75      comparator function;
  76      there are no (key, value1) and (key, value2) pairs with the same key
  77      (in the sense of the comparator function).
  78 @tab @code{omap}
  79 @tab @code{"gl_omap.h"}
  80 @tab @code{"gl_xomap.h"}
  81 @end multitable
  82
  83 Operations without out-of-memory checking (suitable for use in libraries) are
  84 declared in the ``main include file''.  Whereas operations with out-of-memory
  85 checking (suitable only in programs) are declared in the ``include file for
  86 operations with out-of-memory checking''.
  87
  88 For each of the data types, several implementations are available, with
  89 different performance profiles with respect to the available operations.
  90 This enables you to start with the simplest implementation (ARRAY) initially,
  91 and switch to a more suitable implementation after profiling your application.
  92 The implementation of each container instance is specified in a single place
  93 only: in the invocation of the function @code{gl_*_create_empty} that creates
  94 the instance.
  95
  96 The implementations and the guaranteed average performance for the operations
  97 for the ``sequential list'' data type are:
  98
  99 @multitable @columnfractions 0.2 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
 100 @headitem Operation
 101 @tab ARRAY
 102 @tab CARRAY
 103 @tab LINKED
 104 @tab TREE
 105 @tab LINKEDHASH with duplicates
 106 @tab LINKEDHASH without duplicates
 107 @tab TREEHASH with duplicates
 108 @tab TREEHASH without duplicates
 109 @item @code{gl_list_size}
 110 @tab @math{O(1)}
 111 @tab @math{O(1)}
 112 @tab @math{O(1)}
 113 @tab @math{O(1)}
 114 @tab @math{O(1)}
 115 @tab @math{O(1)}
 116 @tab @math{O(1)}
 117 @tab @math{O(1)}
 118 @item @code{gl_list_node_value}
 119 @tab @math{O(1)}
 120 @tab @math{O(1)}
 121 @tab @math{O(1)}
 122 @tab @math{O(1)}
 123 @tab @math{O(1)}
 124 @tab @math{O(1)}
 125 @tab @math{O(1)}
 126 @tab @math{O(1)}
 127 @item @code{gl_list_node_set_value}
 128 @tab @math{O(1)}
 129 @tab @math{O(1)}
 130 @tab @math{O(1)}
 131 @tab @math{O(1)}
 132 @tab @math{O(1)}
 133 @tab @math{O(1)}
 134 @tab @math{O((@log n)@mathopsup{2})}
 135 @tab @math{O(1)}
 136 @item @code{gl_list_next_node}
 137 @tab @math{O(1)}
 138 @tab @math{O(1)}
 139 @tab @math{O(1)}
 140 @tab @math{O(@log n)}
 141 @tab @math{O(1)}
 142 @tab @math{O(1)}
 143 @tab @math{O(@log n)}
 144 @tab @math{O(@log n)}
 145 @item @code{gl_list_previous_node}
 146 @tab @math{O(1)}
 147 @tab @math{O(1)}
 148 @tab @math{O(1)}
 149 @tab @math{O(@log n)}
 150 @tab @math{O(1)}
 151 @tab @math{O(1)}
 152 @tab @math{O(@log n)}
 153 @tab @math{O(@log n)}
 154 @item @code{gl_list_get_at}
 155 @tab @math{O(1)}
 156 @tab @math{O(1)}
 157 @tab @math{O(n)}
 158 @tab @math{O(@log n)}
 159 @tab @math{O(n)}
 160 @tab @math{O(n)}
 161 @tab @math{O(@log n)}
 162 @tab @math{O(@log n)}
 163 @item @code{gl_list_get_first}
 164 @tab @math{O(1)}
 165 @tab @math{O(1)}
 166 @tab @math{O(1)}
 167 @tab @math{O(@log n)}
 168 @tab @math{O(1)}
 169 @tab @math{O(1)}
 170 @tab @math{O(@log n)}
 171 @tab @math{O(@log n)}
 172 @item @code{gl_list_get_last}
 173 @tab @math{O(1)}
 174 @tab @math{O(1)}
 175 @tab @math{O(1)}
 176 @tab @math{O(@log n)}
 177 @tab @math{O(1)}
 178 @tab @math{O(1)}
 179 @tab @math{O(@log n)}
 180 @tab @math{O(@log n)}
 181 @item @code{gl_list_set_at}
 182 @tab @math{O(1)}
 183 @tab @math{O(1)}
 184 @tab @math{O(n)}
 185 @tab @math{O(@log n)}
 186 @tab @math{O(n)}
 187 @tab @math{O(n)}
 188 @tab @math{O((@log n)@mathopsup{2})}
 189 @tab @math{O(@log n)}
 190 @item @code{gl_list_set_first}
 191 @tab @math{O(1)}
 192 @tab @math{O(1)}
 193 @tab @math{O(1)}
 194 @tab @math{O(@log n)}
 195 @tab @math{O(n)}
 196 @tab @math{O(1)}
 197 @tab @math{O((@log n)@mathopsup{2})}
 198 @tab @math{O(@log n)}
 199 @item @code{gl_list_set_last}
 200 @tab @math{O(1)}
 201 @tab @math{O(1)}
 202 @tab @math{O(1)}
 203 @tab @math{O(@log n)}
 204 @tab @math{O(n)}
 205 @tab @math{O(1)}
 206 @tab @math{O((@log n)@mathopsup{2})}
 207 @tab @math{O(@log n)}
 208 @item @code{gl_list_search}
 209 @tab @math{O(n)}
 210 @tab @math{O(n)}
 211 @tab @math{O(n)}
 212 @tab @math{O(n)}
 213 @tab @math{O(n)}
 214 @tab @math{O(1)}
 215 @tab @math{O(@log n)}
 216 @tab @math{O(1)}
 217 @item @code{gl_list_search_from}
 218 @tab @math{O(n)}
 219 @tab @math{O(n)}
 220 @tab @math{O(n)}
 221 @tab @math{O(n)}
 222 @tab @math{O(n)}
 223 @tab @math{O(1)}
 224 @tab @math{O((@log n)@mathopsup{2})}
 225 @tab @math{O(@log n)}
 226 @item @code{gl_list_search_from_to}
 227 @tab @math{O(n)}
 228 @tab @math{O(n)}
 229 @tab @math{O(n)}
 230 @tab @math{O(n)}
 231 @tab @math{O(n)}
 232 @tab @math{O(1)}
 233 @tab @math{O((@log n)@mathopsup{2})}
 234 @tab @math{O(@log n)}
 235 @item @code{gl_list_indexof}
 236 @tab @math{O(n)}
 237 @tab @math{O(n)}
 238 @tab @math{O(n)}
 239 @tab @math{O(n)}
 240 @tab @math{O(n)}
 241 @tab @math{O(n)}
 242 @tab @math{O(@log n)}
 243 @tab @math{O(@log n)}
 244 @item @code{gl_list_indexof_from}
 245 @tab @math{O(n)}
 246 @tab @math{O(n)}
 247 @tab @math{O(n)}
 248 @tab @math{O(n)}
 249 @tab @math{O(n)}
 250 @tab @math{O(n)}
 251 @tab @math{O((@log n)@mathopsup{2})}
 252 @tab @math{O(@log n)}
 253 @item @code{gl_list_indexof_from_to}
 254 @tab @math{O(n)}
 255 @tab @math{O(n)}
 256 @tab @math{O(n)}
 257 @tab @math{O(n)}
 258 @tab @math{O(n)}
 259 @tab @math{O(n)}
 260 @tab @math{O((@log n)@mathopsup{2})}
 261 @tab @math{O(@log n)}
 262 @item @code{gl_list_add_first}
 263 @tab @math{O(n)}
 264 @tab @math{O(1)}
 265 @tab @math{O(1)}
 266 @tab @math{O(@log n)}
 267 @tab @math{O(1)}
 268 @tab @math{O(1)}
 269 @tab @math{O((@log n)@mathopsup{2})}
 270 @tab @math{O(@log n)}
 271 @item @code{gl_list_add_last}
 272 @tab @math{O(1)}
 273 @tab @math{O(1)}
 274 @tab @math{O(1)}
 275 @tab @math{O(@log n)}
 276 @tab @math{O(1)}
 277 @tab @math{O(1)}
 278 @tab @math{O((@log n)@mathopsup{2})}
 279 @tab @math{O(@log n)}
 280 @item @code{gl_list_add_before}
 281 @tab @math{O(n)}
 282 @tab @math{O(n)}
 283 @tab @math{O(1)}
 284 @tab @math{O(@log n)}
 285 @tab @math{O(1)}
 286 @tab @math{O(1)}
 287 @tab @math{O((@log n)@mathopsup{2})}
 288 @tab @math{O(@log n)}
 289 @item @code{gl_list_add_after}
 290 @tab @math{O(n)}
 291 @tab @math{O(n)}
 292 @tab @math{O(1)}
 293 @tab @math{O(@log n)}
 294 @tab @math{O(1)}
 295 @tab @math{O(1)}
 296 @tab @math{O((@log n)@mathopsup{2})}
 297 @tab @math{O(@log n)}
 298 @item @code{gl_list_add_at}
 299 @tab @math{O(n)}
 300 @tab @math{O(n)}
 301 @tab @math{O(n)}
 302 @tab @math{O(@log n)}
 303 @tab @math{O(n)}
 304 @tab @math{O(n)}
 305 @tab @math{O((@log n)@mathopsup{2})}
 306 @tab @math{O(@log n)}
 307 @item @code{gl_list_remove_node}
 308 @tab @math{O(n)}
 309 @tab @math{O(n)}
 310 @tab @math{O(1)}
 311 @tab @math{O(@log n)}
 312 @tab @math{O(n)}
 313 @tab @math{O(1)}
 314 @tab @math{O((@log n)@mathopsup{2})}
 315 @tab @math{O(@log n)}
 316 @item @code{gl_list_remove_at}
 317 @tab @math{O(n)}
 318 @tab @math{O(n)}
 319 @tab @math{O(n)}
 320 @tab @math{O(@log n)}
 321 @tab @math{O(n)}
 322 @tab @math{O(n)}
 323 @tab @math{O((@log n)@mathopsup{2})}
 324 @tab @math{O(@log n)}
 325 @item @code{gl_list_remove_first}
 326 @tab @math{O(n)}
 327 @tab @math{O(1)}
 328 @tab @math{O(1)}
 329 @tab @math{O(@log n)}
 330 @tab @math{O(n)}
 331 @tab @math{O(1)}
 332 @tab @math{O((@log n)@mathopsup{2})}
 333 @tab @math{O(@log n)}
 334 @item @code{gl_list_remove_last}
 335 @tab @math{O(1)}
 336 @tab @math{O(1)}
 337 @tab @math{O(1)}
 338 @tab @math{O(@log n)}
 339 @tab @math{O(n)}
 340 @tab @math{O(1)}
 341 @tab @math{O((@log n)@mathopsup{2})}
 342 @tab @math{O(@log n)}
 343 @item @code{gl_list_remove}
 344 @tab @math{O(n)}
 345 @tab @math{O(n)}
 346 @tab @math{O(n)}
 347 @tab @math{O(n)}
 348 @tab @math{O(n)}
 349 @tab @math{O(1)}
 350 @tab @math{O((@log n)@mathopsup{2})}
 351 @tab @math{O(@log n)}
 352 @item @code{gl_list_iterator}
 353 @tab @math{O(1)}
 354 @tab @math{O(1)}
 355 @tab @math{O(1)}
 356 @tab @math{O(@log n)}
 357 @tab @math{O(1)}
 358 @tab @math{O(1)}
 359 @tab @math{O(@log n)}
 360 @tab @math{O(@log n)}
 361 @item @code{gl_list_iterator_from_to}
 362 @tab @math{O(1)}
 363 @tab @math{O(1)}
 364 @tab @math{O(n)}
 365 @tab @math{O(@log n)}
 366 @tab @math{O(n)}
 367 @tab @math{O(n)}
 368 @tab @math{O(@log n)}
 369 @tab @math{O(@log n)}
 370 @item @code{gl_list_iterator_next}
 371 @tab @math{O(1)}
 372 @tab @math{O(1)}
 373 @tab @math{O(1)}
 374 @tab @math{O(@log n)}
 375 @tab @math{O(1)}
 376 @tab @math{O(1)}
 377 @tab @math{O(@log n)}
 378 @tab @math{O(@log n)}
 379 @item @code{gl_sortedlist_search}
 380 @tab @math{O(@log n)}
 381 @tab @math{O(@log n)}
 382 @tab @math{O(n)}
 383 @tab @math{O(@log n)}
 384 @tab @math{O(n)}
 385 @tab @math{O(n)}
 386 @tab @math{O(@log n)}
 387 @tab @math{O(@log n)}
 388 @item @code{gl_sortedlist_search_from}
 389 @tab @math{O(@log n)}
 390 @tab @math{O(@log n)}
 391 @tab @math{O(n)}
 392 @tab @math{O(@log n)}
 393 @tab @math{O(n)}
 394 @tab @math{O(n)}
 395 @tab @math{O(@log n)}
 396 @tab @math{O(@log n)}
 397 @item @code{gl_sortedlist_indexof}
 398 @tab @math{O(@log n)}
 399 @tab @math{O(@log n)}
 400 @tab @math{O(n)}
 401 @tab @math{O(@log n)}
 402 @tab @math{O(n)}
 403 @tab @math{O(n)}
 404 @tab @math{O(@log n)}
 405 @tab @math{O(@log n)}
 406 @item @code{gl_sortedlist_indexof_from}
 407 @tab @math{O(@log n)}
 408 @tab @math{O(@log n)}
 409 @tab @math{O(n)}
 410 @tab @math{O(@log n)}
 411 @tab @math{O(n)}
 412 @tab @math{O(n)}
 413 @tab @math{O(@log n)}
 414 @tab @math{O(@log n)}
 415 @item @code{gl_sortedlist_add}
 416 @tab @math{O(n)}
 417 @tab @math{O(n)}
 418 @tab @math{O(n)}
 419 @tab @math{O(@log n)}
 420 @tab @math{O(n)}
 421 @tab @math{O(n)}
 422 @tab @math{O((@log n)@mathopsup{2})}
 423 @tab @math{O(@log n)}
 424 @item @code{gl_sortedlist_remove}
 425 @tab @math{O(n)}
 426 @tab @math{O(n)}
 427 @tab @math{O(n)}
 428 @tab @math{O(@log n)}
 429 @tab @math{O(n)}
 430 @tab @math{O(n)}
 431 @tab @math{O((@log n)@mathopsup{2})}
 432 @tab @math{O(@log n)}
 433 @end multitable
 434
 435 The implementations and the guaranteed average performance for the operations
 436 for the ``set'' data type are:
 437
 438 @multitable @columnfractions 0.4 0.2 0.4
 439 @headitem Operation
 440 @tab ARRAY
 441 @tab LINKEDHASH, HASH
 442 @item @code{gl_set_size}
 443 @tab @math{O(1)}
 444 @tab @math{O(1)}
 445 @item @code{gl_set_add}
 446 @tab @math{O(n)}
 447 @tab @math{O(1)}
 448 @item @code{gl_set_remove}
 449 @tab @math{O(n)}
 450 @tab @math{O(1)}
 451 @item @code{gl_set_search}
 452 @tab @math{O(n)}
 453 @tab @math{O(1)}
 454 @item @code{gl_set_iterator}
 455 @tab @math{O(1)}
 456 @tab @math{O(1)}
 457 @item @code{gl_set_iterator_next}
 458 @tab @math{O(1)}
 459 @tab @math{O(1)}
 460 @end multitable
 461
 462 The implementations and the guaranteed average performance for the operations
 463 for the ``ordered set'' data type are:
 464
 465 @multitable @columnfractions 0.5 0.25 0.25
 466 @headitem Operation
 467 @tab ARRAY
 468 @tab TREE
 469 @item @code{gl_oset_size}
 470 @tab @math{O(1)}
 471 @tab @math{O(1)}
 472 @item @code{gl_oset_add}
 473 @tab @math{O(n)}
 474 @tab @math{O(@log n)}
 475 @item @code{gl_oset_remove}
 476 @tab @math{O(n)}
 477 @tab @math{O(@log n)}
 478 @item @code{gl_oset_search}
 479 @tab @math{O(@log n)}
 480 @tab @math{O(@log n)}
 481 @item @code{gl_oset_search_atleast}
 482 @tab @math{O(@log n)}
 483 @tab @math{O(@log n)}
 484 @item @code{gl_oset_iterator}
 485 @tab @math{O(1)}
 486 @tab @math{O(@log n)}
 487 @item @code{gl_oset_iterator_next}
 488 @tab @math{O(1)}
 489 @tab @math{O(@log n)}
 490 @end multitable
 491
 492 The implementations and the guaranteed average performance for the operations
 493 for the ``map'' data type are:
 494
 495 @multitable @columnfractions 0.4 0.2 0.4
 496 @headitem Operation
 497 @tab ARRAY
 498 @tab LINKEDHASH, HASH
 499 @item @code{gl_map_size}
 500 @tab @math{O(1)}
 501 @tab @math{O(1)}
 502 @item @code{gl_map_get}
 503 @tab @math{O(n)}
 504 @tab @math{O(1)}
 505 @item @code{gl_map_put}
 506 @tab @math{O(n)}
 507 @tab @math{O(1)}
 508 @item @code{gl_map_remove}
 509 @tab @math{O(n)}
 510 @tab @math{O(1)}
 511 @item @code{gl_map_search}
 512 @tab @math{O(n)}
 513 @tab @math{O(1)}
 514 @item @code{gl_map_iterator}
 515 @tab @math{O(1)}
 516 @tab @math{O(1)}
 517 @item @code{gl_map_iterator_next}
 518 @tab @math{O(1)}
 519 @tab @math{O(1)}
 520 @end multitable
 521
 522 The implementations and the guaranteed average performance for the operations
 523 for the ``ordered map'' data type are:
 524
 525 @multitable @columnfractions 0.5 0.25 0.25
 526 @headitem Operation
 527 @tab ARRAY
 528 @tab TREE
 529 @item @code{gl_omap_size}
 530 @tab @math{O(1)}
 531 @tab @math{O(1)}
 532 @item @code{gl_omap_get}
 533 @tab @math{O(@log n)}
 534 @tab @math{O(@log n)}
 535 @item @code{gl_omap_put}
 536 @tab @math{O(n)}
 537 @tab @math{O(@log n)}
 538 @item @code{gl_omap_remove}
 539 @tab @math{O(n)}
 540 @tab @math{O(@log n)}
 541 @item @code{gl_omap_search}
 542 @tab @math{O(@log n)}
 543 @tab @math{O(@log n)}
 544 @item @code{gl_omap_search_atleast}
 545 @tab @math{O(@log n)}
 546 @tab @math{O(@log n)}
 547 @item @code{gl_omap_iterator}
 548 @tab @math{O(1)}
 549 @tab @math{O(@log n)}
 550 @item @code{gl_omap_iterator_next}
 551 @tab @math{O(1)}
 552 @tab @math{O(@log n)}
 553 @end multitable
 554
 555 For C++, Gnulib provides a C++ template class for each of these container data types.
 556
 557 @multitable @columnfractions .30 .20 .25 .25
 558 @headitem Data type
 559 @tab C++ class
 560 @tab Module
 561 @tab Include file
 562 @item Sequential list
 563 @tab @code{gl_List}
 564 @tab @code{list-c++}
 565 @tab @code{"gl_list.hh"}
 566 @item Set
 567 @tab @code{gl_Set}
 568 @tab @code{set-c++}
 569 @tab @code{"gl_set.hh"}
 570 @item Ordered set
 571 @tab @code{gl_OSet}
 572 @tab @code{oset-c++}
 573 @tab @code{"gl_oset.hh"}
 574 @item Map
 575 @tab @code{gl_Map}
 576 @tab @code{map-c++}
 577 @tab @code{"gl_map.hh"}
 578 @item Ordered map
 579 @tab @code{gl_OMap}
 580 @tab @code{omap-c++}
 581 @tab @code{"gl_omap.hh"}
 582 @end multitable
 583
 584 @ifnottex
 585 @unmacro log
 586 @end ifnottex
 587 @ifhtml
 588 @unmacro mathopsup
 589 @end ifhtml
 590 @ifinfo
 591 @unmacro mathopsup
 592 @end ifinfo