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 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
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
\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
}.
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
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 \&c. It should be noted that
39 all of wxArray 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.
44 wxSortedArray is a wxArray variant which should be used when searching in the
45 array is a frequently used operation. It requires you to define an additional
46 function for comparing two elements of the array element type and always stores
47 its items in the sorted order (according to this function). Thus, it's
48 \helpref{Index()
}{wxarrayindex
} function execution time is $O(log(N))$ instead of
49 $O(N)$ for the usual arrays but the
\helpref{Add()
}{wxarrayadd
} method is
50 slower: it is $O(log(N))$ instead of constant time (neglecting time spent in
51 memory allocation routine). However, in a usual situation elements are added to
52 an array much less often than searched inside it, so wxSortedArray may lead to
53 huge performance improvements compared to wxArray. As wxArray this array can not
56 wxObjArray class treats its elements like "objects". It may delete them when
57 they are removed from the array (invoking the correct destructor) and copies
58 them using the objects copy constructor. In order to implement this behaviour
59 the definition of the wxObjArray arrays is split in two parts: first, you should
60 declare the new wxObjArray class using WX
\_DECLARE\_OBJARRAY() macro and then
61 you must include the file defining the implementation of template type:
62 <wx/arrimpl.cpp> and define the array class with WX
\_DEFINE\_OBJARRAY() macro
63 from a point where the full (as opposed to `forward') declaration of the array
64 elements class is in scope. As it probably sounds very complicated here is an
68 #include <wx/dynarray.h>
70 // we must forward declare the array because it's used inside the class
75 // this defines two new types: ArrayOfDirectories and ArrayOfFiles which can be
76 // now used as shown below
77 WX_DECLARE_OBJARRAY(MyDirectory, ArrayOfDirectories);
78 WX_DECLARE_OBJARRAY(MyFile, ArrayOfFiles);
83 ArrayOfDirectories m_subdirectories; // all subdirectories
84 ArrayOfFiles m_files; // all files in this directory
89 // now that we have MyDirectory declaration in scope we may finish the
90 // definition of ArrayOfDirectories
91 #include <wx/arrimpl.cpp> // this is a magic incantation which must be done!
92 WX_DEFINE_OBJARRAY(ArrayOfDirectories);
98 It is not as elegant as writing
101 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
}
186 \helpref{Add
}{wxarrayadd
}\\
187 \helpref{Insert
}{wxarrayinsert
}
189 \membersection{Removing items
}
191 \helpref{WX
\_CLEAR\_ARRAY}{wxcleararray
}\\
192 \helpref{Empty
}{wxarrayempty
}\\
193 \helpref{Clear
}{wxarrayclear
}\\
194 \helpref{Remove
}{wxarrayremove
}
196 \membersection{Searching and sorting
}
198 \helpref{Index
}{wxarrayindex
}\\
199 \helpref{Sort
}{wxarraysort
}
201 %%%%% MEMBERS HERE %%%%%
202 \helponly{\insertatlevel{2}{
208 \membersection{WX
\_DEFINE\_ARRAY}\label{wxdefinearray
}
210 \func{}{WX
\_DEFINE\_ARRAY}{\param{}{T
},
\param{name
}}
212 This macro defines a new array class named
{\it name
} and containing the
213 elements of type
{\it T
}. Example:
216 WX_DEFINE_ARRAY(int, wxArrayInt);
219 WX_DEFINE_ARRAY(MyClass *, wxArrayOfMyClass);
222 Note that wxWindows predefines the following standard array classes: wxArrayInt,
223 wxArrayLong and wxArrayPtrVoid.
225 \membersection{WX
\_DEFINE\_SORTED\_ARRAY}\label{wxdefinesortedarray
}
227 \func{}{WX
\_DEFINE\_SORTED\_ARRAY}{\param{}{T
},
\param{}{name
}}
229 This macro defines a new sorted array class named
{\it name
} and containing
230 the elements of type
{\it T
}. Example:
233 WX_DEFINE_SORTED_ARRAY(int, wxArrayInt);
236 WX_DEFINE_SORTED_ARRAY(MyClass *, wxArrayOfMyClass);
239 You will have to initialize the objects of this class by passing a comparaison
240 function to the array object constructor like this:
242 int CompareInts(int n1, int n2)
247 wxArrayInt sorted(CompareInts);
249 int CompareMyClassObjects(MyClass *item1, MyClass *item2)
251 // sort the items by their address...
252 return Stricmp(item1->GetAddress(), item2->GetAddress());
255 wxArrayOfMyClass another(CompareMyClassObjects);
258 \membersection{WX
\_DECLARE\_OBJARRAY}\label{wxdeclareobjarray
}
260 \func{}{WX
\_DECLARE\_OBJARRAY}{\param{}{T
},
\param{}{name
}}
262 This macro declares a new object array class named
{\it name
} and containing
263 the elements of type
{\it T
}. Example:
266 WX_DEFINE_OBJARRAY(MyClass, wxArrayOfMyClass); // note: not "MyClass *"!
268 You must use
\helpref{WX
\_DEFINE\_OBJARRAY()
}{wxdefineobjarray
} macro to define
269 the array class - otherwise you would get link errors.
271 \membersection{WX
\_DEFINE\_OBJARRAY}\label{wxdefineobjarray
}
273 \func{}{WX
\_DEFINE\_OBJARRAY}{\param{}{name
}}
275 This macro defines the methods of the array class
{\it name
} not defined by the
276 \helpref{WX
\_DECLARE\_OBJARRAY()
}{wxdeclareobjarray
} macro. You must include the
277 file <wx/arrimpl.cpp> before using this macro and you must have the full
278 declaration of the class of array elements in scope! If you forget to do the
279 first, the error will be caught by the compiler, but, unfortunately, many
280 compilers will not give any warnings if you forget to do the second - but the
281 objects of the class will not be copied correctly and their real destructor will
287 // first declare the class!
291 MyClass(const MyClass&);
298 #include <wx/arrimpl.cpp>
299 WX_DEFINE_OBJARRAY(wxArrayOfMyClass);
302 \membersection{WX
\_CLEAR\_ARRAY}\label{wxcleararray
}
304 \func{\void}{WX
\_CLEAR\_ARRAY}{\param{wxArray\&
}{array
}}
306 This macro may be used to delete all elements of the array before emptying it.
307 It can not be used with wxObjArrays - but they will delete their elements anyhow
308 when you call Empty().
310 \membersection{Default constructors
}\label{wxarrayctor
}
314 \func{}{wxObjArray
}{}
316 Default constructor initializes an empty array object.
318 \func{}{wxSortedArray
}{\param{int
(*)(T first, T second)}{compareFunction}}
320 There is no default constructor for wxSortedArray classes - you must initialize it
321 with a function to use for item comparaison. It is a function which is passed
322 two arguments of type {\it T} where {\it T} is the array element type and which
323 should return a negative, zero or positive value according to whether the first
324 element passed to it is less than, equal to or greater than the second one.
326 \membersection{wxArray copy constructor and assignemnt operator}\label{wxarrayctorcopy}
328 \func{}{wxArray}{\param{const wxArray\& }{array}}
330 \func{}{wxSortedArray}{\param{const wxSortedArray\& }{array}}
332 \func{}{wxObjArray}{\param{const wxObjArray\& }{array}}
334 \func{wxArray\&}{operator=}{\param{const wxArray\& }{array}}
336 \func{wxSortedArray\&}{operator=}{\param{const wxSortedArray\& }{array}}
338 \func{wxObjArray\&}{operator=}{\param{const wxObjArray\& }{array}}
340 The copy constructors and assignment operators perform a shallow array copy
341 (i.e. they don't copy the objects pointed to even if the source array contains
342 the items of pointer type) for wxArray and wxSortedArray and a deep copy (i.e.
343 the array element are copied too) for wxObjArray.
345 \membersection{wxArray::\destruct{wxArray}}\label{wxarraydtor}
347 \func{}{\destruct{wxArray}}{}
349 \func{}{\destruct{wxSortedArray}}{}
351 \func{}{\destruct{wxObjArray}}{}
353 The wxObjArray destructor deletes all the items owned by the array. This is not
354 done by wxArray and wxSortedArray versions - you may use
355 \helpref{WX\_CLEAR\_ARRAY}{wxcleararray} macro for this.
357 \membersection{wxArray::Add}\label{wxarrayadd}
359 \func{\void}{Add}{\param{T }{item}}
361 \func{\void}{Add}{\param{T *}{item}}
363 \func{\void}{Add}{\param{T \&}{item}}
365 Appends a new element to the array (where {\it T} is the type of the array
368 The first version is used with wxArray and wxSortedArray. The second and the
369 third are used with wxObjArray. There is an {\bf important difference} between
370 them: if you give a pointer to the array, it will take ownership of it, i.e.
371 will delete it when the item is deleted from the array. If you give a reference
372 to the array, however, the array will make a copy of the item and will not take
373 ownership of the original item. Once again, it only makes sense for wxObjArrays
374 because the other array types never take ownership of their elements.
376 \membersection{wxArray::Alloc}\label{wxarrayalloc}
378 \func{\void}{Alloc}{\param{size\_t }{count}}
380 Preallocates memory for a given number of array elements. It is worth calling
381 when the number of items which are going to be added to the array is known in
382 advance because it will save unneeded memory reallocation. If the array already
383 has enough memory for the given number of items, nothing happens.
385 \membersection{wxArray::Clear}\label{wxarrayclear}
387 \func{\void}{Clear}{\void}
389 This function does the same as \helpref{Empty()}{wxarrayempty} and additionally
390 frees the memory allocated to the array.
392 \membersection{wxArray::Count}\label{wxarraycount}
394 \constfunc{size\_t}{Count}{\void}
396 Same as \helpref{GetCount()}{wxarraygetcount}. This function is deprecated -
397 it exists only for compatibility.
399 \membersection{wxObjArray::Detach}\label{wxobjarraydetach}
401 \func{T *}{Detach}{\param{size\_t }{index}}
403 Removes the element from the array, but, unlike,
405 \helpref{Remove()}{wxarrayremove} doesn't delete it. The function returns the
406 pointer to the removed element.
408 \membersection{wxArray::Empty}\label{wxarrayempty}
410 \func{\void}{Empty}{\void}
412 Empties the array. For wxObjArray classes, this destroys all of the array
413 elements. For wxArray and wxSortedArray this does nothing except marking the
414 array of being empty - this function does not free the allocated memory, use
415 \helpref{Clear()}{wxarrayclear} for this.
417 \membersection{wxArray::GetCount}\label{wxarraygetcount}
419 \constfunc{size\_t}{GetCount}{\void}
421 Return the number of items in the array.
423 \membersection{wxArray::Index}\label{wxarrayindex}
425 \func{int}{Index}{\param{T\& }{item}, \param{bool }{searchFromEnd = FALSE}}
427 \func{int}{Index}{\param{T\& }{item}}
429 The first version of the function is for wxArray and wxObjArray, the second is
430 for wxSortedArray only.
432 Searches the element in the array, starting from either beginning or the end
433 depending on the value of {\it searchFromEnd} parameter. wxNOT\_FOUND is
434 returned if the element is not found, otherwise the index of the element is
437 Linear search is used for the wxArray and wxObjArray classes but binary search
438 in the sorted array is used for wxSortedArray (this is why searchFromEnd
439 parameter doesn't make sense for it).
441 \membersection{wxArray::Insert}\label{wxarrayinsert}
443 \func{\void}{Insert}{\param{T }{item}, \param{size\_t }{n}}
445 \func{\void}{Insert}{\param{T *}{item}, \param{size\_t }{n}}
447 \func{\void}{Insert}{\param{T \&}{item}, \param{size\_t }{n}}
449 Insert a new item into the array before the item {\it n} - thus, {\it
450 Insert(something, 0u}} will insert an item in such way that it will become the
453 Please see \helpref{Add()}{wxarrayadd} for explanation of the differences
454 between the overloaded versions of this function.
456 \membersection{wxArray::IsEmpty}\label{wxarrayisempty}
458 \constfunc{bool}{IsEmpty}{}
460 Returns TRUE if the array is empty, FALSE otherwise.
462 \membersection{wxArray::Item}\label{wxarrayitem}
464 \constfunc{T\&}{Item}{\param{size\_t }{index}}
466 Returns the item at the given position in the array. If {\it index} is out of
467 bounds, an assert failure is raised in the debug builds but nothing special is
468 done in the release build.
470 The returned value is of type "reference to the array element type" for all of
473 \membersection{wxArray::Last}\label{wxarraylast}
475 \constfunc{T\&}{Last}{\void}
477 Returns the last element in the array, i.e. is the same as Item(GetCount() - 1).
478 An assert failure is raised in the debug mode if the array is empty.
480 The returned value is of type "reference to the array element type" for all of
483 \membersection{wxArray::Remove}\label{wxarrayremove}
485 \func{\void}{Remove}{\param{size\_t }{index}}
487 \func{\void}{Remove}{\param{T }{item}}
489 Removes the element from the array either by index or by value. When an element
490 is removed from wxObjArray it is deleted by the array - use
491 \helpref{Detach()}{wxobjarraydetach} if you don't want this to happen. On the
492 other hand, when an object is removed from a wxArray nothing happens - you
493 should delete the it manually if required:
501 See also \helpref{WX\_CLEAR\_ARRAY}{wxcleararray} macro which deletes all
502 elements of a wxArray (supposed to contain pointers).
504 \membersection{wxArray::Shrink}\label{wxarrayshrink}
506 \func{\void}{Shrink}{\void}
508 Frees all memory unused by the array. If the program knows that no new items
509 will be added to the array it may call Shrink() to reduce its memory usage.
510 However, if a new item is added to the array, some extra memory will be
513 \membersection{wxArray::Sort}\label{wxarraysort}
515 \func{\void}{Sort}{\param{CMPFUNC<T> }{compareFunction}}
517 The notation CMPFUNC<T> should be read as if we had the following declaration:
520 template int CMPFUNC(T *first, T *second);
523 where {\it T} is the type of the array elements. I.e. it is a function returning
524 {\it int} which is passed two arguments of type {\it T *}.
526 Sorts the array using the specified compare function: this function should
527 return a negative, zero or positive value according to whether the first element
528 passed to it is less than, equal to or greater than the second one.
530 wxSortedArray doesn't have this function because it is always sorted.