docs/Writerside/topics/list.h.md

changeset 1428
0ac4aa1737fd
parent 1421
809eb30cd621
child 1429
6e0c3a8a914a
equal deleted inserted replaced
1427:943bfd9e7978 1428:0ac4aa1737fd
146 The functions `cxListEmplace()` and `cxListEmplaceAt()` behave like `cxListAdd()` and `cxListInsert()`, 146 The functions `cxListEmplace()` and `cxListEmplaceAt()` behave like `cxListAdd()` and `cxListInsert()`,
147 except that they only allocate the memory and return a pointer to it, leaving it to the callee to copy the element data into it. 147 except that they only allocate the memory and return a pointer to it, leaving it to the callee to copy the element data into it.
148 Be aware that when the list is storing pointers, the allocated memory will be for the pointer, not the actual element's data. 148 Be aware that when the list is storing pointers, the allocated memory will be for the pointer, not the actual element's data.
149 149
150 The function `cxListInsertSorted()` inserts the element at the correct position so that the list remains sorted according to the list's compare function. 150 The function `cxListInsertSorted()` inserts the element at the correct position so that the list remains sorted according to the list's compare function.
151 On top of that, `cxListInsertUnique()` inserts the element only if it is not already in the list. 151 It is important that the list is already sorted before calling this function.
152 On the other hand, `cxListInsertUnique()` inserts the element only if it is not already in the list.
153 In this case it is strongly recommended that the list is already sorted but not required; the function will fall back to an inefficient algorithm when the list is not sorted.
152 154
153 When you are currently iterating through a list, you can insert elements before or after the current position of the iterator 155 When you are currently iterating through a list, you can insert elements before or after the current position of the iterator
154 with `cxListInsertBefore()` or `cxListInsertAfter()`, respectively. 156 with `cxListInsertBefore()` or `cxListInsertAfter()`, respectively.
155 This _should_ be done with [mutating iterators](iterator.h.md#mutating-iterators) only, but is also defined for normal iterators. 157 This _should_ be done with [mutating iterators](iterator.h.md#mutating-iterators) only, but is also defined for normal iterators.
156 158
158 Otherwise, the contents at the location pointed to by `elem` are copied to the list's memory with the element size specified during creation of the list. 160 Otherwise, the contents at the location pointed to by `elem` are copied to the list's memory with the element size specified during creation of the list.
159 161
160 On the other hand, the `array` argument for `cxListAddArray()`, `cxListInsertArray()`, `cxListInsertSortedArray()`, and `cxListInsertUniqueArray()` 162 On the other hand, the `array` argument for `cxListAddArray()`, `cxListInsertArray()`, `cxListInsertSortedArray()`, and `cxListInsertUniqueArray()`
161 must always point to an array of elements to be added (i.e., either an array of pointers or an array of actual elements). 163 must always point to an array of elements to be added (i.e., either an array of pointers or an array of actual elements).
162 164
163 When calling `cxListInsertSortedArray()` or `cxListInsertUniqueArray()`, the `array` must already be sorted.
164
165 The return values of the array-inserting functions are the number of elements that have been successfully _processed_. 165 The return values of the array-inserting functions are the number of elements that have been successfully _processed_.
166 Usually this is equivalent to the number of inserted elements, except for `cxListInsertUniqueArray()`, 166 Usually this is equivalent to the number of inserted elements, except for `cxListInsertUniqueArray()`,
167 where the actual number of inserted elements may be lower than the number of successfully processed elements. 167 where the actual number of inserted elements may be lower than the number of successfully processed elements.
168 168
169 > Implementations are required to optimize the insertion of a sorted array into a sorted list in linear time, 169 > Implementations are required to optimize the insertion of a sorted array into a sorted list in linear time,
170 > while inserting each element separately via `cxListInsertSorted()` may take quadratic time. 170 > while inserting each element separately via `cxListInsertSorted()` may take quadratic time.
171 171 >
172 > The functions do not check if the list is already sorted, nor do they actively sort the list. 172 > When used with sorted lists, the arrays passed to the functions must also be sorted according to the list's compare function.
173 > In debug builds, invoking the functions on unsorted lists may trigger an assertion. 173 > Only when `cxListInsertUniqueArray()` is used with a list that is not sorted, the array does not need to be sorted.
174 >
175 > The functions do not check if the passed arrays are sorted.
174 > {style="note"} 176 > {style="note"}
175 177
176 ## Access and Find 178 ## Access and Find
177 179
178 <link-summary>Functions for searching and accessing elements.</link-summary> 180 <link-summary>Functions for searching and accessing elements.</link-summary>

mercurial