Home > Store

Extended STL, Volume 1: Collections and Iterators

Register your product to gain access to bonus material or receive a coupon.

Extended STL, Volume 1: Collections and Iterators


  • Sorry, this book is no longer in print.
Not for Sale

eBook (Watermarked)

  • Your Price: $31.99
  • List Price: $39.99
  • About Watermarked eBooks
  • This PDF will be accessible from your Account page after purchase and requires PDF reading software, such as Acrobat® Reader®.

    The eBook requires no passwords or activation to read. We customize your eBook by discreetly watermarking it with your name, making it uniquely yours.

    Watermarked eBook FAQ


  • Copyright 2007
  • Edition: 1st
  • Book
  • ISBN-10: 0-321-30550-7
  • ISBN-13: 978-0-321-30550-3
  • eBook (Watermarked)
  • ISBN-10: 0-321-51445-9
  • ISBN-13: 978-0-321-51445-5

“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.

Sample Content

Online Sample Chapters

Extended STL: Filtered Iteration

Extended STL: The Fibonacci Sequence

Downloadable Sample Chapter

Download Chapter 23: The Fibonacci Sequence

Download Chapter 42: Filtered Iteration

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


Download the Preface


Download the Index


Submit Errata

More Information

InformIT Promotional Mailings & Special Offers

I would like to receive exclusive offers and hear about products from InformIT and its family of brands. I can unsubscribe at any time.


Pearson Education, Inc., 221 River Street, Hoboken, New Jersey 07030, (Pearson) presents this site to provide information about products and services that can be purchased through this site.

This privacy notice provides an overview of our commitment to privacy and describes how we collect, protect, use and share personal information collected through this site. Please note that other Pearson websites and online products and services have their own separate privacy policies.

Collection and Use of Information

To conduct business and deliver products and services, Pearson collects and uses personal information in several ways in connection with this site, including:

Questions and Inquiries

For inquiries and questions, we collect the inquiry or question, together with name, contact details (email address, phone number and mailing address) and any other additional information voluntarily submitted to us through a Contact Us form or an email. We use this information to address the inquiry and respond to the question.

Online Store

For orders and purchases placed through our online store on this site, we collect order details, name, institution name and address (if applicable), email address, phone number, shipping and billing addresses, credit/debit card information, shipping options and any instructions. We use this information to complete transactions, fulfill orders, communicate with individuals placing orders or visiting the online store, and for related purposes.


Pearson may offer opportunities to provide feedback or participate in surveys, including surveys evaluating Pearson products, services or sites. Participation is voluntary. Pearson collects information requested in the survey questions and uses the information to evaluate, support, maintain and improve products, services or sites, develop new products and services, conduct educational research and for other purposes specified in the survey.

Contests and Drawings

Occasionally, we may sponsor a contest or drawing. Participation is optional. Pearson collects name, contact information and other information specified on the entry form for the contest or drawing to conduct the contest or drawing. Pearson may collect additional personal information from the winners of a contest or drawing in order to award the prize and for tax reporting purposes, as required by law.


If you have elected to receive email newsletters or promotional mailings and special offers but want to unsubscribe, simply email information@informit.com.

Service Announcements

On rare occasions it is necessary to send out a strictly service related announcement. For instance, if our service is temporarily suspended for maintenance we might send users an email. Generally, users may not opt-out of these communications, though they can deactivate their account information. However, these communications are not promotional in nature.

Customer Service

We communicate with users on a regular basis to provide requested services and in regard to issues relating to their account we reply via email or phone in accordance with the users' wishes when a user submits their information through our Contact Us form.

Other Collection and Use of Information

Application and System Logs

Pearson automatically collects log data to help ensure the delivery, availability and security of this site. Log data may include technical information about how a user or visitor connected to this site, such as browser type, type of computer/device, operating system, internet service provider and IP address. We use this information for support purposes and to monitor the health of the site, identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents and appropriately scale computing resources.

Web Analytics

