+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:
+<wx/arrimpl.cpp> 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 <wx/dynarray.h>
+
+// 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 <wx/arrimpl.cpp> // 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<MyDirectory> 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}
+
+<wx/dynarray.h> for wxArray and wxSortedArray and additionally <wx/arrimpl.cpp>
+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 <wx/arrimpl.cpp> 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/arrimpl.cpp>
+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<T> }{compareFunction}}
+
+The notation CMPFUNC<T> 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.
+
projects / wxWidgets.git / blobdiff