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