X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/6e6110ee8194ee39944dffd57cce9f22cd8b961e..e195c8c95fb154d035bab400952fc81c62439549:/docs/latex/wx/array.tex diff --git a/docs/latex/wx/array.tex b/docs/latex/wx/array.tex index 41d5c66f3f..733e548d5d 100644 --- a/docs/latex/wx/array.tex +++ b/docs/latex/wx/array.tex @@ -1,3 +1,596 @@ \section{\class{wxArray}}\label{wxarray} -TODO +This section describes the so called {\it dynamic arrays}. This is a C +array-like data structure i.e. the member access time is constant (and not +linear according to the number of container elements as for linked lists). However, these +arrays are dynamic in the sense that they will automatically allocate more +memory if there is not enough of it for adding a new element. They also perform +range checking on the index values but in debug mode only, so please be sure to +compile your application in debug mode to use it (see \helpref{debugging overview}{debuggingoverview} for +details). So, unlike the arrays in some other +languages, attempt to access an element beyond the arrays bound doesn't +automatically expand the array but provokes an assertion failure instead in +debug build and does nothing (except possibly crashing your program) in the +release build. + +The array classes were designed to be reasonably efficient, both in terms of +run-time speed and memory consumption and the executable size. The speed of +array item access is, of course, constant (independent of the number of elements) +making them much more efficient than linked lists (\helpref{wxList}{wxlist}). +Adding items to the arrays is also implemented in more or less constant time - +but the price is preallocating the memory in advance. In the \helpref{memory management}{wxarraymemorymanagement} section +you may find some useful hints about optimizing wxArray memory usage. As for executable size, all +wxArray functions are inline, so they do not take {\it any space at all}. + +wxWindows has three different kinds of array. All of them derive from +wxBaseArray class which works with untyped data and can not be used directly. +The standard macros WX\_DEFINE\_ARRAY(), WX\_DEFINE\_SORTED\_ARRAY() and +WX\_DEFINE\_OBJARRAY() are used to define a new class deriving from it. The +classes declared will be called in this documentation wxArray, wxSortedArray and +wxObjArray but you should keep in mind that no classes with such names actually +exist, each time you use one of WX\_DEFINE\_XXXARRAY macro you define a class +with a new name. In fact, these names are "template" names and each usage of one +of the macros mentioned above creates a template specialization for the given +element type. + +wxArray is suitable for storing integer types and pointers which it does not +treat as objects in any way, i.e. the element pointed to by the pointer is not +deleted when the element is removed from the array. It should be noted that +all of wxArray's functions are inline, so it costs strictly nothing to define as +many array types as you want (either in terms of the executable size or the +speed) as long as at least one of them is defined and this is always the case +because wxArrays are used by wxWindows internally. This class has one serious +limitation: it can only be used for storing integral types (bool, char, short, +int, long and their unsigned variants) or pointers (of any kind). An attempt +to use with objects of sizeof() greater than sizeof(long) will provoke a +runtime assertion failure, however declaring a wxArray of floats will not (on +the machines where sizeof(float) <= sizeof(long)), yet it will {\bf not} work, +please use wxObjArray for storing floats and doubles (NB: a more efficient +wxArrayDouble class is scheduled for the next release of wxWindows). + +wxSortedArray is a wxArray variant which should be used when searching in the +array is a frequently used operation. It requires you to define an additional +function for comparing two elements of the array element type and always stores +its items in the sorted order (according to this function). Thus, it is + \helpref{Index()}{wxarrayindex} function execution time is $O(log(N))$ instead of +$O(N)$ for the usual arrays but the \helpref{Add()}{wxarrayadd} method is +slower: it is $O(log(N))$ instead of constant time (neglecting time spent in +memory allocation routine). However, in a usual situation elements are added to +an array much less often than searched inside it, so wxSortedArray may lead to +huge performance improvements compared to wxArray. Finally, it should be +noticed that, as wxArray, wxSortedArray can be only used for storing integral +types or pointers. + +wxObjArray class treats its elements like "objects". It may delete them when +they are removed from the array (invoking the correct destructor) and copies +them using the objects copy constructor. In order to implement this behaviour +the definition of the wxObjArray arrays is split in two parts: first, you should +declare the new wxObjArray class using WX\_DECLARE\_OBJARRAY() macro and then +you must include the file defining the implementation of template type: + and define the array class with WX\_DEFINE\_OBJARRAY() macro +from a point where the full (as opposed to `forward') declaration of the array +elements class is in scope. As it probably sounds very complicated here is an +example: + +\begin{verbatim} +#include + +// we must forward declare the array because it is used inside the class +// declaration +class MyDirectory; +class MyFile; + +// this defines two new types: ArrayOfDirectories and ArrayOfFiles which can be +// now used as shown below +WX_DECLARE_OBJARRAY(MyDirectory, ArrayOfDirectories); +WX_DECLARE_OBJARRAY(MyFile, ArrayOfFiles); + +class MyDirectory +{ +... + ArrayOfDirectories m_subdirectories; // all subdirectories + ArrayOfFiles m_files; // all files in this directory +}; + +... + +// now that we have MyDirectory declaration in scope we may finish the +// definition of ArrayOfDirectories -- note that this expands into some C++ +// code and so should only be compiled once (i.e., don't put this in the +// header, but into a source file or you will get linkin errors) +#include // this is a magic incantation which must be done! +WX_DEFINE_OBJARRAY(ArrayOfDirectories); + +// that's all! +\end{verbatim} + +It is not as elegant as writing + +\begin{verbatim} +typedef std::vector ArrayOfDirectories; +\end{verbatim} + +but is not that complicated and allows the code to be compiled with any, however +dumb, C++ compiler in the world. + +Things are much simpler for wxArray and wxSortedArray however: it is enough +just to write + +\begin{verbatim} +WX_DEFINE_ARRAY(MyDirectory *, ArrayOfDirectories); +WX_DEFINE_SORTED_ARRAY(MyFile *, ArrayOfFiles); +\end{verbatim} + +\wxheading{See also:} + +\helpref{Container classes overview}{wxcontaineroverview}, \helpref{wxList}{wxlist} + +\wxheading{Include files} + + for wxArray and wxSortedArray and additionally +for wxObjArray. + +\latexignore{\rtfignore{\wxheading{Function groups}}} + +\membersection{Macros for template array definition} + +To use an array you must first define the array class. This is done with the +help of the macros in this section. The class of array elements must be (at +least) forward declared for WX\_DEFINE\_ARRAY, WX\_DEFINE\_SORTED\_ARRAY and +WX\_DECLARE\_OBJARRAY macros and must be fully declared before you use +WX\_DEFINE\_OBJARRAY macro. + +\helpref{WX\_DEFINE\_ARRAY}{wxdefinearray}\\ +\helpref{WX\_DEFINE\_EXPORTED\_ARRAY}{wxdefinearray}\\ +\helpref{WX\_DEFINE\_SORTED\_ARRAY}{wxdefinesortedarray}\\ +\helpref{WX\_DEFINE\_SORTED\_EXPORTED\_ARRAY}{wxdefinesortedarray}\\ +\helpref{WX\_DECLARE\_EXPORTED\_OBJARRAY}{wxdeclareobjarray}\\ +\helpref{WX\_DEFINE\_OBJARRAY}{wxdefineobjarray} + +\membersection{Constructors and destructors} + +Array classes are 100\% C++ objects and as such they have the appropriate copy +constructors and assignment operators. Copying wxArray just copies the elements +but copying wxObjArray copies the arrays items. However, for memory-efficiency +sake, neither of these classes has virtual destructor. It is not very important +for wxArray which has trivial destructor anyhow, but it does mean that you +should avoid deleting wxObjArray through a wxBaseArray pointer (as you would +never use wxBaseArray anyhow it shouldn't be a problem) and that you should not +derive your own classes from the array classes. + +\helpref{wxArray default constructor}{wxarrayctordef}\\ +\helpref{wxArray copy constructors and assignment operators}{wxarrayctorcopy}\\ +\helpref{\destruct{wxArray}}{wxarraydtor} + +\membersection{Memory management}\label{wxarraymemorymanagement} + +Automatic array memory management is quite trivial: the array starts by +preallocating some minimal amount of memory (defined by +WX\_ARRAY\_DEFAULT\_INITIAL\_SIZE) and when further new items exhaust already +allocated memory it reallocates it adding 50\% of the currently allocated +amount, but no more than some maximal number which is defined by +ARRAY\_MAXSIZE\_INCREMENT constant. Of course, this may lead to some memory +being wasted (ARRAY\_MAXSIZE\_INCREMENT in the worst case, i.e. 4Kb in the +current implementation), so the \helpref{Shrink()}{wxarrayshrink} function is +provided to unallocate the extra memory. The \helpref{Alloc()}{wxarrayalloc} +function can also be quite useful if you know in advance how many items you are +going to put in the array and will prevent the array code from reallocating the +memory more times than needed. + +\helpref{Alloc}{wxarrayalloc}\\ +\helpref{Shrink}{wxarrayshrink} + +\membersection{Number of elements and simple item access} + +Functions in this section return the total number of array elements and allow to +retrieve them - possibly using just the C array indexing $[]$ operator which +does exactly the same as \helpref{Item()}{wxarrayitem} method. + +\helpref{Count}{wxarraycount}\\ +\helpref{GetCount}{wxarraygetcount}\\ +\helpref{IsEmpty}{wxarrayisempty}\\ +\helpref{Item}{wxarrayitem}\\ +\helpref{Last}{wxarraylast} + +\membersection{Adding items} + +\helpref{Add}{wxarrayadd}\\ +\helpref{Insert}{wxarrayinsert}\\ +\helpref{WX\_APPEND\_ARRAY}{wxappendarray} + +\membersection{Removing items} + +\helpref{WX\_CLEAR\_ARRAY}{wxcleararray}\\ +\helpref{Empty}{wxarrayempty}\\ +\helpref{Clear}{wxarrayclear}\\ +\helpref{RemoveAt}{wxarrayremoveat}\\ +\helpref{Remove}{wxarrayremove} + +\membersection{Searching and sorting} + +\helpref{Index}{wxarrayindex}\\ +\helpref{Sort}{wxarraysort} + +%%%%% MEMBERS HERE %%%%% +\helponly{\insertatlevel{2}{ + +\wxheading{Members} + +}} + +\membersection{WX\_DEFINE\_ARRAY}\label{wxdefinearray} + +\func{}{WX\_DEFINE\_ARRAY}{\param{}{T}, \param{}{name}} + +\func{}{WX\_DEFINE\_EXPORTED\_ARRAY}{\param{}{T}, \param{}{name}} + +This macro defines a new array class named {\it name} and containing the +elements of type {\it T}. The second form is used when compiling DLL +under Windows and array needs to be visible outside the DLL. +Example: + +\begin{verbatim} +WX_DEFINE_ARRAY(int, wxArrayInt); + +class MyClass; +WX_DEFINE_ARRAY(MyClass *, wxArrayOfMyClass); +\end{verbatim} + +Note that wxWindows predefines the following standard array classes: wxArrayInt, +wxArrayLong and wxArrayPtrVoid. + +\membersection{WX\_DEFINE\_SORTED\_ARRAY}\label{wxdefinesortedarray} + +\func{}{WX\_DEFINE\_SORTED\_ARRAY}{\param{}{T}, \param{}{name}} + +\func{}{WX\_DEFINE\_SORTED\_EXPORTED\_ARRAY}{\param{}{T}, \param{}{name}} + +This macro defines a new sorted array class named {\it name} and containing +the elements of type {\it T}. The second form is used when compiling DLL +under Windows and array needs to be visible outside the DLL. + +Example: + +\begin{verbatim} +WX_DEFINE_SORTED_ARRAY(int, wxSortedArrayInt); + +class MyClass; +WX_DEFINE_SORTED_ARRAY(MyClass *, wxArrayOfMyClass); +\end{verbatim} + +You will have to initialize the objects of this class by passing a comparison +function to the array object constructor like this: + +\begin{verbatim} +int CompareInts(int n1, int n2) +{ + return n1 - n2; +} + +wxSortedArrayInt sorted(CompareInts); + +int CompareMyClassObjects(MyClass *item1, MyClass *item2) +{ + // sort the items by their address... + return Stricmp(item1->GetAddress(), item2->GetAddress()); +} + +wxArrayOfMyClass another(CompareMyClassObjects); +\end{verbatim} + +\membersection{WX\_DECLARE\_OBJARRAY}\label{wxdeclareobjarray} + +\func{}{WX\_DECLARE\_OBJARRAY}{\param{}{T}, \param{}{name}} + +\func{}{WX\_DECLARE\_EXPORTED\_OBJARRAY}{\param{}{T}, \param{}{name}} + +This macro declares a new object array class named {\it name} and containing +the elements of type {\it T}. The second form is used when compiling DLL +under Windows and array needs to be visible outside the DLL. + +Example: + +\begin{verbatim} +class MyClass; +WX_DEFINE_OBJARRAY(MyClass, wxArrayOfMyClass); // note: not "MyClass *"! +\end{verbatim} + +You must use \helpref{WX\_DEFINE\_OBJARRAY()}{wxdefineobjarray} macro to define +the array class - otherwise you would get link errors. + +\membersection{WX\_DEFINE\_OBJARRAY}\label{wxdefineobjarray} + +\func{}{WX\_DEFINE\_OBJARRAY}{\param{}{name}} + +This macro defines the methods of the array class {\it name} not defined by the +\helpref{WX\_DECLARE\_OBJARRAY()}{wxdeclareobjarray} macro. You must include the +file before using this macro and you must have the full +declaration of the class of array elements in scope! If you forget to do the +first, the error will be caught by the compiler, but, unfortunately, many +compilers will not give any warnings if you forget to do the second - but the +objects of the class will not be copied correctly and their real destructor will +not be called. + +Example of usage: + +\begin{verbatim} +// first declare the class! +class MyClass +{ +public: + MyClass(const MyClass&); + + ... + + virtual ~MyClass(); +}; + +#include +WX_DEFINE_OBJARRAY(wxArrayOfMyClass); +\end{verbatim} + +\membersection{WX\_APPEND\_ARRAY}\label{wxappendarray} + +\func{void}{WX\_APPEND\_ARRAY}{\param{wxArray\& }{array}, \param{wxArray\& }{other}} + +This macro may be used to append all elements of the {\it other} array to the +{\it array}. The two arrays must be of the same type. + +\membersection{WX\_CLEAR\_ARRAY}\label{wxcleararray} + +\func{void}{WX\_CLEAR\_ARRAY}{\param{wxArray\& }{array}} + +This macro may be used to delete all elements of the array before emptying it. +It can not be used with wxObjArrays - but they will delete their elements anyhow +when you call Empty(). + +\membersection{Default constructors}\label{wxarrayctordef} + +\func{}{wxArray}{\void} + +\func{}{wxObjArray}{\void} + +Default constructor initializes an empty array object. + +\func{}{wxSortedArray}{\param{int (*)(T first, T second)}{compareFunction}} + +There is no default constructor for wxSortedArray classes - you must initialize it +with a function to use for item comparison. It is a function which is passed +two arguments of type {\it T} where {\it T} is the array element type and which +should return a negative, zero or positive value according to whether the first +element passed to it is less than, equal to or greater than the second one. + +\membersection{wxArray copy constructor and assignment operator}\label{wxarrayctorcopy} + +\func{}{wxArray}{\param{const wxArray\& }{array}} + +\func{}{wxSortedArray}{\param{const wxSortedArray\& }{array}} + +\func{}{wxObjArray}{\param{const wxObjArray\& }{array}} + +\func{wxArray\&}{operator$=$}{\param{const wxArray\& }{array}} + +\func{wxSortedArray\&}{operator$=$}{\param{const wxSortedArray\& }{array}} + +\func{wxObjArray\&}{operator$=$}{\param{const wxObjArray\& }{array}} + +The copy constructors and assignment operators perform a shallow array copy +(i.e. they don't copy the objects pointed to even if the source array contains +the items of pointer type) for wxArray and wxSortedArray and a deep copy (i.e. +the array element are copied too) for wxObjArray. + +\membersection{wxArray::\destruct{wxArray}}\label{wxarraydtor} + +\func{}{\destruct{wxArray}}{\void} + +\func{}{\destruct{wxSortedArray}}{\void} + +\func{}{\destruct{wxObjArray}}{\void} + +The wxObjArray destructor deletes all the items owned by the array. This is not +done by wxArray and wxSortedArray versions - you may use +\helpref{WX\_CLEAR\_ARRAY}{wxcleararray} macro for this. + +\membersection{wxArray::Add}\label{wxarrayadd} + +\func{void}{Add}{\param{T }{item}} + +\func{void}{Add}{\param{T *}{item}} + +\func{void}{Add}{\param{T \&}{item}} + +Appends a new element to the array (where {\it T} is the type of the array +elements.) + +The first version is used with wxArray and wxSortedArray. The second and the +third are used with wxObjArray. There is an important difference between +them: if you give a pointer to the array, it will take ownership of it, i.e. +will delete it when the item is deleted from the array. If you give a reference +to the array, however, the array will make a copy of the item and will not take +ownership of the original item. Once again, it only makes sense for wxObjArrays +because the other array types never take ownership of their elements. + +You may also use \helpref{WX\_APPEND\_ARRAY}{wxappendarray} macro to append all +elements of one array to another one. + +\membersection{wxArray::Alloc}\label{wxarrayalloc} + +\func{void}{Alloc}{\param{size\_t }{count}} + +Preallocates memory for a given number of array elements. It is worth calling +when the number of items which are going to be added to the array is known in +advance because it will save unneeded memory reallocation. If the array already +has enough memory for the given number of items, nothing happens. + +\membersection{wxArray::Clear}\label{wxarrayclear} + +\func{void}{Clear}{\void} + +This function does the same as \helpref{Empty()}{wxarrayempty} and additionally +frees the memory allocated to the array. + +\membersection{wxArray::Count}\label{wxarraycount} + +\constfunc{size\_t}{Count}{\void} + +Same as \helpref{GetCount()}{wxarraygetcount}. This function is deprecated - +it exists only for compatibility. + +\membersection{wxObjArray::Detach}\label{wxobjarraydetach} + +\func{T *}{Detach}{\param{size\_t }{index}} + +Removes the element from the array, but, unlike, +\helpref{Remove()}{wxarrayremove} doesn't delete it. The function returns the +pointer to the removed element. + +\membersection{wxArray::Empty}\label{wxarrayempty} + +\func{void}{Empty}{\void} + +Empties the array. For wxObjArray classes, this destroys all of the array +elements. For wxArray and wxSortedArray this does nothing except marking the +array of being empty - this function does not free the allocated memory, use +\helpref{Clear()}{wxarrayclear} for this. + +\membersection{wxArray::GetCount}\label{wxarraygetcount} + +\constfunc{size\_t}{GetCount}{\void} + +Return the number of items in the array. + +\membersection{wxArray::Index}\label{wxarrayindex} + +\func{int}{Index}{\param{T\& }{item}, \param{bool }{searchFromEnd = FALSE}} + +\func{int}{Index}{\param{T\& }{item}} + +The first version of the function is for wxArray and wxObjArray, the second is +for wxSortedArray only. + +Searches the element in the array, starting from either beginning or the end +depending on the value of {\it searchFromEnd} parameter. wxNOT\_FOUND is +returned if the element is not found, otherwise the index of the element is +returned. + +Linear search is used for the wxArray and wxObjArray classes but binary search +in the sorted array is used for wxSortedArray (this is why searchFromEnd +parameter doesn't make sense for it). + +{\bf NB:} even for wxObjArray classes, the operator==() of the elements in the +array is {\bf not} used by this function. It searches exactly the given +element in the array and so will only succeed if this element had been +previously added to the array, but fail even if another, identical, element is +in the array. + +\membersection{wxArray::Insert}\label{wxarrayinsert} + +\func{void}{Insert}{\param{T }{item}, \param{size\_t }{n}} + +\func{void}{Insert}{\param{T *}{item}, \param{size\_t }{n}} + +\func{void}{Insert}{\param{T \&}{item}, \param{size\_t }{n}} + +Insert a new item into the array before the item {\it n} - thus, {\it Insert(something, 0u)} will +insert an item in such way that it will become the +first array element. + +Please see \helpref{Add()}{wxarrayadd} for explanation of the differences +between the overloaded versions of this function. + +\membersection{wxArray::IsEmpty}\label{wxarrayisempty} + +\constfunc{bool}{IsEmpty}{\void} + +Returns TRUE if the array is empty, FALSE otherwise. + +\membersection{wxArray::Item}\label{wxarrayitem} + +\constfunc{T\&}{Item}{\param{size\_t }{index}} + +Returns the item at the given position in the array. If {\it index} is out of +bounds, an assert failure is raised in the debug builds but nothing special is +done in the release build. + +The returned value is of type "reference to the array element type" for all of +the array classes. + +\membersection{wxArray::Last}\label{wxarraylast} + +\constfunc{T\&}{Last}{\void} + +Returns the last element in the array, i.e. is the same as Item(GetCount() - 1). +An assert failure is raised in the debug mode if the array is empty. + +The returned value is of type "reference to the array element type" for all of +the array classes. + +\membersection{wxArray::Remove}\label{wxarrayremove} + +\func{\void}{Remove}{\param{T }{item}} + +Removes an element from the array by value: the first item of the +array equal to {\it item} is removed, an assert failure will result from an +attempt to remove an item which doesn't exist in the array. + +When an element is removed from wxObjArray it is deleted by the array - use +\helpref{Detach()}{wxobjarraydetach} if you don't want this to happen. On the +other hand, when an object is removed from a wxArray nothing happens - you +should delete it manually if required: + +\begin{verbatim} +T *item = array[n]; +delete item; +array.Remove(n) +\end{verbatim} + +See also \helpref{WX\_CLEAR\_ARRAY}{wxcleararray} macro which deletes all +elements of a wxArray (supposed to contain pointers). + +\membersection{wxArray::RemoveAt}\label{wxarrayremoveat} + +\func{\void}{RemoveAt}{\param{size\_t }{index}} + +Removes an element from the array by index. When an element +is removed from wxObjArray it is deleted by the array - use +\helpref{Detach()}{wxobjarraydetach} if you don't want this to happen. On the +other hand, when an object is removed from a wxArray nothing happens - you +should delete it manually if required: + +\begin{verbatim} +T *item = array[n]; +delete item; +array.RemoveAt(n) +\end{verbatim} + +See also \helpref{WX\_CLEAR\_ARRAY}{wxcleararray} macro which deletes all +elements of a wxArray (supposed to contain pointers). + +\membersection{wxArray::Shrink}\label{wxarrayshrink} + +\func{void}{Shrink}{\void} + +Frees all memory unused by the array. If the program knows that no new items +will be added to the array it may call Shrink() to reduce its memory usage. +However, if a new item is added to the array, some extra memory will be +allocated again. + +\membersection{wxArray::Sort}\label{wxarraysort} + +\func{void}{Sort}{\param{CMPFUNC }{compareFunction}} + +The notation CMPFUNC should be read as if we had the following declaration: + +\begin{verbatim} +template int CMPFUNC(T *first, T *second); +\end{verbatim} + +where {\it T} is the type of the array elements. I.e. it is a function returning +{\it int} which is passed two arguments of type {\it T *}. + +Sorts the array using the specified compare function: this function should +return a negative, zero or positive value according to whether the first element +passed to it is less than, equal to or greater than the second one. + +wxSortedArray doesn't have this function because it is always sorted. +