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> |