Open Watcom STL

From Open Watcom

Revision as of 23:35, 18 November 2012; view current revision
←Older revision | Newer revision→
Jump to: navigation, search

Contents

Overview

Open Watcom STL (OWSTL) is a fresh implementation of the Standard Template Library. It is not a port of any other STL implementation nor is it derived from any other implementation. OWSTL was created specifically for Open Watcom. It takes advantage of Open Watcom's unique features while specifically working around, if necessary, Open Watcom's limitations and bugs. See the Design Philosphy section below for more details about the design criteria and goals for OWSTL.

This page describes the portion of OWSTL that supports the 1998 and 2003 standards. Some functionality from the 2011 standard has also been implemented but it is described elsewhere.

Currently OWSTL is in an unfinished, immature state. Perhaps 50% of the STL is available, depending on how one measures it. We believe that with the community's help OWSTL can become a fully functional and high quaility implementation. If you use OWSTL and find problems with it, don't hesitate to report them either in the Open Watcom Bugzilla or in the Open Watcom newsgroups.

OWSTL is only available in Open Watcom v1.4 or later releases. Although a few STL features do exist in Open Watcom v1.3, STL support in v1.3 is very minimal. If you wish to experiment with OWSTL we recommend that you install the latest version of Open Watcom. Note that OWSTL evolves with the compiler so any particular version of OWSTL is unlikely to work with an earlier version of the compiler.

Design Philosophy

One might reasonably ask, "How is OWSTL different from other STL implementations?" In this section we attempt to answer that question by making explicit the design criteria and goals for the OWSTL project. The order of the items below is not significant.

Clarity of Presentation 
Writing clear code is, of course, always good. In the case of an open source template library, where essentially all of the code is in header files, clarity seems especially important. We want OWSTL to invite study, not only to help improve its quaility, but also to serve as an educational vehicle for novice C++ programmers. Templates that are easy to read also improves debugging in cases where you want to step into the library code. Several of the other criteria below are derived from the desire to make OWSTL as clear as possible.
Specific to Open Watcom 
OWSTL does not attempt to be usable with other compilers---including earlier versions of Open Watcom. It was developed for the current version of Open Watcom only. This simplifies the implementation considerably because it is not necessary to clutter the code with #ifdef blocks to selectively work around bugs and quirks in multiple compilation systems. This also allows OWSTL to take advantage of Open Watcom specific features and extensions in a straight forward way.
Conformance to the C++ Standard 
It is our priority to make OWSTL highly conformant to the standard.
Good Support for 16-bit Programming 
Since Open Watcom C/C++ supports several 16-bit targets, we want OWSTL to be useable with such targets. This means the library needs to behave in a reasonable way even when used in programs with significant memory constraints. This is particularly important for a template library where "code bloat" is sometimes a problem.

Status and Notes

The list below, organized by header file, gives more details about how much of the STL is currently available and what parts remain to be implemented. It also contains a few implementation notes that may be of interest to some users. Although incomplete, this list is intended to eventually be a reference for OWSTL users as well as a "to-do" list for potential contributors. Note that this list reflects the current development version of OWSTL. The last official release may have additional unimplemented components that have since been implemented.

None of the IOStreams header files are listed here. Open Watcom currently uses an "old-style" IOStreams library that has been moved into namespace std. One consequence of this is that I/O operators for STL components (notably std::string) have not yet been implemented. It is our intention to modernize the IOStreams library in a future release but we consider that project separate from OWSTL.

<algorithm>

The following algorithms, shown in alphabetical order, are missing from algorithm and are currently unimplemented. All other algorithms as specified by the 1998 standard should be present.

