Semantics Consulting, Inc.

flist<T, Alloc>

Category: containers Component type: type

Description

flist is an STL-compliant container that uses two-way pointers to implement a doubly-linked list that can change its mind as to which way it's organized.  Its iterators are similarly confused, and this makes for some interesting complexity results.

flist has all the same members as std::list.  flist has half the storage overhead of list while providing similar performance (except for reversing, which is contant time for flist).

flist has the same storage overhead and similar performance to (typical, non-standard) slist (except for insert, erase, and reverse, where flist provides constant time, rather than linear performance) but provides bidirectional rather than forward iterators.  For parity (but not compatibility) with slist, flist also provides the slist insert_after, erase_after, splice_after, and previous members.

The major difference between flist and list or slist is that flist is not a "node-based" container (even though it's implemented with nodes) because insertion, deletion, swapping, splicing, or assigning can invalidate iterators adjacent to the nodes directly affected by the operation.  Note, however, that pointers and references to adjacent nodes are not affected by these operations.  Due to iterator invalidation during splicing, flist's splice_before and splice_after operations return an flist::splice_return_type which contains three iterators: two give the spliced subrange in the target list, and the third gives the end iterator from the source list.  splice_return_type is a std::pair, the first element of which is a std::pair:
    typedef std::pair<std::pair<iterator,iterator>,iterator> splice_return_type;
Because a (typically) 24-byte return may be too bulky for some applications, the usual splice members have the usual void return.

flist's "fickle" iterators are unusual in that they can easily change their minds about about which way they're traversing (that's what makes them fickle).  Note that flist also provides reverse_iterators, but they differ from fickle iterators, since reverse_iterators are always reversed.  Direction of iteration in an flist is relative anyway, since an flist can reverse itself in constant time. Many algorithms can be efficiently rendered by reversing an flist and its iterators at will; reversing an flist or flist iterator has about the same cost as incrementing an iterator.  Changing direction with a fickle iterator is faster and simpler than the corresponding code written with reverse_iterators, because ++ may be marginally faster than -- for flist, and there is no irritating base() offset for fickle iterators as there is for a reverse_iterator; that is, when you reverse an flist iterator, it still refers to the same list element, it's just that the effects of ++ and -- are reversed.  (If the above discussion irritates you, just avoid the reverse functions, and use an flist as a lightweight list.)

An early version is described in CUJ 20(6), June 2002:  "Running Circles Round You, Logically."  A prepublication version of the article is available at <http://www.semantics.org/publications/02_06_logicalcircles.pdf>.

Definition

Defined in the non-standard header flist.h.

Examples

An implementation of flist::resize that uses fickle iterators:
template <typename T, class A>
void flist<T,A>::resize( size_type n, const value_type &v ) {
size_type s( size() );
if( s < n ) {
flist temp( n-s, v );
splice( end(), temp );
}
else if( s > n ) {
iterator e( end() );
e.reverse();
std::advance( e, s-n );
e.reverse();
erase( e, end() );
}
}

An implementation of flist::merge that uses two different forms of splice:
template <typename T, class A>
template <typename Comp>
void flist<T,A>::merge( flist &that, Comp comp ) {
   if( this == &that )
        return;
    iterator first1 = begin();
    iterator first2 = that.begin();
    while( first1 != end() && first2 != that.end() ) {
        if( comp( *first2, *first1 ) ) {
            iterator i = first2;
            while( ++i != that.end() && comp( *i, *first1 ) ) {}
            splice_return_type r = splice_before( first1, that, first2, i );
            first1 = r.first.second;
            first2 = r.second;
        }
        else
            ++first1;
    }
    if( first2 != that.end() )
        splice( end(), that, first2, that.end() );
}

An implementation of flist::remove_if that is wary of invalidated iterators.  In addition to the usual care taken with invalidation on erase, note that the end() value is not cached:
template <typename T, class A>
template <typename Pred>
void flist<T,A>::remove_if( Pred pred ) {
    iterator first = begin();
    while( first != end() ) {
        if( pred( *first ) )
            first = erase( first );
        else
            ++first;
    }
}

Template parameters

Parameter Description Default
T The flist's value type: the type of object that is stored in the flist.  
Alloc The flist's allocator, used for all internal memory management. std::allocator

Model of

Reversible Container, Front Insertion Sequence, Back Insertion Sequence.

Type requirements

None, except for those imposed by the requirements of Reversible Container, Front Insertion Sequence, and Back Insertion Sequence.

Public base classes

None that you should care about.
For implementation purposes a particular implementation of flist may use public derivation, but these base classes (if any) are never to be considered or used as polymorphic base classes.

Common Members

Member Where defined Description
value_type Container The type of object, T, stored in the list.
pointer Container Pointer to T.
reference Container Reference to T
const_reference Container Const reference to T
size_type Container An unsigned integral type.
difference_type Container A signed integral type.
iterator Container Iterator used to iterate through an flist.
const_iterator Container Const iterator used to iterate through an flist.
reverse_iterator Reversible Container Iterator used to iterate backwards through an flist.
const_reverse_iterator Reversible Container Const iterator used to iterate backwards through an flist.
iterator begin() Container Returns an iterator pointing to the beginning of the flist.
iterator end() Container Returns an iterator pointing to the end of the flist.
const_iterator begin() const Container Returns a const_iterator pointing to the beginning of the flist.
const_iterator end() const Container Returns a const_iterator pointing to the end of the flist.
reverse_iterator rbegin() Reversible Container Returns a reverse_iterator pointing to the beginning of the reversed flist.
reverse_iterator rend() Reversible Container Returns a reverse_iterator pointing to the end of the reversed flist.
const_reverse_iterator rbegin() const Reversible Container Returns a const_reverse_iterator pointing to the beginning of the reversed flist.
const_reverse_iterator rend() const Reversible Container Returns a const_reverse_iterator pointing to the end of the reversed flist.
size_type size() const Container Returns the size of the flist. Note: you should not assume that this function is constant time. It is permitted to be O(N), where N is the number of elements in the flist. If you wish to test whether an flist is empty, you should write L.empty() rather than L.size() == 0.
size_type max_size() const Container Returns the largest possible size of the flist.
bool empty() const Container true if the flist's size is 0.
flist() Container Creates an empty flist.
flist(size_type n) Sequence Creates an flist with n elements, each of which is a copy of T().
flist(size_type n, const T& t) Sequence Creates an flist with n copies of t.
flist(const flist&) Container The copy constructor.
template <class InputIterator>
flist(InputIterator f, InputIterator l)
Sequence Creates an flist with a copy of a range.
~flist() Container The destructor.
flist& operator=(const flist&) Container The assignment operator.
reference front() Front Insertion Sequence Returns the first element.
const_reference front() const Front Insertion Sequence Returns the first element.
reference back() Sequence Returns the last element.
const_reference back() const Back Insertion Sequence Returns the last element.
void push_front(const T&) Front Insertion Sequence Inserts a new element at the beginning.  Invalidates iterators that std::list does not (see below).
void push_back(const T&) Back Insertion Sequence Inserts a new element at the end.  Invalidates iterators that std::list does not (see below).
void pop_front() Front Insertion Sequence Removes the first element.  Invalidates iterators that std::list does not (see below).
void pop_back() Back Insertion Sequence Removes the last element. Invalidates iterators that std::list does not (see below).
void swap(flist&) Container Swaps the contents of two flists.  Invalidates iterators that std::list does not (see below).
iterator insert(iterator pos,
                const T& x)
Sequence Inserts x before pos.  Invalidates iterators that std::list does not (see below).
template <class InputIterator>
void insert(iterator pos,
InputIterator f,
InputIterator l)
Sequence Inserts the range [f, l) before pos.  Invalidates iterators that std::list does not (see below).
void insert(iterator pos, 
size_type n, const T& x)
Sequence Inserts n copies of x before pos.  Invalidates iterators that std::list does not (see below).
iterator erase(iterator pos) Sequence Erases the element at position pos.  Invalidates iterators that std::list does not (see below).
iterator erase(iterator first,
               iterator last)
Sequence Erases the range [first, last)  Invalidates iterators that std::list does not (see below).
void clear() Sequence Erases all of the elements.
void resize(n, t = T()) Sequence Inserts or erases elements at the end such that the size becomes n.  Invalidates iterators that std::list does not (see below).
bool operator==(const flist&)
Forward Container Tests two flists for equality.  Note that this may be a member or non-member.  This implementation defines == as a member, and provides an implementation of !=.
bool operator<(const flist&)
Forward Container Lexicographical comparison of two flists.  Note that this may be a member or non-member.  This implementation defines < as a member, and also provides the other relational operators.

Members Also Present in std::list

Function Description
void splice(iterator position, 
flist& x);
position must be a valid iterator in *this, and x must be an flist that is distinct from *this. (That is, it is required that &x != this.) All of the elements of x are inserted before position and removed from x. Invalidates iterators that std::list does not (see below).  This function is constant time.
 
void splice(iterator position,
flist& x,
iterator i);
position must be a valid iterator in *this, and i must be a dereferenceable iterator in x. Splice moves the element pointed to by i from x to *this, inserting it before position. Invalidates iterators that std::list does not (see below).  If position == i or position == ++i, this function is a null operation. This function is constant time.
 
void splice(iterator position,
flist& x,
iterator f, iterator l);
position must be a valid iterator in *this, and [first, last) must be a valid range in x. position may not be an iterator in the range [first, last). Splice moves the elements in [first, last) from x to *this, inserting them before position. Invalidates iterators that std::list does not (see below).  This function is constant time.
void remove(const T& val); Removes all elements that compare equal to val. The relative order of elements that are not removed is unchanged. Invalidates iterators that std::list does not (see below).. This function is linear time: it performs exactly size() comparisons for equality.
template<class Predicate> 
void remove_if(Predicate p);
Removes all elements *i such that p(*i) is true. The relative order of elements that are not removed is unchanged.  Invalidates iterators that std::list does not (see below). This function is linear time: it performs exactly size() applications of p.
void unique(); Removes all but the first element in every consecutive group of equal elements. The relative order of elements that are not removed is unchanged.  Invalidates iterators that std::list does not (see below). This function is linear time: it performs exactly size() - 1 comparisons for equality.
template<class BinaryPredicate>
void unique(BinaryPredicate p);
Removes all but the first element in every consecutive group of equivalent elements, where two elements *i and *j are considered equivalent if p(*i, *j) is true. The relative order of elements that are not removed is unchanged.  Invalidates iterators that std::list does not (see below). This function is linear time: it performs exactly size() - 1 comparisons for equality.
void merge(flist& x); Both *this and x must be sorted according to operator<, and they must be distinct. (That is, it is required that &x != this.) This function removes all of x's elements and inserts them in order into *this. The merge is stable; that is, if an element from *this is equivalent to one from x, then the element from *this will precede the one from x. Invalidates iterators that std::list does not (see below). This function is linear time: it performs at most size() + x.size() - 1 comparisons.
template<class BinaryPredicate>
void merge(flist& x,
BinaryPredicate Comp);
Comp must be a comparison function that induces a strict weak ordering (as defined in the LessThan Comparable requirements) on objects of type T, and both *this and x must be sorted according to that ordering. The lists x and *this must be distinct. (That is, it is required that &x != this.) This function removes all of x's elements and inserts them in order into *this. The merge is stable; that is, if an element from *this is equivalent to one from x, then the element from *this will precede the one from x. Invalidates iterators that std::list does not (see below). This function is linear time: it performs at most size() + x.size() - 1 applications of Comp.
void reverse(); Reverses the order of elements in the flist. Iterators are not invalidated (but see below under iterators).  This function is constant time.
void sort(); Sorts *this according to operator<. The sort is stable, that is, the relative order of equivalent elements is preserved. Invalidates iterators that std::list does not (see below).  The number of comparisons is approximately N log N, where N is the flist's size.
template<class BinaryPredicate>
void sort(BinaryPredicate comp);
Comp must be a comparison function that induces a strict weak ordering (as defined in the LessThan Comparable requirements on objects of type T. This function sorts the list *this according to Comp. The sort is stable, that is, the relative order of equivalent elements is preserved. Invalidates iterators that std::list does not (see below).  The number of comparisons is approximately N log N, where N is the flist's size.

Members Also Present in (Non-Standard) slist

These members are included in flist for parity (but not compatibility) with slist.  The reasoning is that flist may prove to be a reasonable alternative to slist in many situations, and code developed for slist with its "_after" functions may be easily ported to an flist-based implementation.
Function Description
iterator previous(iterator pos) pos must be a valid iterator in *this. The return value is an iterator prev such that ++prev == pos. Complexity: linear in the number of iterators in the range [begin(), pos).
const_iterator previous(const_iterator pos) pos must be a valid iterator in *this. The return value is an iterator prev such that ++prev == pos. Complexity: linear in the number of iterators in the range [begin(), pos).
iterator insert_after(iterator pos) pos must be a dereferenceable iterator in *this. (That is, pos may not be end().) Inserts a copy of T() immediately following pos. The return value is an iterator that points to the new element. Complexity: constant time.  Invalidates iterators that slist does not (see below).
iterator insert_after(iterator pos,
const value_type& x)
pos must be a dereferenceable iterator in *this. (That is, pos may not be end().) Inserts a copy of x immediately following pos. The return value is an iterator that points to the new element. Complexity: constant time.  Invalidates iterators that slist does not (see below).
template<class InputIterator>
void insert_after(iterator pos,
InputIterator f, InputIterator l)
Inserts elements from the range [f, l) immediately following pos. Complexity: linear in last - first.  Invalidates iterators that slist does not (see below).
void insert_after(iterator pos, 
size_type n, const value_type& x)
Inserts n copies of x immediately following pos. Complexity: linear in n.  Invalidates iterators that slist does not (see below).
iterator erase_after(iterator pos) Erases the element pointed to by the iterator following pos. If pos is end(), begin() is erased.  pos may not refer to the element preceding end().  Complexity: constant time.  The return value is a new iterator that refers to the element pos referred to before the erase (since pos may be invalid).  Invalidates iterators that slist does not (see below).
iterator erase_after(iterator before_first,
                     iterator last)
Erases all elements in the range [before_first + 1, last). Complexity: linear in last - (before_first + 1).  The return value is a new iterator that refers to the element pos referred to before the erase (since pos may be invalid).  Invalidates iterators that slist does not (see below).
splice_return_type splice_after(iterator pos,
                    flist &x )
pos must be a valid iterator in *this, or pos must be equal to end().  If pos == end(), the splice will take place before begin()x must be an flist that is distinct from *this. (That is, it is required that &x != this.)  All of the elements of x are inserted after pos and removed from x.   Invalidates iterators that slist does not (see below).  This function is constant time.  Note that the signature and return type of this splice_after differ from that of slist::splice_after.
splice_return_type splice_after(iterator pos,
                    flist &x,
                    iterator prev)
pos must be a valid iterator in *this, or pos must be equal to end().  If pos == end(), the splice will take place before begin()x must be an flist that is distinct from *this. (That is, it is required that &x != this.)  Moves the element following prev to *this, inserting it immediately after pos.    Invalidates iterators that slist does not (see below).  This function is constant time.  Note that the signature and return type of this splice_after differ from that of slist::splice_after.
splice_return_type splice_after(iterator pos,
flist &x,
iterator before_first,
iterator before_last)
pos must be a valid iterator in *this, or pos must be equal to end().  If pos == end(), the splice will take place before begin()x must be an flist that is distinct from *this. (That is, it is required that &x != this.)  Moves the elements in the range [before_first + 1, before_last + 1) to *this, inserting them immediately after pos.    Invalidates iterators that slist does not (see below).  This function is constant time.  Note that the signature and return type of this splice_after differ from that of slist::splice_after.

New Members Present In Neither std::list Nor slist

Function Description
splice_return_type splice_before(iterator position, 
flist& x);
Behaves like the corresponding splice member, but returns splice_return_type rather than void.
 
splice_return_type splice_before(iterator position,
flist& x,
iterator i);
Behaves like the corresponding splice member, but returns splice_return_type rather than void.
 
splice_return_type splice_before(iterator position,
flist& x,
iterator f, iterator l);
Behaves like the corresponding splice member, but returns splice_return_type rather than void.

Notes on flist Iterators and Iterator Invalidation

flist iterators are fickle because they can easily change direction through use of their reverse member function.

Iterator comparison does not take into account the iterator's current direction of movement; if two iterators refer to the same list element (or are both equal to end()) they compare equal.

A reverse_iterator is not an iterator and does not support the reverse function.  Of course, it's possible generate a reverse_iterator from a reversed iterator.

Reversing an flist does not invalidate iterators, but the iterators will continue to move in the direction they did before the reversal.  From the flist's point of view, all iterators have been reversed.  From the iterators' point of view, nothing has changed.

Low-level note on invalidation:  An flist iterator is implemented with two pointers.  As with the typical implementation of std::list and slist iterators, one pointer points to the list node to which the iterator refers.  Unlike the typical implementations of std::list and slist, an flist iterator also has a pointer to the node preceding the node to which it refers.  This iterator structure allows flist to encode two node addresses within a single pointer.

The advantage (in addition to constant time reversals and fickle iterators) is that an flist has the same functionality and performance as std::list, but requires half the memory overhead, and flist has the same memory overhead and performance as slist, but provides bidirectional iterators.

The disadvantage is that this iterator structure means that flist is not a "node-based container."  That is, insertion or deletion of an flist element may affect iterators to other elements.  To be precise, since an flist iterator has a pointer to the previous as well as the current list node, a deletion  will affect not only iterators to  the erased element(s), but also iterators to the preceding and following elements, and an insertion will affect iterators to existing elements both preceding and following the inserted element(s).

However, note that flist is node-based with respect to pointers and references to elements; as with std::list and slist, pointers and references to adjacent elements are unaffected by insertions, deletions, swapping, sorting, merging, etc.

iterator Function Description
iterator reverse() The iterator will still refer to the same flist element as before, but the effect of ++ and -- will be reversed.  The return value is a copy of the (now reversed) *this.  This is a constant time operation.
const_iterator reverse() const The iterator will still refer to the same flist element as before, but the effect of ++ and -- will be reversed.  The return value is a copy of the (now reversed) *this.  This is a constant time operation.



Copyright (c) 2006 by Stephen C. Dewhurst and/or Semantics Consulting, Inc
http://www.semantics.org