Pearson may use third party web trend analytical services, including Google Analytics, to collect visitor information, such as IP addresses, browser types, referring pages, pages visited and time spent on a particular site. While these analytical services collect and report information on an anonymous basis, they may use cookies to gather web trend information. The information gathered may enable Pearson (but not the third party web trend services) to link information with application and system log data. Pearson uses this information for system administration and to identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents, appropriately scale computing resources and otherwise support and deliver this site and its services.

Cookies and Related Technologies

This site uses cookies and similar technologies to personalize content, measure traffic patterns, control security, track use and access of information on this site, and provide interest-based messages and advertising. Users can manage and block the use of cookies through their browser. Disabling or blocking certain cookies may limit the functionality of this site.

Do Not Track

This site currently does not respond to Do Not Track signals.


Pearson uses appropriate physical, administrative and technical security measures to protect personal information from unauthorized access, use and disclosure.


This site is not directed to children under the age of 13.


Pearson may send or direct marketing communications to users, provided that

  • Pearson will not use personal information collected or processed as a K-12 school service provider for the purpose of directed or targeted advertising.
  • Such marketing is consistent with applicable law and Pearson's legal obligations.
  • Pearson will not knowingly direct or send marketing communications to an individual who has expressed a preference not to receive marketing.
  • Where required by applicable law, express or implied consent to marketing exists and has not been withdrawn.

Pearson may provide personal information to a third party service provider on a restricted basis to provide marketing solely on behalf of Pearson or an affiliate or customer for whom Pearson is a service provider. Marketing preferences may be changed at any time.

Correcting/Updating Personal Information

If a user's personally identifiable information changes (such as your postal address or email address), we provide a way to correct or update that user's personal data provided to us. This can be done on the Account page. If a user no longer desires our service and desires to delete his or her account, please contact us at customer-service@informit.com and we will process the deletion of a user's account.


Users can always make an informed choice as to whether they should proceed with certain services offered by InformIT. If you choose to remove yourself from our mailing list(s) simply visit the following page and uncheck any communication you no longer want to receive: www.informit.com/u.aspx.

Sale of Personal Information

Pearson does not rent or sell personal information in exchange for any payment of money.

While Pearson does not sell personal information, as defined in Nevada law, Nevada residents may email a request for no sale of their personal information to NevadaDesignatedRequest@pearson.com.

Supplemental Privacy Statement for California Residents

California residents should read our Supplemental privacy statement for California residents in conjunction with this Privacy Notice. The Supplemental privacy statement for California residents explains Pearson's commitment to comply with California law and applies to personal information of California residents collected in connection with this site and the Services.

Sharing and Disclosure

Pearson may disclose personal information, as follows:

  • As required by law.
  • With the consent of the individual (or their parent, if the individual is a minor)
  • In response to a subpoena, court order or legal process, to the extent permitted or required by law
  • To protect the security and safety of individuals, data, assets and systems, consistent with applicable law
  • In connection the sale, joint venture or other transfer of some or all of its company or assets, subject to the provisions of this Privacy Notice
  • To investigate or address actual or suspected fraud or other illegal activities
  • To exercise its legal rights, including enforcement of the Terms of Use for this site or another contract
  • To affiliated Pearson companies and other companies and organizations who perform work for Pearson and are obligated to protect the privacy of personal information consistent with this Privacy Notice
  • To a school, organization, company or government agency, where Pearson collects or processes the personal information in a school setting or on behalf of such organization, company or government agency.


This web site contains links to other sites. Please be aware that we are not responsible for the privacy practices of such other sites. We encourage our users to be aware when they leave our site and to read the privacy statements of each and every web site that collects Personal Information. This privacy statement applies solely to information collected by this web site.

Requests and Contact

Please contact us about this Privacy Notice or if you have any requests or questions relating to the privacy of your personal information.

Changes to this Privacy Notice

We may revise this Privacy Notice through an updated posting. We will identify the effective date of the revision in the posting. Often, updates are made to provide greater clarity or to comply with changes in regulatory requirements. If the updates involve material changes to the collection, protection, use or disclosure of Personal Information, Pearson will provide notice of the change through a conspicuous notice on this site or other appropriate way. Continued use of the site after the effective date of a posted revision evidences acceptance. Please contact us if you have questions or concerns about the Privacy Notice or any objection to any revisions.

Last Update: November 17, 2020