Elgrint::MList<T> class

Declared in MList.h


Linear ordered collection, similar to MVector, but with more flexible insert/remove.


Base class: Collection

Template parameters:

Name Description

The type of any element in MList. Must have a public copy constructor and a public destructor.


Name Description
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.


Name Description
MList(v) Conversion constructor. Converts MVector into MList in O(1) time complexity.


Name Description
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.


Name Description
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.

The reversed switch (from width list back to vector) occurs only when MList is emptied, or assigned to another list in a "vector mode" (using operator= or swapWith).

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.


Let us know

Please Contact us to report any errors on this page, or to suggest any improvements.

Miranor Home | About Miranor | About Elgrint | Create account | Login | Account settings | Contact Us | Privacy Policy | Site map

© Copyright 2014 by Miranor. All rights reserved. By using this site you agree to the Terms of Use.

Page last updated on August 10th, 2014.