missing feature dependancy plan of action
equal_range( Forward, Forward, const T& )
equal_range( Forward, Forward, const T&, Compare )
includes( Input1, Input1, Input2, Input )
includes( Input1, Input1, Input2, Input2, Compare )
inplace_merge( Bidirectional, Bidirectional, Bidirectional )
inplace_merge( Bidirectional, Bidirectional, Bidirectional, Compare )
lower_bound( Forward, Forward, const T& )
lower_bound( Forward, Forward, const T&, Compare )
merge( Input1, Input1, Input2, Input2, Output result )
merge( Input1, Input1, Input2, Input2, Output result, Compare )
nth_element( RandomAccess, RandomAccess, RandomAccess )
nth_element( RandomAccess, RandomAccess, RandomAccess, Compare )
partial_sort( RandomAccess, RandomAccess, RandomAccess )
partial_sort( RandomAccess, RandomAccess, RandomAccess, Compare )
partial_sort_copy( Input, Input, RandomAccess, RandomAccess )
partial_sort_copy( Input, Input, RandomAccess, RandomAccess, Compare )
partition( Bidirectional, Bidirectional, Predicate )
rotate( Forward, Forward, Forward )
rotate_copy( Forward, Forward, Forward, Output )
set_difference( Input1, Input1, Input2, Input2, Output )
set_difference( Input1, Input1, Input2, Input2, Output, Compare )
set_intersection( Input1, Input1, Input2, Input2, Output )
set_intersection( Input1, Input1, Input2, Input2, Output, Compare )
set_symmetric_difference( Input1, Input1, Input2, Input2, Output )
set_symmetric_difference( Input1, Input1, Input2, Input2, Output, Compare )
set_union( Input1, Input1, Input2, Input2, Output )
set_union( Input1, Input1, Input2, Input2, Output, Compare )
stable_partition( Bidirectional, Bidirectional, Predicate )
stable_sort( RandomAccess, RandomAccess )
stable_sort( RandomAccess, RandomAccess, Compare )
upper_bound( Forward, Forward, const T& )
upper_bound( Forward, Forward, const T& , Compare )

The OWSTL implementation of unique does not follow the precise letter of the standard. This is common since the standard is defective in this regard. See "Unique effects unclear when predicate not an equivalence relation" in the WG21 library defects list. Open Watcom follows the proposed resolution in the defect report. For maximum portability avoid using unique with a non-equivalence relation.

The OWSTL implementation of sort uses a QuickSort with a median-of-three pivioting scheme. It is recursive and thus uses O(log(N)) stack space (in the average case).

<bitset>

Mostly complete.

<complex>

Mostly complete. No I/O operators for std::complex have been implemented but essentially all of the operations exist. This code needs to be reviewed by someone well versed in numerical methods.

<deque>

Partially complete. Enough functionality exists to be useful but many member functions are missing. Version 1.8 contains an updated implementaion that guarrentes references will not be invalidated when inserting at front and back, as required by the standard. Following is a table of missing methods.

missing feature dependancy plan of action
template ctor(InputIterator, InputIterator, const Allocator&)
operator=(const deque&)
template assign(InputIterator, InputIterator)
assign(size_type, const T& )
insert(iterator, const T&)
insert(iterator, size_type, const T&)
template insert (iterator, InputIterator, InputIterator)
erase(iterator, iterator)
swap(deque&)
clear()
all associated template function operators

<functional>

Complete.

<iterator>

Mostly complete. The only significant missing components are the stream iterators. These will be added once the new IOStreams library is sufficiently mature. The following table documents missing features.

missing feature dependancy plan of action
istream_iterator IOStreams
ostream_iterator IOStreams
istreambuf_iterator IOStreams
ostreambuf_iterator IOStreams

<limits>

Mostly complete. Support for numeric_limits on the floating point types is marginal and not complete. The current implementation of limits is based on the macros in the C header limits.h. Including limits will cause limits.h to also be included, bringing the macros it defines into view. This may not be desirable. However, this approach also means that corrections to limits.h are automatically applied to limits as well.

<list>

Partially complete. Enough functionality exists to be useful. The following table documents missing features.

missing feature dependancy plan of action
template <InputIterator> ctor - must explicitly pass allocator Member template default arguments Understand compiler more
size_type max_size() const
void resize(size_type, T = T())
const_reference front() const;
const_reference back() const;
template <class Predicate> void remove_if( Predicate )
void unique()
template <class BinaryPredicate> void unique( BinaryPredicate )
template <class Compare> void merge( list& , Compare )

<map>

Partially complete. Enough functionality exists to be useful. The following table documents missing features.

missing feature dependancy plan of action
template<InputIterator> ctor Member template default arguments Understand compiler more
reverse_iterator None Haven't gotten around to it yet
const_reverse_iterator
rend() and rend() const
rbegin() and rbegin() const
max_size()
erase( iterator first, iterator last )
swap
key_comp()
value_comp()
find( key_type ) const
count()
equal_range( key_type ) and equal_range( key_type ) const
non member operators and specialized swap algorithm


