Open Watcom STL
From Open Watcom
Contents |
Overview
Open Watcom STL (OWSTL) is a fresh implementation of the Standard Template Library (as described in the C++ 1998 and 2003 standards). 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.
Currently OWSTL is in an unfinished, immature state. Perhaps 50% of the STL is available, depending on how one measures it, and none of the code has yet been exercised extensively in the real world. It is our hope, of course, that both of these issues will get resolved in the coming months. 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 you will need to install or upgrade to v1.4 or later. Naturally we recommend that you use the latest version of Open Watcom possible. Note also that copying the OWSTL headers into an installation of a pre-v1.4 release is not likely to work. The current implementation of OWSTL depends on a number of namespace/template bug fixes that occured during the development of Open Watcom v1.4.
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
#ifdefblocks 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 algorith and are currently unimplemented. All other algorithms as specified by the 1998 standard should be present.
| missing feature | dependancy | plan of action |
|---|---|---|
| binary_search( Forward, Forward, const T& ) | ||
| binary_search( Forward, Forward, const T&, Compare ) | ||
| 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 ) | ||
| lexicographical_compare( Input1, Input1, Input2, Input2 ) | ||
| lexicographical_compare( Input1, Input1, Input2, Input2, 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 ) | ||
| next_permutation( Bidirectional, Bidirectional ) | ||
| next_permutation( Bidirectional, Bidirectional, 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 ) | ||
| prev_permutation( Bidirectional, Bidirectional ) | ||
| prev_permutation( Bidirectional, Bidirectional, Compare ) | ||
| rotate( Forward, Forward, Forward ) | ||
| rotate_copy( Forward, Forward, Forward, Output ) | ||
| search( Forward1, Forward1, Forward2, Forward2 ) | ||
| search( Forward1, Forward1, Forward2, Forward2, BinaryPredicate ) | ||
| search_n( Forward, Forward, Size, const T& ) | ||
| search_n( Forward, Forward, Size, const T&, BinaryPredicate ) | ||
| 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>
Not implemented. This header header is currently just a placeholder.
<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.
- Obtain user feedback on the STL components that currently exist. Actively maintain the existing components.
- 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.
- Write user level documentation to augment the current C++ Library Reference manual.
- Add extensions of interest to Open Watcom users (for example,
nearandfarallocators, etc). - Perform detailed performance evaluations and then optimize the implementation.
- Implement some sort of scope control facility in the preprocessor so that the simple local names used in OWSTL will be safe.
- Experiment with alternative implementation methods, perhaps allowing the user to select from the alternatives at compile time (or run time?).
- Add the new STL features as required by the upcoming revision of the C++ standard.
- Build a "debugging" version of OWSTL that includes additional run time (or compile time?) checks.
