1{include resources/ug-header.md} 2{set-property title "CL-Containers User's Guide"} 3{set-property style-sheet user-guide} 4{set-property docs-package cl-containers} 5 6# CL-Containers User's Guide 7 8# Table of Contents 9 10{table-of-contents :start 2 :depth 3} 11 12## Introduction 13 14Common Lisp ships with a set of powerful built in data 15structures including the venerable list, full featured 16arrays, and hash-tables. The Common Lisp Container Library 17{clcl} enhances and builds on these structures in 18two ways: 19 20 1. By adding containers that are not available in native 21 Lisp (for example: binary search trees, red-black trees, 22 sparse arrays and so on). 23 24 2. By standardizing the container interface so that they 25 are simpler to use and so that changing design decisions 26 becomes significantly easier. 27 28The containers in {clcl} can be divided into three storage 29types: Ordered, Unordered and Associative. 30 31 * Ordered containers store things in (some) order. The order 32 may be based on how items were inserted into the container 33 or it may depend on an explicit sorting. 34 35 * Unordered containers also store things and share much of 36 Ordered containers interface. However, the items in an 37 Unordered container do not maintain any particular 38 arrangement. 39 40 * Associative containers store items *associated* 41 with some index or key. The key may be simple (for 42 example, a one-dimensional array indexed by an integer) or 43 complex (for example, a nested hash table indexed by 44 color, size and object class). 45 46The way containers store their contents provides another view 47in {clcl}'s design: containers may store their contents 48directly (think of a list) or they may wrap each element 49within some data-structure -- a node -- that helps the 50container keep track of what is going on (think of a binary 51tree). We'll see many examples of both styles below. 52 53There are many other mixins that combine to produce generic 54container behavior. For example, a 55[bounded-container-mixin][] starts at some fixed size and 56cannot grow beyond it whereas a [keyed-container-mixin][] 57provide a `key` function that is used by other container 58functions (e.g., [sort-container][]) to modify their 59behavior. 60 61## Terminology 62 63*Containers* store *elements*. Sometimes the elements are 64wrapped in *nodes*. We can *insert*, *delete*, *search-for*, 65*find*, *iterate*, and *collect* both elements and nodes from 66a container. We can also look at the *size* of a container, 67see it is *empty* (with [emptyp][]) and *empty* it (with 68[empty!][]). Ordered containers also let us find the *first*, 69*last* and *nth* element (or node) and they may let us *sort* 70or *reverse* the contents as a whole. Associative containers 71provide the ability to look at *keys* and elements (or, 72sometimes, *values*). We can collect and iterate either one 73of these or both simultaneously. Finally, certain specialized 74container classes provide synonyms for their usual 75operations. For example, you can still pop and push into a 76[stack-container][]. 77 78## Using a container 79 80### Creating and inspecting 81 82{include user-guide/creation-and-inspection.mmd} 83 84### General use: adding, deleting, finding 85 86{include user-guide/editing.mmd} 87 88### Some and Every 89 90{include user-guide/querying.mmd} 91 92### Counting, Collecting, and Canvasing 93 94{include user-guide/iteration-and-collection.mmd} 95 96### Finding and Searching 97 98{include user-guide/searching.mmd} 99 100### Miscellaneous 101 102{docs reduce-elements} 103{docs reduce-nodes} 104{docs dimensions} 105 106### Container taxonomy 107 108{include user-guide/taxonomy.mmd} 109 110### Iterators 111 112{include user-guide/iteration.mmd} 113 114## Indices 115 116### Index of Functions 117 118{docs-index (function macro) function} 119 120### Index of variables 121 122{docs-index variable} 123 124### Full symbol index 125 126{docs-index :all} 127 128<hr> 129 130#### Glossary 131 132{glossary} 133 134 135#### Footnotes 136 137{footnotes} 138 139{include resources/ug-footer.md} 140