OWSTL extensions

From Open Watcom

Revision as of 02:16, 11 January 2009; view current revision
←Older revision | Newer revision→
Jump to: navigation, search

Introduction

The extentions to the standard c++ library provided by OWSTL are documented here. Information about the C++0x 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()

const_iterator begin() const const_iterator cbegin() const

return an iterator pointing to the first element in the list
iterator end()

const_iterator end() const const_iterator cend() const

return and iterator pointing to one past the last element of the list
iterator previous( iterator i )

const_iterator previous( const_iterator i ) const

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

const_reference front() const

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