Extended STL, Volume 1: Collections and Iterators

“Wilson’s menu of STL treatments will no doubt be good eating for generic programming adherents, ardent C programmers just now taking on STL and C++, Java programmers taking a second look at C++, and authors of libraries targeting multiple platforms and languages. Bon appetit!” --George Frazier, Cadence Design Systems, Inc. “A thorough treatment of the details and caveats of STL extension.” --Pablo Aguilar, C++ Software Engineer “This book is not just about extending STL, it’s also about extending my thinking in C++.” --Serge Krynine, C++ Software Engineer, RailCorp Australia “You might not agree 100% with everything Wilson has to say, but as a whole his book is the most valuable, in-depth study of practical STL-like programming.” --Thorsten Ottosen, M.C.S., Boost Contributor “Wilson is a master lion tamer, persuading multifarious third-party library beasts to jump through STL hoops. He carefully guides the reader through the design considerations, pointing out the pitfalls and making sure you don't get your head bitten off.” --Adi Shavit, Chief Software Architect, EyeTech Co. Ltd “Wilson’s book provides more than enough information to change the angst/uncertainty level of extending STL from ‘daunting’ to ‘doable.’ ” --Garth Lancaster, EDI/Automation Manager, Business Systems Group, MBF Australia “This book will open up your eyes and uncover just how powerful STL’s abstractions really are.” --Nevin “:-)” Liber, 19-year veteran of C++ “In the canon of C++ there are very few books that extend the craft. Wilson’s work consistently pushes the limits, showing what can and cannot be done, and the tradeoffs involved.” --John O’Halloran, Head of Software Development, Mediaproxy “Essential concepts and practices to take the working programmer beyond the standard library.” --Greg Peet “Extended STL is not just a book about adapting the STL to fit in with your everyday work, it’s also an odyssey through software design and concepts, C++ power techniques, and the perils of real-world software development--in other words, it’s a Matthew Wilson book. If you're serious about C++, I think you should read it.” --Björn Karlsson, Principle Architect, ReadSoft; author of Beyond the C++ Standard Library: An Introduction to Boost In Extended STL, renowned C++ expert Matthew Wilson shows how to go beyond the C++ standard and extend the Standard Template Library into the wider C++ world of APIs and non-standard collections, to write software that is more efficient, expressive, flexible, and robust. In Volume 1, Wilson’s innovative techniques help you master STL extension in two important areas: adapting technology-specific libraries and operating system APIs to STL-compliant collections, and defining sophisticated iterator adaptors with which the latent efficiency and expressive power of STL can be realized. Using real-world examples, Wilson illustrates several powerful concepts and techniques that enable you to extend STL in directions never envisioned by its creators, including collections, element reference categories, external iterator invalidation and inferred interface adaptation. Extended STL, Volume 1, will be an invaluable resource for every C++ programmer who is at least minimally familiar with the STL. Learn specific principles and techniques for STL extension Learn more about the STL by looking inside the implementation of STL extensions Learn general techniques for implementing wrappers over operating system APIs and technology-specific libraries Learn how to write iterator adaptors and understand the reasons behind the restrictions on their implementations and use Specific coverage includes Making the most of collections, and understanding how they differ from containers Mastering element reference categories: defining them, detecting them, and using them to design STL extension collections and iterators Working with external iterator invalidation, and understanding its surprising impact on the design of STL-compatible collections Adapting real-world APIs ranging from file system enumeration to scatter/gather I/O Using standalone iterator types, from simple std::ostream_iterator extensions to sophisticated adaptors that filter and transform types or values The accompanying CD-ROM contains an extensive collection of open-source libraries created by the author. Also included: several test projects, and three bonus chapters.