<memory>

Mostly complete. Note that (among other things) std::auto_ptr is not 100% compliant with the standard, although it should be close enough for some applications.

<numeric>

Complete.

<queue>

Complete.

<set>

Partially complete. Enough functionality exists to be useful.

<slist>

Non-standard extension to provide a single linked list container. More information here.

<stack>

Complete.

<string>

Mostly complete. Although there are no I/O operators, all other member functions and string operations are available. OWSTL's std::string implementation is not a copy-on-write implementation. The OWSTL developer's documentation (part of the source distribution) discuss the reasons for this in more detail.

String objects always have a capacity that is a power of two in size. When the capacity is increased (for example after a push_back that fills the current buffer) the size of the internal buffer is doubled. The smallest capacity used is eight.

OWSTL's std::string do not bother to null terminate their internal buffers. When c_str is called, a null character is appended to the buffer at that time. The internal buffer is resized when there is one space left so that at all times there will be space for a null character. The c_str member never causes a reallocation (and never throws an exception).

<utility>

Complete.

<valarray>

Not implemented. This header is currently just a placeholder.

<vector>

Partially complete. Enough functionality exists to be useful. Some member functions are known to not yet be exception safe.

Special Features

OWSTL contains a number of special features. In this section we highlight those features.

Case insensitive string comparisons

After doing #include <string> a special instantiation of std::basic_string named watcom::istring is available that does all comparisons in a case-insensitive manner. For example

#include <string>

void f( )
{
  watcom::istring s( "HELLO" );
  if( s == "hello" ) {
    // Matches "HELLO", "Hello", "HeLlO", etc.
  }
  watcom::istring::size_type result = find( s, "ell" );  // Returns 1.
}

Simple Local Names

OWSTL is written without the extensive use of underscore characters that one typically finds in STL implementations. For example, consider OWSTL's version of for_each

template< class InputIterator, class Function >
Function for_each( InputIterator first, InputIterator last, Function f )
{
  while( first != last ) {
    f( *first );
    ++first;
  }
  return( f );
}

This is to be contrasted with a more common style that looks like

template< class __InputIterator, class __Function >
__Function for_each( __InputIterator _first, __InputIterator _last, __Function _f )
{
  while( _first != _last ) {
    _f( *_first );
    ++_first;
  }
  return( _f );
}

We feel that the extensive use of underscores obscures the code and makes it difficult to read. Thus we avoid them.

The underscores are normally used to protect the names from accidental modification due to user defined macros. Since the preprocessor does not respect the usual C++ scope rules, such macros might conflict with the simple names used in the first example. To avoid this, other template libraries use implementation reserved names even for symbols that would otherwise be local.

We believe, however, that the correct way to protect template bodies from molestation by the preprocessor is to provide the preprocessor with some sort of scope control facility. This has not yet been done in Open Watcom partly because we are waiting to see if such a facility becomes part of the upcoming C++ standard. In the meantime we take advantage of the fact that OWSTL is new and immature and thus no existing Open Watcom users are relying on it (no legacy code to worry about). We provide simple local names for easy comprehension and will deal with preprocessor issues later as they arise.

Future Directions

In this section we provide a rough road map describing the anticipated future work on OWSTL. If you are interested in contributing to OWSTL you can consider this list as a "to do" list. The items below are approximately in descending order of priority.

  1. Obtain user feedback on the STL components that currently exist. Actively maintain the existing components.
  2. Finish OWSTL by providing the remaining functionality as required by the current (2003) C++ standard. This will also require updating the C++ compiler itself since it does not yet support all the necessary features for processing a fully standard STL.
  3. Write user level documentation to augment the current C++ Library Reference manual.
  4. Add extensions of interest to Open Watcom users (for example, near and far allocators, etc).
  5. Perform detailed performance evaluations and then optimize the implementation.
  6. Implement some sort of scope control facility in the preprocessor so that the simple local names used in OWSTL will be safe.
  7. Experiment with alternative implementation methods, perhaps allowing the user to select from the alternatives at compile time (or run time?).
  8. Add the new STL features as required by the upcoming revision of the C++ standard.
  9. Build a "debugging" version of OWSTL that includes additional run time (or compile time?) checks.
Personal tools