]> git.saurik.com Git - wxWidgets.git/blob - docs/latex/wx/array.tex
Minor tweek for WXPM
[wxWidgets.git] / docs / latex / wx / array.tex
1 \section{\class{wxArray}}\label{wxarray}
2
3 This section describes the so called {\it dynamic arrays}. This is a C
4 array-like data structure i.e. the member access time is constant (and not
5 linear according to the number of container elements as for linked lists). However, these
6 arrays are dynamic in the sense that they will automatically allocate more
7 memory if there is not enough of it for adding a new element. They also perform
8 range checking on the index values but in debug mode only, so please be sure to
9 compile your application in debug mode to use it (see \helpref{debugging overview}{debuggingoverview} for
10 details). So, unlike the arrays in some other
11 languages, attempt to access an element beyond the arrays bound doesn't
12 automatically expand the array but provokes an assertion failure instead in
13 debug build and does nothing (except possibly crashing your program) in the
14 release build.
15
16 The array classes were designed to be reasonably efficient, both in terms of
17 run-time speed and memory consumption and the executable size. The speed of
18 array item access is, of course, constant (independent of the number of elements)
19 making them much more efficient than linked lists (\helpref{wxList}{wxlist}).
20 Adding items to the arrays is also implemented in more or less constant time -
21 but the price is preallocating the memory in advance. In the \helpref{memory management}{wxarraymemorymanagement} section
22 you may find some useful hints about optimizing wxArray memory usage. As for executable size, all
23 wxArray functions are inline, so they do not take {\it any space at all}.
24
25 wxWindows has three different kinds of array. All of them derive from
26 wxBaseArray class which works with untyped data and can not be used directly.
27 The standard macros WX\_DEFINE\_ARRAY(), WX\_DEFINE\_SORTED\_ARRAY() and
28 WX\_DEFINE\_OBJARRAY() are used to define a new class deriving from it. The
29 classes declared will be called in this documentation wxArray, wxSortedArray and
30 wxObjArray but you should keep in mind that no classes with such names actually
31 exist, each time you use one of WX\_DEFINE\_XXXARRAY macro you define a class
32 with a new name. In fact, these names are "template" names and each usage of one
33 of the macros mentioned above creates a template specialization for the given
34 element type.
35
36 wxArray is suitable for storing integer types and pointers which it does not
37 treat as objects in any way, i.e. the element pointed to by the pointer is not
38 deleted when the element is removed from the array. It should be noted that
39 all of wxArray's functions are inline, so it costs strictly nothing to define as
40 many array types as you want (either in terms of the executable size or the
41 speed) as long as at least one of them is defined and this is always the case
42 because wxArrays are used by wxWindows internally. This class has one serious
43 limitation: it can only be used for storing integral types (bool, char, short,
44 int, long and their unsigned variants) or pointers (of any kind). An attempt
45 to use with objects of sizeof() greater than sizeof(long) will provoke a
46 runtime assertion failure, however declaring a wxArray of floats will not (on
47 the machines where sizeof(float) <= sizeof(long)), yet it will {\bf not} work,
48 please use wxObjArray for storing floats and doubles (NB: a more efficient
49 wxArrayDouble class is scheduled for the next release of wxWindows).
50
51 wxSortedArray is a wxArray variant which should be used when searching in the
52 array is a frequently used operation. It requires you to define an additional
53 function for comparing two elements of the array element type and always stores
54 its items in the sorted order (according to this function). Thus, it's
55 \helpref{Index()}{wxarrayindex} function execution time is $O(log(N))$ instead of
56 $O(N)$ for the usual arrays but the \helpref{Add()}{wxarrayadd} method is
57 slower: it is $O(log(N))$ instead of constant time (neglecting time spent in
58 memory allocation routine). However, in a usual situation elements are added to
59 an array much less often than searched inside it, so wxSortedArray may lead to
60 huge performance improvements compared to wxArray. Finally, it should be
61 noticed that, as wxArray, wxSortedArray can be only used for storing integral
62 types or pointers.
63
64 wxObjArray class treats its elements like "objects". It may delete them when
65 they are removed from the array (invoking the correct destructor) and copies
66 them using the objects copy constructor. In order to implement this behaviour
67 the definition of the wxObjArray arrays is split in two parts: first, you should
68 declare the new wxObjArray class using WX\_DECLARE\_OBJARRAY() macro and then
69 you must include the file defining the implementation of template type:
70 <wx/arrimpl.cpp> and define the array class with WX\_DEFINE\_OBJARRAY() macro
71 from a point where the full (as opposed to `forward') declaration of the array
72 elements class is in scope. As it probably sounds very complicated here is an
73 example:
74
75 \begin{verbatim}
76 #include <wx/dynarray.h>
77
78 // we must forward declare the array because it's used inside the class
79 // declaration
80 class MyDirectory;
81 class MyFile;
82
83 // this defines two new types: ArrayOfDirectories and ArrayOfFiles which can be
84 // now used as shown below
85 WX_DECLARE_OBJARRAY(MyDirectory, ArrayOfDirectories);
86 WX_DECLARE_OBJARRAY(MyFile, ArrayOfFiles);
87
88 class MyDirectory
89 {
90 ...
91 ArrayOfDirectories m_subdirectories; // all subdirectories
92 ArrayOfFiles m_files; // all files in this directory
93 };
94
95 ...
96
97 // now that we have MyDirectory declaration in scope we may finish the
98 // definition of ArrayOfDirectories -- note that this expands into some C++
99 // code and so should only be compiled once (i.e., don't put this in the
100 // header, but into a source file or you will get linkin errors)
101 #include <wx/arrimpl.cpp> // this is a magic incantation which must be done!
102 WX_DEFINE_OBJARRAY(ArrayOfDirectories);
103
104 // that's all!
105 \end{verbatim}
106
107 It is not as elegant as writing
108
109 \begin{verbatim}
110 typedef std::vector<MyDirectory> ArrayOfDirectories;
111 \end{verbatim}
112
113 but is not that complicated and allows the code to be compiled with any, however
114 dumb, C++ compiler in the world.
115
116 Things are much simpler for wxArray and wxSortedArray however: it is enough
117 just to write
118
119 \begin{verbatim}
120 WX_DEFINE_ARRAY(MyDirectory *, ArrayOfDirectories);
121 WX_DEFINE_SORTED_ARRAY(MyFile *, ArrayOfFiles);
122 \end{verbatim}
123
124 \wxheading{See also:}
125
126 \helpref{Container classes overview}{wxcontaineroverview}, \helpref{wxList}{wxlist}
127
128 \wxheading{Required headers:}
129
130 <wx/dynarray.h> for wxArray and wxSortedArray and additionally <wx/arrimpl.cpp>
131 for wxObjArray.
132
133 \latexignore{\rtfignore{\wxheading{Function groups}}}
134
135 \membersection{Macros for template array definition}
136
137 To use an array you must first define the array class. This is done with the
138 help of the macros in this section. The class of array elements must be (at
139 least) forward declared for WX\_DEFINE\_ARRAY, WX\_DEFINE\_SORTED\_ARRAY and
140 WX\_DECLARE\_OBJARRAY macros and must be fully declared before you use
141 WX\_DEFINE\_OBJARRAY macro.
142
143 \helpref{WX\_DEFINE\_ARRAY}{wxdefinearray}\\
144 \helpref{WX\_DEFINE\_SORTED\_ARRAY}{wxdefinesortedarray}\\
145 \helpref{WX\_DECLARE\_OBJARRAY}{wxdeclareobjarray}\\
146 \helpref{WX\_DEFINE\_OBJARRAY}{wxdefineobjarray}
147
148 \membersection{Constructors and destructors}
149
150 Array classes are 100\% C++ objects and as such they have the appropriate copy
151 constructors and assignment operators. Copying wxArray just copies the elements
152 but copying wxObjArray copies the arrays items. However, for memory-efficiency
153 sake, neither of these classes has virtual destructor. It is not very important
154 for wxArray which has trivial destructor anyhow, but it does mean that you
155 should avoid deleting wxObjArray through a wxBaseArray pointer (as you would
156 never use wxBaseArray anyhow it shouldn't be a problem) and that you should not
157 derive your own classes from the array classes.
158
159 \helpref{wxArray default constructor}{wxarrayctordef}\\
160 \helpref{wxArray copy constructors and assignment operators}{wxarrayctorcopy}\\
161 \helpref{\destruct{wxArray}}{wxarraydtor}
162
163 \membersection{Memory management}\label{wxarraymemorymanagement}
164
165 Automatic array memory management is quite trivial: the array starts by
166 preallocating some minimal amount of memory (defined by
167 WX\_ARRAY\_DEFAULT\_INITIAL\_SIZE) and when further new items exhaust already
168 allocated memory it reallocates it adding 50\% of the currently allocated
169 amount, but no more than some maximal number which is defined by
170 ARRAY\_MAXSIZE\_INCREMENT constant. Of course, this may lead to some memory
171 being wasted (ARRAY\_MAXSIZE\_INCREMENT in the worst case, i.e. 4Kb in the
172 current implementation), so the \helpref{Shrink()}{wxarrayshrink} function is
173 provided to unallocate the extra memory. The \helpref{Alloc()}{wxarrayalloc}
174 function can also be quite useful if you know in advance how many items you are
175 going to put in the array and will prevent the array code from reallocating the
176 memory more times than needed.
177
178 \helpref{Alloc}{wxarrayalloc}\\
179 \helpref{Shrink}{wxarrayshrink}
180
181 \membersection{Number of elements and simple item access}
182
183 Functions in this section return the total number of array elements and allow to
184 retrieve them - possibly using just the C array indexing $[]$ operator which
185 does exactly the same as \helpref{Item()}{wxarrayitem} method.
186
187 \helpref{Count}{wxarraycount}\\
188 \helpref{GetCount}{wxarraygetcount}\\
189 \helpref{IsEmpty}{wxarrayisempty}\\
190 \helpref{Item}{wxarrayitem}\\
191 \helpref{Last}{wxarraylast}
192
193 \membersection{Adding items}
194
195 \helpref{Add}{wxarrayadd}\\
196 \helpref{Insert}{wxarrayinsert}
197
198 \membersection{Removing items}
199
200 \helpref{WX\_CLEAR\_ARRAY}{wxcleararray}\\
201 \helpref{Empty}{wxarrayempty}\\
202 \helpref{Clear}{wxarrayclear}\\
203 \helpref{Remove}{wxarrayremove}
204
205 \membersection{Searching and sorting}
206
207 \helpref{Index}{wxarrayindex}\\
208 \helpref{Sort}{wxarraysort}
209
210 %%%%% MEMBERS HERE %%%%%
211 \helponly{\insertatlevel{2}{
212
213 \wxheading{Members}
214
215 }}
216
217 \membersection{WX\_DEFINE\_ARRAY}\label{wxdefinearray}
218
219 \func{}{WX\_DEFINE\_ARRAY}{\param{}{T}, \param{}{name}}
220
221 This macro defines a new array class named {\it name} and containing the
222 elements of type {\it T}. Example:
223
224 \begin{verbatim}
225 WX_DEFINE_ARRAY(int, wxArrayInt);
226
227 class MyClass;
228 WX_DEFINE_ARRAY(MyClass *, wxArrayOfMyClass);
229 \end{verbatim}
230
231 Note that wxWindows predefines the following standard array classes: wxArrayInt,
232 wxArrayLong and wxArrayPtrVoid.
233
234 \membersection{WX\_DEFINE\_SORTED\_ARRAY}\label{wxdefinesortedarray}
235
236 \func{}{WX\_DEFINE\_SORTED\_ARRAY}{\param{}{T}, \param{}{name}}
237
238 This macro defines a new sorted array class named {\it name} and containing
239 the elements of type {\it T}. Example:
240
241 \begin{verbatim}
242 WX_DEFINE_SORTED_ARRAY(int, wxSortedArrayInt);
243
244 class MyClass;
245 WX_DEFINE_SORTED_ARRAY(MyClass *, wxArrayOfMyClass);
246 \end{verbatim}
247
248 You will have to initialize the objects of this class by passing a comparaison
249 function to the array object constructor like this:
250 \begin{verbatim}
251 int CompareInts(int n1, int n2)
252 {
253 return n1 - n2;
254 }
255
256 wxSortedArrayInt sorted(CompareInts);
257
258 int CompareMyClassObjects(MyClass *item1, MyClass *item2)
259 {
260 // sort the items by their address...
261 return Stricmp(item1->GetAddress(), item2->GetAddress());
262 }
263
264 wxArrayOfMyClass another(CompareMyClassObjects);
265 \end{verbatim}
266
267 \membersection{WX\_DECLARE\_OBJARRAY}\label{wxdeclareobjarray}
268
269 \func{}{WX\_DECLARE\_OBJARRAY}{\param{}{T}, \param{}{name}}
270
271 This macro declares a new object array class named {\it name} and containing
272 the elements of type {\it T}. Example:
273
274 \begin{verbatim}
275 class MyClass;
276 WX_DEFINE_OBJARRAY(MyClass, wxArrayOfMyClass); // note: not "MyClass *"!
277 \end{verbatim}
278
279 You must use \helpref{WX\_DEFINE\_OBJARRAY()}{wxdefineobjarray} macro to define
280 the array class - otherwise you would get link errors.
281
282 \membersection{WX\_DEFINE\_OBJARRAY}\label{wxdefineobjarray}
283
284 \func{}{WX\_DEFINE\_OBJARRAY}{\param{}{name}}
285
286 This macro defines the methods of the array class {\it name} not defined by the
287 \helpref{WX\_DECLARE\_OBJARRAY()}{wxdeclareobjarray} macro. You must include the
288 file <wx/arrimpl.cpp> before using this macro and you must have the full
289 declaration of the class of array elements in scope! If you forget to do the
290 first, the error will be caught by the compiler, but, unfortunately, many
291 compilers will not give any warnings if you forget to do the second - but the
292 objects of the class will not be copied correctly and their real destructor will
293 not be called.
294
295 Example of usage:
296
297 \begin{verbatim}
298 // first declare the class!
299 class MyClass
300 {
301 public:
302 MyClass(const MyClass&);
303
304 ...
305
306 virtual ~MyClass();
307 };
308
309 #include <wx/arrimpl.cpp>
310 WX_DEFINE_OBJARRAY(wxArrayOfMyClass);
311 \end{verbatim}
312
313 \membersection{WX\_CLEAR\_ARRAY}\label{wxcleararray}
314
315 \func{void}{WX\_CLEAR\_ARRAY}{\param{wxArray\& }{array}}
316
317 This macro may be used to delete all elements of the array before emptying it.
318 It can not be used with wxObjArrays - but they will delete their elements anyhow
319 when you call Empty().
320
321 \membersection{Default constructors}\label{wxarrayctordef}
322
323 \func{}{wxArray}{\void}
324
325 \func{}{wxObjArray}{\void}
326
327 Default constructor initializes an empty array object.
328
329 \func{}{wxSortedArray}{\param{int (*)(T first, T second)}{compareFunction}}
330
331 There is no default constructor for wxSortedArray classes - you must initialize it
332 with a function to use for item comparaison. It is a function which is passed
333 two arguments of type {\it T} where {\it T} is the array element type and which
334 should return a negative, zero or positive value according to whether the first
335 element passed to it is less than, equal to or greater than the second one.
336
337 \membersection{wxArray copy constructor and assignment operator}\label{wxarrayctorcopy}
338
339 \func{}{wxArray}{\param{const wxArray\& }{array}}
340
341 \func{}{wxSortedArray}{\param{const wxSortedArray\& }{array}}
342
343 \func{}{wxObjArray}{\param{const wxObjArray\& }{array}}
344
345 \func{wxArray\&}{operator$=$}{\param{const wxArray\& }{array}}
346
347 \func{wxSortedArray\&}{operator$=$}{\param{const wxSortedArray\& }{array}}
348
349 \func{wxObjArray\&}{operator$=$}{\param{const wxObjArray\& }{array}}
350
351 The copy constructors and assignment operators perform a shallow array copy
352 (i.e. they don't copy the objects pointed to even if the source array contains
353 the items of pointer type) for wxArray and wxSortedArray and a deep copy (i.e.
354 the array element are copied too) for wxObjArray.
355
356 \membersection{wxArray::\destruct{wxArray}}\label{wxarraydtor}
357
358 \func{}{\destruct{wxArray}}{\void}
359
360 \func{}{\destruct{wxSortedArray}}{\void}
361
362 \func{}{\destruct{wxObjArray}}{\void}
363
364 The wxObjArray destructor deletes all the items owned by the array. This is not
365 done by wxArray and wxSortedArray versions - you may use
366 \helpref{WX\_CLEAR\_ARRAY}{wxcleararray} macro for this.
367
368 \membersection{wxArray::Add}\label{wxarrayadd}
369
370 \func{void}{Add}{\param{T }{item}}
371
372 \func{void}{Add}{\param{T *}{item}}
373
374 \func{void}{Add}{\param{T \&}{item}}
375
376 Appends a new element to the array (where {\it T} is the type of the array
377 elements.)
378
379 The first version is used with wxArray and wxSortedArray. The second and the
380 third are used with wxObjArray. There is an important difference between
381 them: if you give a pointer to the array, it will take ownership of it, i.e.
382 will delete it when the item is deleted from the array. If you give a reference
383 to the array, however, the array will make a copy of the item and will not take
384 ownership of the original item. Once again, it only makes sense for wxObjArrays
385 because the other array types never take ownership of their elements.
386
387 \membersection{wxArray::Alloc}\label{wxarrayalloc}
388
389 \func{void}{Alloc}{\param{size\_t }{count}}
390
391 Preallocates memory for a given number of array elements. It is worth calling
392 when the number of items which are going to be added to the array is known in
393 advance because it will save unneeded memory reallocation. If the array already
394 has enough memory for the given number of items, nothing happens.
395
396 \membersection{wxArray::Clear}\label{wxarrayclear}
397
398 \func{void}{Clear}{\void}
399
400 This function does the same as \helpref{Empty()}{wxarrayempty} and additionally
401 frees the memory allocated to the array.
402
403 \membersection{wxArray::Count}\label{wxarraycount}
404
405 \constfunc{size\_t}{Count}{\void}
406
407 Same as \helpref{GetCount()}{wxarraygetcount}. This function is deprecated -
408 it exists only for compatibility.
409
410 \membersection{wxObjArray::Detach}\label{wxobjarraydetach}
411
412 \func{T *}{Detach}{\param{size\_t }{index}}
413
414 Removes the element from the array, but, unlike,
415
416 \helpref{Remove()}{wxarrayremove} doesn't delete it. The function returns the
417 pointer to the removed element.
418
419 \membersection{wxArray::Empty}\label{wxarrayempty}
420
421 \func{void}{Empty}{\void}
422
423 Empties the array. For wxObjArray classes, this destroys all of the array
424 elements. For wxArray and wxSortedArray this does nothing except marking the
425 array of being empty - this function does not free the allocated memory, use
426 \helpref{Clear()}{wxarrayclear} for this.
427
428 \membersection{wxArray::GetCount}\label{wxarraygetcount}
429
430 \constfunc{size\_t}{GetCount}{\void}
431
432 Return the number of items in the array.
433
434 \membersection{wxArray::Index}\label{wxarrayindex}
435
436 \func{int}{Index}{\param{T\& }{item}, \param{bool }{searchFromEnd = FALSE}}
437
438 \func{int}{Index}{\param{T\& }{item}}
439
440 The first version of the function is for wxArray and wxObjArray, the second is
441 for wxSortedArray only.
442
443 Searches the element in the array, starting from either beginning or the end
444 depending on the value of {\it searchFromEnd} parameter. wxNOT\_FOUND is
445 returned if the element is not found, otherwise the index of the element is
446 returned.
447
448 Linear search is used for the wxArray and wxObjArray classes but binary search
449 in the sorted array is used for wxSortedArray (this is why searchFromEnd
450 parameter doesn't make sense for it).
451
452 \membersection{wxArray::Insert}\label{wxarrayinsert}
453
454 \func{void}{Insert}{\param{T }{item}, \param{size\_t }{n}}
455
456 \func{void}{Insert}{\param{T *}{item}, \param{size\_t }{n}}
457
458 \func{void}{Insert}{\param{T \&}{item}, \param{size\_t }{n}}
459
460 Insert a new item into the array before the item {\it n} - thus, {\it Insert(something, 0u)} will
461 insert an item in such way that it will become the
462 first array element.
463
464 Please see \helpref{Add()}{wxarrayadd} for explanation of the differences
465 between the overloaded versions of this function.
466
467 \membersection{wxArray::IsEmpty}\label{wxarrayisempty}
468
469 \constfunc{bool}{IsEmpty}{\void}
470
471 Returns TRUE if the array is empty, FALSE otherwise.
472
473 \membersection{wxArray::Item}\label{wxarrayitem}
474
475 \constfunc{T\&}{Item}{\param{size\_t }{index}}
476
477 Returns the item at the given position in the array. If {\it index} is out of
478 bounds, an assert failure is raised in the debug builds but nothing special is
479 done in the release build.
480
481 The returned value is of type "reference to the array element type" for all of
482 the array classes.
483
484 \membersection{wxArray::Last}\label{wxarraylast}
485
486 \constfunc{T\&}{Last}{\void}
487
488 Returns the last element in the array, i.e. is the same as Item(GetCount() - 1).
489 An assert failure is raised in the debug mode if the array is empty.
490
491 The returned value is of type "reference to the array element type" for all of
492 the array classes.
493
494 \membersection{wxArray::Remove}\label{wxarrayremove}
495
496 \func{\void}{Remove}{\param{size\_t }{index}}
497
498 \func{\void}{Remove}{\param{T }{item}}
499
500 Removes the element from the array either by index or by value. When an element
501 is removed from wxObjArray it is deleted by the array - use
502 \helpref{Detach()}{wxobjarraydetach} if you don't want this to happen. On the
503 other hand, when an object is removed from a wxArray nothing happens - you
504 should delete the it manually if required:
505
506 \begin{verbatim}
507 T *item = array[n];
508 delete item;
509 array.Remove(n)
510 \end{verbatim}
511
512 See also \helpref{WX\_CLEAR\_ARRAY}{wxcleararray} macro which deletes all
513 elements of a wxArray (supposed to contain pointers).
514
515 \membersection{wxArray::Shrink}\label{wxarrayshrink}
516
517 \func{void}{Shrink}{\void}
518
519 Frees all memory unused by the array. If the program knows that no new items
520 will be added to the array it may call Shrink() to reduce its memory usage.
521 However, if a new item is added to the array, some extra memory will be
522 allocated again.
523
524 \membersection{wxArray::Sort}\label{wxarraysort}
525
526 \func{void}{Sort}{\param{CMPFUNC<T> }{compareFunction}}
527
528 The notation CMPFUNC<T> should be read as if we had the following declaration:
529
530 \begin{verbatim}
531 template int CMPFUNC(T *first, T *second);
532 \end{verbatim}
533
534 where {\it T} is the type of the array elements. I.e. it is a function returning
535 {\it int} which is passed two arguments of type {\it T *}.
536
537 Sorts the array using the specified compare function: this function should
538 return a negative, zero or positive value according to whether the first element
539 passed to it is less than, equal to or greater than the second one.
540
541 wxSortedArray doesn't have this function because it is always sorted.
542