Table of Contents:
Preface    xvii Aims    xvii Subject Matter    xviii Structure    xix Supplementary Material    xx Acknowledgments    xxi Parachutes: Coda    xxii About the Author    xxiii Prologue    xxiv A Dichotomy of Character    xxiv Principles of UNIX Programming    xxv Seven Signs of Successful C++ Software Libraries    xxvi Balancing the Signs: Satisfiction, Dialecticism, and Idioms Old and New    xxxii Example Libraries    xxxiii Presentation Conventions    xxxvii Fonts    xxxvii . . . versus ...    xxxvii End Iterator Precomputation    xxxviii Nested Class Type Qualification    xxxix NULL    xxxix Template Parameter Names    xl Member and Namespace-Scope Type Names    xl Calling Conventions    xl Endpoint Iterators    xl Namespace for Standard C Names    xl Class Adaptors and Instance Adaptors    xl Header File Names    li PART ONE: Foundations    1 Chapter 1: The Standard Template Library    3 1.1     Core Concepts    3 1.2     Containers    4 1.3     Iterators    5 1.4     Algorithms    12 1.5     Function Objects    3 1.6     Allocators    13 Chapter 2: Extended STL Concepts, or When STL Meets the Real World    14 2.1     Terminology    142.2     Collections    152.3     Iterators    18 Chapter 3: Element Reference Categories    21 3.1     Introduction    21 3.2     C++ References    21 3.3     A Taxonomy of Element Reference Categories    23 3.4     Using Element Reference Categories    29 3.5     Defining operator ->()    31 3.6     Element Reference Categories: Coda    31 Chapter 4: The Curious Untemporary Reference    32 Chapter 5: The DRY SPOT Principle    34 5.1     DRY SPOTs in C++    4 5.2     Not Quite DRY SPOTs in C++     36 5.3     Closed Namespaces    38 Chapter 6: The Law of Leaky Abstractions    40 Chapter 7: Contract Programming    42 7.1     Enforcement Types    42 7.2     Enforcement Mechanisms    43 Chapter 8: Constraints    45 8.1     Type System Leverage    45 8.2     Static Assertions    46 Chapter 9: Shims    48 9.1     Introduction    48 9.2     Primary Shims    49 9.3     Composite Shims    52 Chapter 10: Duck and Goose, or the Whimsical Bases of Partial Structural Conformance    57 10.1    Conformance    57 10.2    Explicit Semantic Conformance    62 10.3    Intersecting Conformance    64 Chapter 11: RAII    65 11.1    Mutability    65 11.2    Resource Source    65 Chapter 12: Template Tools    67 12.1    Traits    67 12.2    Type Generators    75 12.3    True Typedefs    76 Chapter 13: Inferred Interface Adaptation: Compile-Time Adaptation of Interface-Incomplete Types    77 13.1    Introduction    77 13.2    Adapting Interface-Incomplete Types     78 13.3    Adapting Immutable Collections    79 13.4    Inferred Interface Adaptation    80 13.5    Applying IIA to the Range    85 Chapter 14: Henney's Hypothesis, or When Templates Attack!     87 Chapter 15: The Independent Autonomies of equal() Friends    89 15.1    Beware Nonmember Friend Function Abuse     89 15.2    Collections and Their Iterators    91 Chapter 16: Essential Components    93 16.1    Introduction    93 16.2    auto_buffer    93 16.3    filesystem_traits    97 16.4    file_path_buffer    103 16.5    scoped_handle    107 16.6    dl_call()    109 PART TWO: Collections    111 Chapter 17: Adapting the glob API    115 17.1    Introduction    115 17.2    Decomposition of the Longhand Version     119 17.3    unixstl::glob_sequence    121 17.4    Decomposition of the Shorthand Version     135 17.5    Summary    135 Chapter 18: Intermezzo: Constructor Clashes and Design That Is, If Not Bad, At Least Ill-Conceived for Seamless Evolution    137 Chapter 19: Adapting the opendir/readdir API    140 19.1    Introduction    140 19.2    Decomposition of the Longhand Version    142v19.3    unixstl::readdir_sequence    144 19.4    Alternate Implementations    61 19.5    Summary    162 Chapter 20: Adapting the FindFirstFile/FindNextFile API    164 20.1    Introduction    164 20.2    Decomposition of Examples    169 20.3    Sequence Design    171 20.4    winstl::basic_findfile_sequence    172 20.5    winstl::basic_findfile_sequence_const_iterator    178 20.6    winstl::basic_findfile_sequence_value_type    191 20.7    Shims 193 20.8    What, No Shims and Constructor Templates?     94 20.9    Summary 194 20.10  File System Enumeration with recls: Coda    195 Chapter 21: Intermezzo: When the Efficiency/Usability Balance Is Tipped: Enumerating FTP Server Directories    196 21.1    inetstl::basic_findfile_sequence    197 21.2    inetstl::basic_ftpdir_sequence    199 Chapter 22: Enumerating Processes and Modules    201 22.1    Collection Characteristics    202 22.2    winstl::pid_sequence    202 22.3    winstl::process_module_sequence    206 22.4    Enumerating All Modules on a System    206 22.5    Avoiding the System Pseudo Processes    208 22.6    Handling Optional API Headers    210 22.7    Summary    211 Chapter 23: The Fibonacci Sequence    212 23.1    Introduction    212 23.2    The Fibonacci Sequence    12 23.3    Fibonacci as an STL Sequence    212 23.4    Discoverability Failure    218 23.5    Defining Finite Bounds    218 23.6    Summary 225 Chapter 24: Adapting MFC's CArray Container Family    227 24.1    Introduction    227 24.2    Motivation    227 24.3    Emulating std::vector    230 24.4    Design Considerations    232 24.5    mfcstl::CArray_adaptor_base Interface    237 24.6    mfcstl::CArray_cadaptor    239 24.7    mfcstl::CArray_iadaptor    244 24.8    Construction    245 24.9    Allocator    245 24.10  Element Access Methods    246 24.11  Iteration    246 24.12  Size    248 24.13  Capacity    252 24.14  Comparison    253 24.15  Modifiers    256 24.16  Assignment and swap()    261 24.17  Summary    264 24.18  On the CD    265 Chapter 25: A Map of the Environment    266 25.1    Introduction    266 25.2    Motivation    266 25.3    getenv(), putenv(), setenv()/unsetenv(), and environ    267 25.4    platformstl::environment_variable_traits    268 25.5    Planning the Interface    271 25.6    Lookup by Name    271 25.7    Inserting, Updating, and Deleting Values by Name    277 25.8    Iteration    278 25.9    Final Iteration Implementation    286 25.10  Heterogeneous Reference Categories?    297 25.11  size() and Subscript by Index    297 25.12  Summary    298 25.13  On the CD    298 Chapter 26: Traveling Back and Forth on the Z-Plane    299 26.1    Prologue    299 26.2    Introduction    299 26.3    Version 1: Forward Iteration    302 26.4    Version 2: Bidirectional Iteration    304 26.5    Handling External Change    306 26.6    winstl::child_window_sequence    309 26.7    Bidirectional Iterator Blues    309 26.8    winstl::zorder_iterator: A Reversal of Self    315 26.9    Finalizing the Window Peer Sequences    321 26.10  Summary    323 26.11  Z-Plane: Coda    323 Chapter 27: String Tokenization    324 27.1    Introduction    324 27.2    strtok()    325 27.3    SynesisSTL::StringTokeniser     327 27.4    Tokenization Use Cases    329 27.5    Other Tokenization Alternatives    330 27.6    stlsoft::string_tokeniser    331 27.7    Test Drive    340 27.8    The Policy Folly    345 27.9    Performance    348 27.10  Summary    352 Chapter 28: Adapting COM Enumerators    353 28.1    Introduction    353 28.2    Motivation    353 28.3    COM Enumerators    355 28.4    Decomposition of the Longhand Version    358 28.5    comstl::enumerator_sequence    359 28.6    comstl::enumerator_sequence::iterator    368 28.7    comstl::enumerator_sequence::iterator::enumeration_context    372 28.8    Iterator Cloning Policies    381 28.9    Choosing a Default Cloning Policy: Applying the Principle of Least Surprise     385 28.10  Summary    390 28.11  Coming Next    391 Chapter 29: Intermezzo: Correcting Minor Design Omissions with Member Type Inference    392 Chapter 30: Adapting COM Collections    394 30.1    Introduction    394 30.2    Motivation    394 30.3    comstl::collection_sequence    398 30.4    Enumerator Acquisition Policies    403 30.5    Summary    406 Chapter 31: Gathering Scattered I/O    407 31.1    Introduction    407 31.2    Scatter/Gather I/O    407 31.3    Scatter/Gather I/O APIs    409 31.4    Adapting ACE_Message_Queue    414 31.5    Time for Some Cake    420 31.6    Summary    427 Chapter 32: Argument-Dependent Return-Type Variance    428 32.1    Introduction    428 32.2    Borrowing a Jewel from Ruby    428 32.3    Dual-Semantic Subscripting in C++    430 32.4    Generalized Compatibility via String Access Shims    431 32.5    A Fly in the int-ment    432 32.6    Selecting Return Type and Overload    433 32.7    Summary    434 Chapter 33: External Iterator Invalidation    435 33.1    Element-Interface Coherence    435 33.2    Windows ListBox and ComboBox Controls    437 33.3    Enumerating Registry Keys and Values    444 33.4    Summary    463 33.5    On the CD    463 PART THREE: Iterators    465 Chapter 34: An Enhanced ostream_iterator    467 34.1    Introduction    467 34.2    std::ostream_iterator    469 34.3    stlsoft::ostream_iterator    470 34.4    Defining Stream Insertion Operators    475 34.5    Summary    476 Chapter 35: Intermezzo: Proscribing Fatuous Output Iterator Syntax Using the Dereference Proxy Pattern    477 35.1    stlsoft::ostream_iterator::deref_proxy    478 Chapter 36: Transform Iterator    481 36.1    Introduction    481 36.2    Motivation    482 36.3    Defining Iterator Adaptors     485 36.4    stlsoft::transform_iterator     487 36.5    Composite Transformations     496 36.6    DRY SPOT Violations?     497 36.7    A Spoonful of Sequence Helps the Medicine . . . ?     501 36.8    Summary     501 36.9    On the CD     502 Chapter 37: Intermezzo: Discretion Being the Better Part of Nomenclature . . .     503 Chapter 38: Member Selector Iterator     506 38.1    Introduction     506 38.2    Motivation     506 38.3    stlsoft::member_selector_iterator     509 38.4    Creator Function Woes     511 38.5    Summary     518 38.6    On the CD     518 Chapter 39: C-Style String Concatenation     519 39.1    Motivation     519 39.2    An Inflexible Version     520 39.3    stlsoft::cstring_concatenator_iterator     522 39.4    Creator Functions     524 39.5    Summary     525 39.6    On the CD     526 Chapter 40: String Object Concatenation     527 40.1    Introduction     527 40.2    stlsoft::string_concatenator_iterator     527 40.3    Heterogeneity of String Types     530 40.4    But . . .     530 40.5    Summary     532 Chapter 41: Adapted Iterators Traits     533 41.1    Introduction     533 41.2    stlsoft::adapted_iterator_traits     533 41.3    Summary     540 41.4    On the CD     541 Chapter 42: Filtered Iteration     542 42.1    Introduction     542 42.2    An Invalid Version     542 42.3    Member Iterators Define the Range     543 42.4    So . . . ?     544 42.5    stlsoft::filter_iterator     545 42.6    Constraining the Iterator Category     549 42.7    Summary     550 42.8    On the CD     550 Chapter 43: Composite Iterator Adaptations     551 43.1    Introduction     551 43.2    Transforming a Filtered Iterator     551 43.3    Filtering a Transformed Iterator     553 43.4    Hedging Our Bets     554 43.5    Summary     554 Epilogue     555 Bibliography     556 Index     559

About the Author :
Matthew Wilson is a software development consultant for Synesis Software and creator of the STLSoft and Pantheios libraries. He is author of Imperfect C++ (Addison-Wesley), a former columnist for C/C++ Users Journal, and a contributor to several leading publications. He has more than fifteen years' C++ experience. Based in Australia, he holds a Ph.D. from Manchester University (UK).