1 /////////////////////////////////////////////////////////////////////////////
3 // Purpose: interface of wxArray<T>
4 // Author: wxWidgets team
6 // Licence: wxWindows license
7 /////////////////////////////////////////////////////////////////////////////
12 This section describes the so called @e "dynamic arrays". This is a C
13 array-like type safe data structure i.e. the member access time is constant
14 (and not linear according to the number of container elements as for linked
15 lists). However, these arrays are dynamic in the sense that they will
16 automatically allocate more memory if there is not enough of it for adding
17 a new element. They also perform range checking on the index values but in
18 debug mode only, so please be sure to compile your application in debug
19 mode to use it (see @ref overview_debugging for details). So, unlike the
20 arrays in some other languages, attempt to access an element beyond the
21 arrays bound doesn't automatically expand the array but provokes an
22 assertion failure instead in debug build and does nothing (except possibly
23 crashing your program) in the release build.
25 The array classes were designed to be reasonably efficient, both in terms
26 of run-time speed and memory consumption and the executable size. The speed
27 of array item access is, of course, constant (independent of the number of
28 elements) making them much more efficient than linked lists (wxList).
29 Adding items to the arrays is also implemented in more or less constant
30 time, but the price is preallocating the memory in advance. In the
31 "memory management" function section, you may find some useful hints about
32 optimizing wxArray memory usage. As for executable size, all wxArray
33 functions are inline, so they do not take @e any space at all.
35 wxWidgets has three different kinds of array. All of them derive from
36 wxBaseArray class which works with untyped data and can not be used
37 directly. The standard macros WX_DEFINE_ARRAY(), WX_DEFINE_SORTED_ARRAY()
38 and WX_DEFINE_OBJARRAY() are used to define a new class deriving from it.
39 The classes declared will be called in this documentation wxArray,
40 wxSortedArray and wxObjArray but you should keep in mind that no classes
41 with such names actually exist, each time you use one of the
42 WX_DEFINE_XXXARRAY() macros, you define a class with a new name. In fact,
43 these names are "template" names and each usage of one of the macros
44 mentioned above creates a template specialization for the given element
47 wxArray is suitable for storing integer types and pointers which it does
48 not treat as objects in any way, i.e. the element pointed to by the pointer
49 is not deleted when the element is removed from the array. It should be
50 noted that all of wxArray's functions are inline, so it costs strictly
51 nothing to define as many array types as you want (either in terms of the
52 executable size or the speed) as long as at least one of them is defined
53 and this is always the case because wxArrays are used by wxWidgets
54 internally. This class has one serious limitation: it can only be used for
55 storing integral types (bool, char, short, int, long and their unsigned
56 variants) or pointers (of any kind). An attempt to use with objects of
57 @c sizeof() greater than @c sizeof(long) will provoke a runtime assertion
58 failure, however declaring a wxArray of floats will not (on the machines
59 where @c "sizeof(float) <= sizeof(long)"), yet it will @b not work, please
60 use wxObjArray for storing floats and doubles.
62 wxSortedArray is a wxArray variant which should be used when searching in
63 the array is a frequently used operation. It requires you to define an
64 additional function for comparing two elements of the array element type
65 and always stores its items in the sorted order (according to this
66 function). Thus, its Index() function execution time is @c "O(log(N))"
67 instead of @c "O(N)" for the usual arrays but the Add() method is slower:
68 it is @c "O(log(N))" instead of constant time (neglecting time spent in
69 memory allocation routine). However, in a usual situation elements are
70 added to an array much less often than searched inside it, so wxSortedArray
71 may lead to huge performance improvements compared to wxArray. Finally, it
72 should be noticed that, as wxArray, wxSortedArray can be only used for
73 storing integral types or pointers.
75 wxObjArray class treats its elements like "objects". It may delete them
76 when they are removed from the array (invoking the correct destructor) and
77 copies them using the objects copy constructor. In order to implement this
78 behaviour the definition of the wxObjArray arrays is split in two parts:
79 first, you should declare the new wxObjArray class using the
80 WX_DECLARE_OBJARRAY() macro and then you must include the file defining the
81 implementation of template type: @<wx/arrimpl.cpp@> and define the array
82 class with the WX_DEFINE_OBJARRAY() macro from a point where the full (as
83 opposed to 'forward') declaration of the array elements class is in scope.
84 As it probably sounds very complicated here is an example:
87 #include <wx/dynarray.h>
89 // We must forward declare the array because it is used
90 // inside the class declaration.
94 // This defines two new types: ArrayOfDirectories and ArrayOfFiles which
95 // can be now used as shown below.
96 WX_DECLARE_OBJARRAY(MyDirectory, ArrayOfDirectories);
97 WX_DECLARE_OBJARRAY(MyFile, ArrayOfFiles);
102 ArrayOfDirectories m_subdirectories; // All subdirectories
103 ArrayOfFiles m_files; // All files in this directory
108 // Now that we have MyDirectory declaration in scope we may finish the
109 // definition of ArrayOfDirectories -- note that this expands into some C++
110 // code and so should only be compiled once (i.e., don't put this in the
111 // header, but into a source file or you will get linking errors)
112 #include <wx/arrimpl.cpp> // This is a magic incantation which must be done!
113 WX_DEFINE_OBJARRAY(ArrayOfDirectories);
118 It is not as elegant as writing this:
121 typedef std::vector<MyDirectory> ArrayOfDirectories;
124 But is not that complicated and allows the code to be compiled with any,
125 however dumb, C++ compiler in the world.
127 Remember to include @<wx/arrimpl.cpp@> just before each
128 WX_DEFINE_OBJARRAY() ocurrence in your code, even if you have several in
131 Things are much simpler for wxArray and wxSortedArray however: it is enough
135 WX_DEFINE_ARRAY_INT(int, ArrayOfInts);
136 WX_DEFINE_SORTED_ARRAY_INT(int, ArrayOfSortedInts);
139 There is only one @c DEFINE macro and no need for separate @c DECLARE one.
140 For the arrays of the primitive types, the macros
141 @c WX_DEFINE_ARRAY_CHAR/SHORT/INT/SIZE_T/LONG/DOUBLE should be used
142 depending on the sizeof of the values (notice that storing values of
143 smaller type, e.g. shorts, in an array of larger one, e.g. @c ARRAY_INT,
144 does not work on all architectures!).
147 @section array_macros Macros for Template Array Definition
149 To use an array you must first define the array class. This is done with
150 the help of the macros in this section. The class of array elements must be
151 (at least) forward declared for WX_DEFINE_ARRAY(), WX_DEFINE_SORTED_ARRAY()
152 and WX_DECLARE_OBJARRAY() macros and must be fully declared before you use
153 WX_DEFINE_OBJARRAY() macro.
156 - WX_DEFINE_EXPORTED_ARRAY()
157 - WX_DEFINE_USER_EXPORTED_ARRAY()
158 - WX_DEFINE_SORTED_ARRAY()
159 - WX_DEFINE_SORTED_EXPORTED_ARRAY()
160 - WX_DEFINE_SORTED_USER_EXPORTED_ARRAY()
161 - WX_DECLARE_EXPORTED_OBJARRAY()
162 - WX_DECLARE_USER_EXPORTED_OBJARRAY()
163 - WX_DEFINE_OBJARRAY()
164 - WX_DEFINE_EXPORTED_OBJARRAY()
165 - WX_DEFINE_USER_EXPORTED_OBJARRAY()
167 To slightly complicate the matters even further, the operator "->" defined
168 by default for the array iterators by these macros only makes sense if the
169 array element type is not a pointer itself and, although it still works,
170 this provokes warnings from some compilers and to avoid them you should use
171 the @c _PTR versions of the macros above. For example, to define an array
172 of pointers to @c double you should use:
175 WX_DEFINE_ARRAY_PTR(double *, MyArrayOfDoublePointers);
178 Note that the above macros are generally only useful for wxObject types.
179 There are separate macros for declaring an array of a simple type, such as
182 The following simple types are supported:
188 To create an array of a simple type, simply append the type you want in
189 CAPS to the array definition.
191 For example, you'd use one of the following variants for an integer array:
193 - WX_DEFINE_ARRAY_INT()
194 - WX_DEFINE_EXPORTED_ARRAY_INT()
195 - WX_DEFINE_USER_EXPORTED_ARRAY_INT()
196 - WX_DEFINE_SORTED_ARRAY_INT()
197 - WX_DEFINE_SORTED_EXPORTED_ARRAY_INT()
198 - WX_DEFINE_SORTED_USER_EXPORTED_ARRAY_INT()
202 @category{containers}
204 @see @ref overview_container, wxList<T>, wxVector<T>
210 @name Constructors and Destructors
212 Array classes are 100% C++ objects and as such they have the
213 appropriate copy constructors and assignment operators. Copying wxArray
214 just copies the elements but copying wxObjArray copies the arrays
215 items. However, for memory-efficiency sake, neither of these classes
216 has virtual destructor. It is not very important for wxArray which has
217 trivial destructor anyhow, but it does mean that you should avoid
218 deleting wxObjArray through a wxBaseArray pointer (as you would never
219 use wxBaseArray anyhow it shouldn't be a problem) and that you should
220 not derive your own classes from the array classes.
229 Default constructor initializes an empty array object.
233 There is no default constructor for wxSortedArray classes - you must
234 initialize it with a function to use for item comparison. It is a
235 function which is passed two arguments of type @c T where @c T is the
236 array element type and which should return a negative, zero or positive
237 value according to whether the first element passed to it is less than,
238 equal to or greater than the second one.
240 wxSortedArray(int (*)(T first
, T second
)compareFunction
);
243 Performs a shallow array copy (i.e. doesn't copy the objects pointed to
244 even if the source array contains the items of pointer type).
246 wxArray(const wxArray
& array
);
248 Performs a shallow array copy (i.e. doesn't copy the objects pointed to
249 even if the source array contains the items of pointer type).
251 wxSortedArray(const wxSortedArray
& array
);
253 Performs a deep copy (i.e. the array element are copied too).
255 wxObjArray(const wxObjArray
& array
);
258 Performs a shallow array copy (i.e. doesn't copy the objects pointed to
259 even if the source array contains the items of pointer type).
261 wxArray
& operator=(const wxArray
& array
);
263 Performs a shallow array copy (i.e. doesn't copy the objects pointed to
264 even if the source array contains the items of pointer type).
266 wxSortedArray
& operator=(const wxSortedArray
& array
);
268 Performs a deep copy (i.e. the array element are copied too).
270 wxObjArray
& operator=(const wxObjArray
& array
);
273 This destructor does not delete all the items owned by the array, you
274 may use the WX_CLEAR_ARRAY() macro for this.
278 This destructor does not delete all the items owned by the array, you
279 may use the WX_CLEAR_ARRAY() macro for this.
283 This destructor deletes all the items owned by the array.
291 @name Memory Management
293 Automatic array memory management is quite trivial: the array starts by
294 preallocating some minimal amount of memory (defined by
295 @c WX_ARRAY_DEFAULT_INITIAL_SIZE) and when further new items exhaust
296 already allocated memory it reallocates it adding 50% of the currently
297 allocated amount, but no more than some maximal number which is defined
298 by the @c ARRAY_MAXSIZE_INCREMENT constant. Of course, this may lead to
299 some memory being wasted (@c ARRAY_MAXSIZE_INCREMENT in the worst case,
300 i.e. 4Kb in the current implementation), so the Shrink() function is
301 provided to deallocate the extra memory. The Alloc() function can also
302 be quite useful if you know in advance how many items you are going to
303 put in the array and will prevent the array code from reallocating the
304 memory more times than needed.
309 Preallocates memory for a given number of array elements. It is worth
310 calling when the number of items which are going to be added to the
311 array is known in advance because it will save unneeded memory
312 reallocation. If the array already has enough memory for the given
313 number of items, nothing happens. In any case, the existing contents of
314 the array is not modified.
316 void Alloc(size_t count
);
319 Frees all memory unused by the array. If the program knows that no new
320 items will be added to the array it may call Shrink() to reduce its
321 memory usage. However, if a new item is added to the array, some extra
322 memory will be allocated again.
330 @name Number of Elements and Simple Item Access
332 Functions in this section return the total number of array elements and
333 allow to retrieve them - possibly using just the C array indexing []
334 operator which does exactly the same as the Item() method.
339 Return the number of items in the array.
341 size_t GetCount() const;
344 Returns @true if the array is empty, @false otherwise.
346 bool IsEmpty() const;
349 Returns the item at the given position in the array. If @a index is out
350 of bounds, an assert failure is raised in the debug builds but nothing
351 special is done in the release build.
353 The returned value is of type "reference to the array element type" for
354 all of the array classes.
356 T
& Item(size_t index
) const;
359 Returns the last element in the array, i.e. is the same as calling
360 "Item(GetCount() - 1)". An assert failure is raised in the debug mode
361 if the array is empty.
363 The returned value is of type "reference to the array element type" for
364 all of the array classes.
377 Appends the given number of @a copies of the @a item to the array
378 consisting of the elements of type @c T.
380 This version is used with wxArray.
382 You may also use WX_APPEND_ARRAY() macro to append all elements of one
383 array to another one but it is more efficient to use the @a copies
384 parameter and modify the elements in place later if you plan to append
387 void Add(T item
, size_t copies
= 1);
389 Appends the @a item to the array consisting of the elements of type
392 This version is used with wxSortedArray, returning the index where
397 Appends the @a item to the array consisting of the elements of type
400 This version is used with wxObjArray. The array will take ownership of
401 the @item, deleting it when the item is deleted from the array. Note
402 that you cannot append more than one pointer as reusing it would lead
403 to deleting it twice (or more) resulting in a crash.
405 You may also use WX_APPEND_ARRAY() macro to append all elements of one
406 array to another one but it is more efficient to use the @a copies
407 parameter and modify the elements in place later if you plan to append
412 Appends the given number of @a copies of the @a item to the array
413 consisting of the elements of type @c T.
415 This version is used with wxObjArray. The array will make a copy of the
416 item and will not take ownership of the original item.
418 You may also use WX_APPEND_ARRAY() macro to append all elements of one
419 array to another one but it is more efficient to use the @a copies
420 parameter and modify the elements in place later if you plan to append
423 void Add(T
& item
, size_t copies
= 1);
426 Inserts the given @a item into the array in the specified @e index
429 Be aware that you will set out the order of the array if you give a
432 This function is useful in conjunction with IndexForInsert() for a
433 common operation of "insert only if not found".
435 void AddAt(T item
, size_t index
);
438 Insert the given number of @a copies of the @a item into the array
439 before the existing item @a n - thus, @e Insert(something, 0u) will
440 insert an item in such way that it will become the first array element.
442 wxSortedArray doesn't have this function because inserting in wrong
443 place would break its sorted condition.
445 Please see Add() for an explanation of the differences between the
446 overloaded versions of this function.
448 void Insert(T item
, size_t n
, size_t copies
= 1);
450 Insert the @a item into the array before the existing item @a n - thus,
451 @e Insert(something, 0u) will insert an item in such way that it will
452 become the first array element.
454 wxSortedArray doesn't have this function because inserting in wrong
455 place would break its sorted condition.
457 Please see Add() for an explanation of the differences between the
458 overloaded versions of this function.
460 void Insert(T
* item
, size_t n
);
462 Insert the given number of @a copies of the @a item into the array
463 before the existing item @a n - thus, @e Insert(something, 0u) will
464 insert an item in such way that it will become the first array element.
466 wxSortedArray doesn't have this function because inserting in wrong
467 place would break its sorted condition.
469 Please see Add() for an explanation of the differences between the
470 overloaded versions of this function.
472 void Insert(T
& item
, size_t n
, size_t copies
= 1);
475 This function ensures that the number of array elements is at least
476 @a count. If the array has already @a count or more items, nothing is
477 done. Otherwise, @a count - GetCount() elements are added and
478 initialized to the value @a defval.
482 void SetCount(size_t count
, T defval
= T(0));
493 This function does the same as Empty() and additionally frees the
494 memory allocated to the array.
499 Removes the element from the array, but unlike Remove(), it doesn't
500 delete it. The function returns the pointer to the removed element.
502 T
* Detach(size_t index
);
505 Empties the array. For wxObjArray classes, this destroys all of the
506 array elements. For wxArray and wxSortedArray this does nothing except
507 marking the array of being empty - this function does not free the
508 allocated memory, use Clear() for this.
513 Removes an element from the array by value: the first item of the array
514 equal to @a item is removed, an assert failure will result from an
515 attempt to remove an item which doesn't exist in the array.
517 When an element is removed from wxObjArray it is deleted by the array -
518 use Detach() if you don't want this to happen. On the other hand, when
519 an object is removed from a wxArray nothing happens - you should delete
520 it manually if required:
528 See also WX_CLEAR_ARRAY() macro which deletes all elements of a wxArray
529 (supposed to contain pointers).
534 Removes @a count elements starting at @a index from the array. When an
535 element is removed from wxObjArray it is deleted by the array - use
536 Detach() if you don't want this to happen. On the other hand, when an
537 object is removed from a wxArray nothing happens - you should delete it
538 manually if required:
546 See also WX_CLEAR_ARRAY() macro which deletes all elements of a wxArray
547 (supposed to contain pointers).
549 RemoveAt(size_t index
, size_t count
= 1);
555 @name Searching and Sorting
560 This version of Index() is for wxArray and wxObjArray only.
562 Searches the element in the array, starting from either beginning or
563 the end depending on the value of @a searchFromEnd parameter.
564 @c wxNOT_FOUND is returned if the element is not found, otherwise the
565 index of the element is returned.
567 @note Even for wxObjArray classes, the operator "==" of the elements in
568 the array is @b not used by this function. It searches exactly
569 the given element in the array and so will only succeed if this
570 element had been previously added to the array, but fail even if
571 another, identical, element is in the array.
573 int Index(T
& item
, bool searchFromEnd
= false) const;
575 This version of Index() is for wxSortedArray only.
577 Searches the element in the array, starting from either beginning or
578 the end depending on the value of @a searchFromEnd parameter.
579 @c wxNOT_FOUND is returned if the element is not found, otherwise the
580 index of the element is returned.
582 const int Index(T
& item
) const;
585 Search for a place to insert @a item into the sorted array (binary
586 search). The index returned is just before the first existing item that
587 is greater or equal (according to the compare function) to the given
590 You have to do extra work to know if the @a item already exists in
593 This function is useful in conjunction with AddAt() for a common
594 operation of "insert only if not found".
596 size_t IndexForInsert(T item
) const;
599 The notation @c "CMPFUNCT<T>" should be read as if we had the following
603 template int CMPFUNC(T *first, T *second);
606 Where @e T is the type of the array elements. I.e. it is a function
607 returning @e int which is passed two arguments of type @e T*.
609 Sorts the array using the specified compare function: this function
610 should return a negative, zero or positive value according to whether
611 the first element passed to it is less than, equal to or greater than
614 wxSortedArray doesn't have this function because it is always sorted.
616 void Sort(CMPFUNC
<T
> compareFunction
);
623 This macro may be used to append all elements of the @a other array to the
624 @a array. The two arrays must be of the same type.
626 #define WX_APPEND_ARRAY(wxArray& array, wxArray& other)
629 This macro may be used to delete all elements of the array before emptying
630 it. It can not be used with wxObjArrays - but they will delete their
631 elements anyway when you call Empty().
633 #define WX_CLEAR_ARRAY(wxArray& array)
637 This macro declares a new object array class named @a name and containing
638 the elements of type @e T.
640 An exported array is used when compiling wxWidgets as a DLL under Windows
641 and the array needs to be visible outside the DLL. An user exported array
642 needed for exporting an array from a user DLL.
648 WX_DECLARE_OBJARRAY(MyClass, wxArrayOfMyClass); // note: not "MyClass *"!
651 You must use WX_DEFINE_OBJARRAY() macro to define the array class,
652 otherwise you would get link errors.
654 #define WX_DECLARE_OBJARRAY(T, name)
655 #define WX_DECLARE_EXPORTED_OBJARRAY(T, name)
656 #define WX_DECLARE_USER_EXPORTED_OBJARRAY(T, name)
661 This macro defines a new array class named @a name and containing the
662 elements of type @a T.
664 An exported array is used when compiling wxWidgets as a DLL under Windows
665 and the array needs to be visible outside the DLL. An user exported array
666 needed for exporting an array from a user DLL.
671 WX_DEFINE_ARRAY_INT(int, MyArrayInt);
674 WX_DEFINE_ARRAY(MyClass *, ArrayOfMyClass);
677 Note that wxWidgets predefines the following standard array classes:
678 @b wxArrayInt, @b wxArrayLong, @b wxArrayShort, @b wxArrayDouble,
681 #define WX_DEFINE_ARRAY(T, name)
682 #define WX_DEFINE_EXPORTED_ARRAY(T, name)
683 #define WX_DEFINE_USER_EXPORTED_ARRAY(T, name, exportspec)
688 This macro defines the methods of the array class @a name not defined by
689 the WX_DECLARE_OBJARRAY() macro. You must include the file
690 @<wx/arrimpl.cpp@> before using this macro and you must have the full
691 declaration of the class of array elements in scope! If you forget to do
692 the first, the error will be caught by the compiler, but, unfortunately,
693 many compilers will not give any warnings if you forget to do the second -
694 but the objects of the class will not be copied correctly and their real
695 destructor will not be called.
697 An exported array is used when compiling wxWidgets as a DLL under Windows
698 and the array needs to be visible outside the DLL. An user exported array
699 needed for exporting an array from a user DLL.
704 // first declare the class!
708 MyClass(const MyClass&);
715 #include <wx/arrimpl.cpp>
716 WX_DEFINE_OBJARRAY(wxArrayOfMyClass);
719 #define WX_DEFINE_OBJARRAY(name)
720 #define WX_DEFINE_EXPORTED_OBJARRAY(name)
721 #define WX_DEFINE_USER_EXPORTED_OBJARRAY(name)
726 This macro defines a new sorted array class named @a name and containing
727 the elements of type @e T.
729 An exported array is used when compiling wxWidgets as a DLL under Windows
730 and the array needs to be visible outside the DLL. An user exported array
731 needed for exporting an array from a user DLL.
736 WX_DEFINE_SORTED_ARRAY_INT(int, MySortedArrayInt);
739 WX_DEFINE_SORTED_ARRAY(MyClass *, ArrayOfMyClass);
742 You will have to initialize the objects of this class by passing a
743 comparison function to the array object constructor like this:
746 int CompareInts(int n1, int n2)
751 MySortedArrayInt sorted(CompareInts);
753 int CompareMyClassObjects(MyClass *item1, MyClass *item2)
755 // sort the items by their address...
756 return Stricmp(item1->GetAddress(), item2->GetAddress());
759 ArrayOfMyClass another(CompareMyClassObjects);
762 #define WX_DEFINE_SORTED_ARRAY(T, name)
763 #define WX_DEFINE_SORTED_EXPORTED_ARRAY(T, name)
764 #define WX_DEFINE_SORTED_USER_EXPORTED_ARRAY(T, name)
768 This macro may be used to prepend all elements of the @a other array to the
769 @a array. The two arrays must be of the same type.
771 #define WX_PREPEND_ARRAY(wxArray& array, wxArray& other)