OWSTL extensions
From Open Watcom
Introduction
The extentions to the standard c++ library provided by OWSTL are documented here. Information about TR1 libraries can be found here.
General
All OW containers have an additional bool _Sane() function that returns false if a check finds the internal data structures are corrupted.
slist
slist is a complete new header providing a single linked list container much like the standard list.
The SGI slist documentation was used for inspiration as well as the standard list.
Following are the methods provided. Also see the header itself for more information.
| member | description |
|---|---|
explicit slist( A const & a = A() )
| construct an empty slist |
explicit slist( size_type n )
| construct a list with n default constructed elements |
slist( size_type n, T const & t, A const & = A() )
| construct a list with n copies of t |
template< InputIt > slist( InputIt f, InputIt l )
| if InputIt is integral type slist( size_type(f), T(l) )
else build from range [f,l) |
slist( slist<T,A> const & )
| copy constructor |
~slist()
| destructor |
slist<T,A>& operator=( slist<T,A> const & )
| assign another slist to this one |
void assign( size_type n, T const & t)
| assign n copies of t |
template < InputIt > void assign( InputIt f, InputIt l )
| if InputIt is integral type assign( size_type(f), T(l) )
else assign range [f,l) |
allocator_type get_allocator() const
| return a copy of the allocator object |
iterator begin()
| return an iterator pointing to the first element in the list |
iterator end()
| return and iterator pointing to one past the last element of the list |
iterator previous( iterator i )
| special function for single linked list
return an iterator r such that ++r = i note it is slow becuase it must linearly search the list from begining to i |
bool empty() const
| is list empty? |
size_type size() const
| return number of objects in list |
max_size() const
| return the maximum number of object that could be held in the list, memory allowing |
void resize( size_type s, T t )
| trim list to s elements or extend it to s by adding copies of t |
void resize( size_type s )
| trim list to s elements or extend it to s by adding default constructed contained type |
reference front()
| return a reference to the first element in the list |
void pop_front()
| remove first element |
void push_front( T const & v )
| add v to front of list |
iterator insert( const_iterator i, T const & v )
| add v before i
slow because needs to do linear search from begining to find place to insert |
void insert( const_iterator i , size_type n, T const & v )
| add n copies of v before i
slow because needs to do linear search from begining to find place to insert |
template< InputIt > void insert( const_iterator it, InputIt f, InputIt l )
| if InputIt is integral type insert( it, size_type(f), T(l) )
else insert range [f,l) before it slow because needs to do linear search from begining to find place to insert |
iterator insert_after( const_iterator i, T const & v)
| insert v after i
fast (constant) time |
insert_after( const_iterator i, size_type n, T const & v);
| add n copies of v after i
fast, time proportional to n only |
template< InputIt > void insert_after( const_iterator it, InputIt f, InputIt l )
| if InputIt is integral type insert_after( it, size_type(f), T(l) )
else insert range [f,l) after it fast, time proportional to number or elements inserted only |
iterator erase( const_iterator i )
| erase element pointed to by i
slow because needs to do linear search from begining to find place to erase |
iterator erase( const_iterator f, const_iterator l )
| erase elements [f,l)
slow because needs to do linear search from begining to find place to erase |
iterator erase_after( const_iterator i )
| erase element ++i
fast(constant) time |
iterator erase_after( const_iterator f, const_iterator l )
| erase [++f, l)
fast, proportional to number of elements to errase |
void swap( slist<T,A>& that )
| swap contents of this and that
fast (constant) becuase just swaps internal pointers, doesn't actually copy objects |
clear()
| remove and free memory of all elements |
void splice( const_iterator i , slist& that )
| move entire contents of that before i |
void splice( const_iterator dst, slist& that, const_iterator src)
| splice node src (pointing to and element in that) before dst |
void splice_after( const_iterator dst, slist& that, const_iterator src )
| splice node ++src after dst
dst & src must be dereferenceable, ++src must be dereferenceable fast (constant) time |
splice_after( const_iterator dst, slist& that, const_iterator b4_first, const_iterator b4_last)
| splice nodes [++b4_first, ++b4_last) after dst
dst b4_first b4_last iterators must be dereferenceable bad things will happen if dst is in range[first, last ) fast (constant) time |
void remove( T const& t )
| remove all elements == t |
template< Predicate > remove( Predictate pred )
| remove element if pred(element) returns true |
void unique()
| remove all but the first element in consecutive group of operator== elements. |
template< Predicate > unique( Predictate pred )
| like unique but use pred(x,y) instead of operator== |
void merge( slist<T,A>& other )
| remove elements from other and place in operator< order into this
both must be sorted first |
template< Compare > void merge( slist<T,A>& other, Compare cmp )
| like merge but use cmp(x,y) for ordering instead of operator< |
void sort()
| sort elements with operator<
fast iterative natural merge sort (O(n) = nlog n worst, n best ) |
template< Compare > void sort( Compare cmp )
| like sort but use cmp(x,y) for ordering instead of operator< |
reverse()
| reverse order of elements |
| friend operators | perform lexicographical comparisons |
_Sane()
| OW special to check invarients of internal structures |
