Declared in MList.h
Base class: Collection
The type of any element in MList. Must have a public copy constructor and a public destructor.
|CIter||Constant iterator of MList.|
|Iter||Non-constant iterator of MList. Usage is identical to that of CIter, up to the differences listed in Collection::Iter.|
|MList(v)||Conversion constructor. Converts MVector into MList in O(1) time complexity.|
|append(x)||Appends x to the end of the list.|
|insert(pos,v)||Inserts all elements of v into the list, starting from index pos.|
|insert(pos,x)||Inserts x into the list, at position pos.|
|popBack()||Removes a single element from the end of the list.|
|remove(pos)||Removes a single element at position pos from the list.|
|remove(first,last)||Removes elements at indices between first and last (inclusive) from the list.|
|set(pos,newVal)||Changes the element at index pos to newVal.|
|setCnt(n,x)||Makes sure that the list contains exactly n elements.|
|get(pos)||Returns a copy of the list's element at position pos.|
MList is very similar to MVector. It supports both constant and non-constant iterators, and all the principal vector methods: append, popBack, set, get, and even setCnt. But in addition to this, MList supports insert and remove operations for any index in the list, whereas MVector only allows insert/remove at the end of the vector, for performance reasons.
By default, MList is just a wrapper around MVector, though it does work slightly slower than the real MVector due to some overhead. As long as the list is sufficiently small or the items are inserted and removed sufficiently near the end, MList remains a wrapper of MVector. If, however, items are inserted or removed far enough from the end to make MVector inefficient, MList is switched to a more advanced (albeit more complicated) MWidthList data structure, which supports the same operations with O(lgn) time complexity. The switch is automatic and transparent. However, if the list has been exceptionally large before the switch, there might be a small delay in operations, as the width list is being constructed.
Since by default MList is simply a wrapper of MVector, a vector can be converted to MList in O(1) time using MList(MVector<T>) constructor, provided, of course, that both vector and list have the same T type.
- The switch from vector mode to width list mode cannot occur if the list owns any iterators (constant or non-constant), because the switch would invalidate the iterators, breaking the transparency of the switch. Thus, it is important not to keep iterators around more than necessary or they can affect the performance of the list (more so than for other collections)
Let us know
Please Contact us to report any errors on this page, or to suggest any improvements.