1 \section{\class{wxArray
}}\label{wxarray
}
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 in 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
10 overview
}{debuggingoverview
} for 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
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 if, of course, constant (independent of 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
22 \helpref{memory management
}{wxarraymemorymanagement
} section you may find some
23 useful hints about optimizing wxArray memory usage. As for executable size, all
24 wxArray functions are inline, so they do not take
{\it any space at all
}.
26 wxWindows has three different kinds of array. All of them derive from
27 wxBaseArray class which works with untyped data and can not be used directly.
28 The standard macros WX
\_DEFINE\_ARRAY(), WX
\_DEFINE\_SORTED\_ARRAY() and
29 WX
\_DEFINE\_OBJARRAY() are used to define a new class deriving from it. The
30 classes declared will be called in this documentation wxArray, wxSortedArray and
31 wxObjArray but you should keep in mind that no classes with such names actually
32 exist, each time you use one of WX
\_DEFINE\_XXXARRAY macro you define a class
33 with a new name. In fact, these names are "template" names and each usage of one
34 of the macros mentioned above creates a template specialization for the given
37 wxArray is suitable for storing integer types and pointers which it does not
38 treat as objects in any way, i.e. the element pointed to by the pointer is not
39 deleted when the element is removed from the array \&c. It should be noted that
40 all of wxArray functions are inline, so it costs strictly nothing to define as
41 many array types as you want (either in terms of the executable size or the
42 speed) as long as at least one of them is defined and this is always the case
43 because wxArrays are used by wxWindows internally.
45 wxSortedArray is a wxArray variant which should be used when searching in the
46 array is a frequently used operation. It requires you to define an additional
47 function for comparing two elements of the array element type and always stores
48 its items in the sorted order (according to this function). Thus, it's
49 \helpref{Index()
}{wxarrayindex
} function execution time is $O(log(N))$ instead of
50 $O(N)$ for the usual arrays but the
\helpref{Add()
}{wxarrayadd
} method is
51 slower: it is $O(log(N))$ instead of constant time (neglecting time spent in
52 memory allocation routine). However, in a usual situation elements are added to
53 an array much less often than searched inside it, so wxSortedArray may lead to
54 huge performance improvements compared to wxArray. As wxArray this array can not
57 wxObjArray class treats its elements like "objects". It may delete them when
58 they are removed from the array (invoking the correct destructor) and copies
59 them using the objects copy constructor. In order to implement this behaviour
60 the definition of the wxObjArray arrays is split in two parts: first, you should
61 declare the new wxObjArray class using WX
\_DECLARE\_OBJARRAY() macro and then
62 you must include the file defining the implementation of template type:
63 <wx/arrimpl.cpp> and define the array class with WX
\_DEFINE\_OBJARRAY() macro
64 from a point where the full (as opposed to `forward') declaration of the array
65 elements class is in scope. As it probably sounds very complicated here is an
69 #include <wx/dynarray.h>
71 // we must forward declare the array because it's used inside the class
76 // this defines two new types: ArrayOfDirectories and ArrayOfFiles which can be
77 // now used as shown below
78 WX_DECLARE_OBJARRAY(MyDirectory, ArrayOfDirectories);
79 WX_DECLARE_OBJARRAY(MyFile, ArrayOfFiles);
84 ArrayOfDirectories m_subdirectories; // all subdirectories
85 ArrayOfFiles m_files; // all files in this directory
90 // now that we have MyDirectory declaration in scope we may finish the
91 // definition of ArrayOfDirectories
92 #include <wx/arrimpl.cpp> // this is a magic incantation which must be done!
93 WX_DEFINE_OBJARRAY(ArrayOfDirectories);
99 It is not as elegant as writing
102 typedef std::vector<MyDirectory> ArrayOfDirectories;
104 but is not that complicated and allows the code to be compiled with any, however
105 dumb, C++ compiler in the world.
107 The things are much simpler for wxArray and wxSortedArray however: it is enough
111 WX_DEFINE_ARRAY(MyDirectory *, ArrayOfDirectories);
112 WX_DEFINE_SORTED_ARRAY(MyFile *, ArrayOfFiles);
115 \wxheading{See also:
}
117 \helpref{Container classes overview
}{wxcontaineroverview
},
\helpref{wxList
}{wxlist
}
119 \wxheading{Required headers:
}
121 <wx/dynarray.h> for wxArray and wxSortedArray and additionally <wx/arrimpl.cpp>
124 \latexignore{\rtfignore{\wxheading{Function groups
}}}
126 \membersection{Macros for template array definition
}
128 To use an array you must first define the array class. This is done with the
129 help of the macros in this section. The class of array elements must be (at
130 least) forward declared for WX
\_DEFINE\_ARRAY, WX
\_DEFINE\_SORTED\_ARRAY and
131 WX
\_DECLARE\_OBJARRAY macros and must be fully declared before you use
132 WX
\_DEFINE\_OBJARRAY macro.
134 \helpref{WX
\_DEFINE\_ARRAY}{wxdefinearray
}\\
135 \helpref{WX
\_DEFINE\_SORTED\_ARRAY}{wxdefinesortedarray
}\\
136 \helpref{WX
\_DECLARE\_OBJARRAY}{wxdeclareobjarray
}\\
137 \helpref{WX
\_DEFINE\_OBJARRAY}{wxdefineobjarray
}
139 \membersection{Constructors and destructors
}
141 Array classes are
100\% C++ objects and as such they have the appropriate copy
142 constructors and assignment operators. Copying wxArray just copies the elements
143 but copying wxObjArray copies the arrays items. However, for memory-efficiency
144 sake, neither of these classes has virtual destructor. It is not very important
145 for wxArray which has trivial destructor anyhow, but it does mean that you
146 should avoid deleting wxObjArray through a wxBaseArray pointer (as you would
147 never use wxBaseArray anyhow it shouldn't be a problem) and that you should not
148 derive your own classes from the array classes.
150 \helpref{wxArray default constructor
}{wxarrayctordef
}
151 \helpref{wxArray copy constructors and assignment operators
}{wxarrayctorcopy
}
152 \helpref{\destruct{wxArray
}}{wxarraydtor
}
154 \membersection{Memory management
}\label{wxarraymemorymanagement
}
156 Automatic array memory management is quite trivial: the array starts by
157 preallocating some minimal amount of memory (defined by
158 WX
\_ARRAY\_DEFAULT\_INITIAL\_SIZE) and when further new items exhaust already
159 allocated memory it reallocates it adding
50\% of the currently allocated
160 amount, but no more than some maximal number which is defined by
161 ARRAY
\_MAXSIZE\_INCREMENT constant. Of course, this may lead to some memory
162 being wasted (ARRAY
\_MAXSIZE\_INCREMENT in the worst case, i.e.
4Kb in the
163 current implementation), so the
\helpref{Shrink()
}{wxarrayshrink
} function is
164 provided to unallocate the extra memory. The
\helpref{Alloc()
}{wxarrayalloc
}
165 function can also be quite useful if you know in advance how many items you are
166 going to put in the array and will prevent the array code from reallocating the
167 memory more times than needed.
169 \helpref{Alloc
}{wxarrayalloc
}\\
170 \helpref{Shrink
}{wxarrayshrink
}
172 \membersection{Number of elements and simple item access
}
174 Functions in this section return the total number of array elements and allow to
175 retrieve them - possibly using just the C array indexing $
[]$ operator which
176 does exactly the same as
\helpref{Item()
}{wxarrayitem
} method.
178 \helpref{Count
}{wxarraycount
}\\
179 \helpref{GetCount
}{wxarraygetcount
}\\
180 \helpref{IsEmpty
}{wxarrayisempty
}\\
181 \helpref{Item
}{wxarrayitem
}\\
182 \helpref{Last
}{wxarraylast
}
184 \membersection{Adding items
}
185 \helpref{Add
}{wxarrayadd
}\\
186 \helpref{Insert
}{wxarrayinsert
}
188 \membersection{Removing items
}
189 \helpref{WX
\_CLEAR\_ARRAY}{wxcleararray
}\\
190 \helpref{Empty
}{wxarrayempty
}\\
191 \helpref{Clear
}{wxarrayclear
}\\
192 \helpref{Remove
}{wxarrayremove
}
194 \membersection{Searching and sorting
}
195 \helpref{Index
}{wxarrayindex
}\\
196 \helpref{Sort
}{wxarraysort
}
198 %%%%% MEMBERS HERE %%%%%
199 \helponly{\insertatlevel{2}{
205 \membersection{WX
\_DEFINE\_ARRAY}\label{wxdefinearray
}
206 \func{}{WX
\_DEFINE\_ARRAY}{\param{}{T
},
\param{name
}}
208 This macro defines a new array class named
{\it name
} and containing the
209 elements of type
{\it T
}. Example:
211 WX_DEFINE_ARRAY(int, wxArrayInt);
214 WX_DEFINE_ARRAY(MyClass *, wxArrayOfMyClass);
217 Note that wxWindows predefines the following standard array classes: wxArrayInt,
218 wxArrayLong and wxArrayPtrVoid.
220 \membersection{WX
\_DEFINE\_SORTED\_ARRAY}\label{wxdefinesortedarray
}
221 \func{}{WX
\_DEFINE\_SORTED\_ARRAY}{\param{}{T
},
\param{name
}}
223 This macro defines a new sorted array class named
{\it name
} and containing
224 the elements of type
{\it T
}. Example:
226 WX_DEFINE_SORTED_ARRAY(int, wxArrayInt);
229 WX_DEFINE_SORTED_ARRAY(MyClass *, wxArrayOfMyClass);
232 You will have to initialize the objects of this class by passing a comparaison
233 function to the array object constructor like this:
235 int CompareInts(int n1, int n2)
240 wxArrayInt sorted(CompareInts);
242 int CompareMyClassObjects(MyClass *item1, MyClass *item2)
244 // sort the items by their address...
245 return Stricmp(item1->GetAddress(), item2->GetAddress());
248 wxArrayOfMyClass another(CompareMyClassObjects);
251 \membersection{WX
\_DECLARE\_OBJARRAY}\label{wxdeclareobjarray
}
252 \func{}{WX
\_DECLARE\_OBJARRAY}{\param{}{T
},
\param{name
}}
254 This macro declares a new object array class named
{\it name
} and containing
255 the elements of type
{\it T
}. Example:
258 WX_DEFINE_OBJARRAY(MyClass, wxArrayOfMyClass); // note: not "MyClass *"!
260 You must use
\helpref{WX
\_DEFINE\_OBJARRAY()
}{wxdefineobjarray
} macro to define
261 the array class - otherwise you would get link errors.
263 \membersection{WX
\_DEFINE\_OBJARRAY}\label{wxdefineobjarray
}
264 \func{}{WX
\_DEFINE\_OBJARRAY}{\param{name
}}
266 This macro defines the methods of the array class
{\it name
} not defined by the
267 \helpref{WX
\_DECLARE\_OBJARRAY()
}{wxdeclareobjarray
} macro. You must include the
268 file <wx/arrimpl.cpp> before using this macro and you must have the full
269 declaration of the class of array elements in scope! If you forget to do the
270 first, the error will be caught by the compiler, but, unfortunately, many
271 compilers will not give any warnings if you forget to do the second - but the
272 objects of the class will not be copied correctly and their real destructor will
277 // first declare the class!
281 MyClass(const MyClass&);
288 #include <wx/arrimpl.cpp>
289 WX_DEFINE_OBJARRAY(wxArrayOfMyClass);
292 \membersection{WX
\_CLEAR\_ARRAY}\label{wxcleararray
}
293 \func{\void}{WX
\_CLEAR\_ARRAY}{\param{wxArray\&
}{array
}}
295 This macro may be used to delete all elements of the array before emptying it.
296 It can not be used with wxObjArrays - but they will delete their elements anyhow
297 when you call Empty().
299 \membersection{Default constructors
}\label{wxarrayctor
}
301 \func{}{wxObjArray
}{}
303 Default constructor initializes an empty array object.
305 \func{}{wxSortedArray
}{\param{int
(*)(T first, T second)}{compareFunction}}
307 There is no default constructor for wxSortedArray classes - you must initialize it
308 with a function to use for item comparaison. It is a function which is passed
309 two arguments of type {\it T} where {\it T} is the array element type and which
310 should return a negative, zero or positive value according to whether the first
311 element passed to it is less than, equal to or greater than the second one.
313 \membersection{wxArray copy constructor and assignemnt operator}\label{wxarrayctorcopy}
314 \func{}{wxArray}{\param{const wxArray\& }{array}}
315 \func{}{wxSortedArray}{\param{const wxSortedArray\& }{array}}
316 \func{}{wxObjArray}{\param{const wxObjArray\& }{array}}
318 \func{wxArray\&}{operator=}{\param{const wxArray\& }{array}}
319 \func{wxSortedArray\&}{operator=}{\param{const wxSortedArray\& }{array}}
320 \func{wxObjArray\&}{operator=}{\param{const wxObjArray\& }{array}}
322 The copy constructors and assignment operators perform a shallow array copy
323 (i.e. they don't copy the objects pointed to even if the source array contains
324 the items of pointer type) for wxArray and wxSortedArray and a deep copy (i.e.
325 the array element are copied too) for wxObjArray.
327 \membersection{wxArray::\destruct{wxArray}}\label{wxarraydtor}
328 \func{}{\destruct{wxArray}}{}
329 \func{}{\destruct{wxSortedArray}}{}
330 \func{}{\destruct{wxObjArray}}{}
332 The wxObjArray destructor deletes all the items owned by the array. This is not
333 done by wxArray and wxSortedArray versions - you may use
334 \helpref{WX\_CLEAR\_ARRAY}{wxcleararray} macro for this.
336 \membersection{wxArray::Add}\label{wxarrayadd}
337 \func{\void}{Add}{\param{T }{item}}
338 \func{\void}{Add}{\param{T *}{item}}
339 \func{\void}{Add}{\param{T \&}{item}}
341 Appends a new element to the array (where {\it T} is the type of the array
344 The first version is used with wxArray and wxSortedArray. The second and the
345 third are used with wxObjArray. There is an {\bf important difference} between
346 them: if you give a pointer to the array, it will take ownership of it, i.e.
347 will delete it when the item is deleted from the array. If you give a reference
348 to the array, however, the array will make a copy of the item and will not take
349 ownership of the original item. Once again, it only makes sense for wxObjArrays
350 because the other array types never take ownership of their elements.
352 \membersection{wxArray::Alloc}\label{wxarrayalloc}
353 \func{\void}{Alloc}{\param{size\_t }{count}}
355 Preallocates memory for a given number of array elements. It is worth calling
356 when the number of items which are going to be added to the array is known in
357 advance because it will save unneeded memory reallocation. If the array already
358 has enough memory for the given number of items, nothing happens.
360 \membersection{wxArray::Clear}\label{wxarrayclear}
361 \func{\void}{Clear}{\void}
363 This function does the same as \helpref{Empty()}{wxarrayempty} and additionally
364 frees the memory allocated to the array.
366 \membersection{wxArray::Count}\label{wxarraycount}
367 \constfunc{size\_t}{Count}{\void}
369 Same as \helpref{GetCount()}{wxarraygetcount}. This function is deprecated -
370 it exists only for compatibility.
372 \membersection{wxObjArray::Detach}\label{wxobjarraydetach}
373 \func{T *}{Detach}{\param{size\_t }{index}}
375 Removes the element from the array, but, unlike,
376 \helpref{Remove()}{wxarrayremove} doesn't delete it. The function returns the
377 pointer to the removed element.
379 \membersection{wxArray::Empty}\label{wxarrayempty}
380 \func{\void}{Empty}{\void}
382 Empties the array. For wxObjArray classes, this destroys all of the array
383 elements. For wxArray and wxSortedArray this does nothing except marking the
384 array of being empty - this function does not free the allocated memory, use
385 \helpref{Clear()}{wxarrayclear} for this.
387 \membersection{wxArray::GetCount}\label{wxarraygetcount}
388 \constfunc{size\_t}{GetCount}{\void}
390 Return the number of items in the array.
392 \membersection{wxArray::Index}\label{wxarrayindex}
393 \func{int}{Index}{\param{T\& }{item}, \param{bool }{searchFromEnd = FALSE}}
394 \func{int}{Index}{\param{T\& }{item}}
396 The first version of the function is for wxArray and wxObjArray, the second is
397 for wxSortedArray only.
399 Searches the element in the array, starting from either beginning or the end
400 depending on the value of {\it searchFromEnd} parameter. wxNOT\_FOUND is
401 returned if the element is not found, otherwise the index of the element is
404 Linear search is used for the wxArray and wxObjArray classes but binary search
405 in the sorted array is used for wxSortedArray (this is why searchFromEnd
406 parameter doesn't make sense for it).
408 \membersection{wxArray::Insert}\label{wxarrayinsert}
409 \func{\void}{Insert}{\param{T }{item}, \param{size\_t }{n}}
410 \func{\void}{Insert}{\param{T *}{item}, \param{size\_t }{n}}
411 \func{\void}{Insert}{\param{T \&}{item}, \param{size\_t }{n}}
413 Insert a new item into the array before the item {\it n} - thus, {\it
414 Insert(something, 0u}} will insert an item in such way that it will become the
417 Please see \helpref{Add()}{wxarrayadd} for explanation of the differences
418 between the overloaded versions of this function.
420 \membersection{wxArray::IsEmpty}\label{wxarrayisempty}
421 \constfunc{bool}{IsEmpty}{}
423 Returns TRUE if the array is empty, FALSE otherwise.
425 \membersection{wxArray::Item}\label{wxarrayitem}
426 \constfunc{T\&}{Item}{\param{size\_t }{index}}
428 Returns the item at the given position in the array. If {\it index} is out of
429 bounds, an assert failure is raised in the debug builds but nothing special is
430 done in the release build.
432 The returned value is of type "reference to the array element type" for all of
435 \membersection{wxArray::Last}\label{wxarraylast}
436 \constfunc{T\&}{Last}{\void}
438 Returns the last element in the array, i.e. is the same as Item(GetCount() - 1).
439 An assert failure is raised in the debug mode if the array is empty.
441 The returned value is of type "reference to the array element type" for all of
444 \membersection{wxArray::Remove}\label{wxarrayremove}
445 \func{\void}{Remove}{\param{size\_t }{index}}
446 \func{\void}{Remove}{\param{T }{item}}
448 Removes the element from the array either by index or by value. When an element
449 is removed from wxObjArray it is deleted by the array - use
450 \helpref{Detach()}{wxobjarraydetach} if you don't want this to happen. On the
451 other hand, when an object is removed from a wxArray nothing happens - you
452 should delete the it manually if required:
459 See also \helpref{WX\_CLEAR\_ARRAY}{wxcleararray} macro which deletes all
460 elements of a wxArray (supposed to contain pointers).
462 \membersection{wxArray::Shrink}\label{wxarrayshrink}
463 \func{\void}{Shrink}{\void}
465 Frees all memory unused by the array. If the program knows that no new items
466 will be added to the array it may call Shrink() to reduce its memory usage.
467 However, if a new item is added to the array, some extra memory will be
470 \membersection{wxArray::Sort}\label{wxarraysort}
471 \func{\void}{Sort}{\param{CMPFUNC<T> }{compareFunction}}
473 The notation CMPFUNC<T> should be read as if we had the following declaration:
475 template int CMPFUNC(T *first, T *second);
477 where {\it T} is the type of the array elements. I.e. it is a function returning
478 {\it int} which is passed two arguments of type {\it T *}.
480 Sorts the array using the specified compare function: this function should
481 return a negative, zero or positive value according to whether the first element
482 passed to it is less than, equal to or greater than the second one.
484 wxSortedArray doesn't have this function because it is always sorted.