Extended STL, Volume 1: Collections and Iterators [Paperback]

Matthew Wilson (Author)

Book Description

Publication Date: June 29, 2007 | ISBN-10: 0321305507 | ISBN-13: 978-0321305503

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

Editorial Reviews

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

Excerpt. © Reprinted by permission. All rights reserved.

My Uncle John is what my parents' generation would call "a man's man." He's tough, rugged, a bit scary, with more than a little of the cowboy in him, and he would admit to fear about as readily as I could render modest defeat. So when he described to me that the challenge in doing your second parachute jump is overcoming the fear of the known, I took note. Having now written two books, I can certainly attest to this same fear. Starting a second when you know how much suffering awaits is not something done lightly. So the question arises, why have I done so?

The reason, elucidated in the Prologue, amounts to an attempt to answer the following seemingly simple dichotomy.

• C++ is too complex.
• C++ is the only language sufficiently powerful for my needs.

One area in which this dichotomy is most pronounced is in using and, particularly, in extending the Standard Template Library (STL). This book (and its sibling, Volume 2), distills the knowledge and experience I have accumulated in tackling this challenging subject over the last decade or so.

Aims

This book describes one good way to use and extend the STL. It defines the following:

• The collection concept and how it differs from the container concept
• The element reference category concept, including why it's important, how it's defined, how it's detected, and the compromises it imposes on the design of STL extension collections and iterators
• The phenomenon of external iterator invalidation and the implications of its surprising behavior on the design of STL-compatible collections
• A mechanism for detecting features of arbitrary collections that may or may not provide mutating operations

It explains several issues:

• Why a transforming iterator adaptor must return elements by value
• Why a filtering iterator must always be given a pair of iterators to manipulate
• What to do if the underlying collection changes during iteration
• Why you should proscribe meaningless syntax for your output iterator classes and how to do so using the Dereference Proxy pattern
• Adapt elements-en-bloc APIs to the STL collection concept
• Adapt element-at-a-time APIs to the STL collection concept
• Share enumeration state in order to properly fulfill the requirements of the input iterator concept
• Enumerate potentially infinite collections
• Specialize standard algorithms for specific iterator types to optimize performance
• Define a safe, platform-independent STL extension for the system environment, implemented in terms of a global variable
• Adapt a collection whose iterator instances' copyability is determined at runtime
• Provide access to a reversible collection that is not repeatable
• Write into a character buffer using an iterator

Extended STL addresses these issues and more. It also looks at how general-purpose, STL-compliant libraries may be built without sacrificing robustness, flexibility, and, especially, performance. Extended STL teaches you how to have your abstraction cake, with efficiency cream, and eat it.

You should read this book if you want to:

• 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
• Pick up techniques for optimizing the performance of general-purpose libraries
• Use proven software components for STL extension

Subject Matter

I believe that you must write about what you know. Because the main purpose of this book is to impart understanding of the process and issues of STL extension, much of the material discussed derives from my work with my own (open-source) STLSoft libraries. Since I've implemented just about everything in STLSoft from scratch, it's therefore the best material to enable me to speak authoritatively. This is especially important when discussing design errors; publicly documenting other people's design errors in detail is unlikely to achieve many positive outcomes.

But this does not mean that reading Extended STL obliges you to use STLSoft or that followers of other libraries cannot learn anything appropriate to their practice here. Indeed, rather than proselytizing the use of any particular library, the material presented gives you an inside-out look at STL extension, focusing on STL principles and extension practices, rather than relying on extant knowledge of STLSoft or any other library. If, when you've read this book, you don't use the STLSoft libraries, I won't be troubled, so long as you've taken away useful knowledge on how to implement and use other STL extensions.

I make no pretension that the methods of STL extension I shall demonstrate in any way represent the only way. C++ is a very powerful language that, sometimes to its detriment, supports a variety of styles and techniques. For example, many, though not all, collections are best implemented as STL collections, while others are better represented as stand-alone iterators. There's a fair amount of overlap, about which much equivocation abides.

For most STL extensions discussed, I take the reader (and the author, in some cases!) on a journey from the raw APIs being wrapped up through intermediate, and often flawed, implementations before reaching an optimum, or at least optimal, version. I do not shy away from the implementation and/or conceptual complexities. Indeed, some of the techniques required to mold external APIs into STL form necessarily involve a degree of technical cunning. I'm not, for the sake of a simple tale, going to pretend that these things don't exist or leave them unexplained in the implementation. I will cover these things, and in so doing I hope to be able to (1) debunk some of their complexity and (2) explain why they are necessary.

One of the best ways to understand STL is to learn how STL components are implemented, and the best way to do that is by implementing them. If you don't have the time (or the inclination) to do that, I recommend that you avail yourself of the second best way, which is to read this book.

Structure

This book is divided into three main parts.

Part One: Foundations

This collection of small chapters provides grounding for the material discussed in Parts II and III. It begins with a brief recap of the main features of the STL, followed by a discussion of concepts and principles pertinent to STL extension, including the introduction of a new concept, the element reference category. The next few chapters consider foundational concepts, mechanisms, paradigms, and principles: conformance, constraints, contracts, DRY SPOT, RAII, and shims. The remaining chapters cover template tools and techniques, including traits and inferred interface adaptation, and several essential components used in the implementations described in Parts II and III.

Part Two: Collections

This represents the bulk of the book. Each chapter covers one or more related real-world collection and its adaptation into an STL extension collection component along with suitable iterator types. The subject matter tracks adaptations of subjects as diverse as file system enumeration, COM enumerators, non-STL containers, Scatter/Gather I/O, and even collections whose elements are subject to external change. The issues covered include concepts of iterator category selection and element reference categories, state sharing, mutability, and external iterator invalidation.

Part Three: Iterators

While the material in Part II includes the definition of iterator types associated with collections, Part III is devoted to stand-alone iterator types. The subjects covered range from custom output iterator types, including a discussion of simple extension of the functionality of std::ostream_iterator, to sophisticated iterator adaptors that can filter and transform the types and/or values of the underlying ranges to which they're applied.

Volume 2

Volume 2 is not yet complete and its structure not finalized, but it will contain material on functions, algorithms, adaptors, allocators, and the STL extension concepts range and view.

Supplementary Material

CD-ROM

The accompanying CD-ROM contains various free software libraries (including all those covered in the text), test programs, tools, and other useful software. Also included are three full but unedited chapters that didn't make it into print--either to save space or to avoid too much compiler specificity--and numerous notes and subsections from other chapters.

Online Resources

Supplementary material will also be available online at http://extendedstl.com/.

Product Details

• Paperback: 624 pages
• Publisher: Addison-Wesley Professional (June 29, 2007)
• Language: English
• ISBN-10: 0321305507
• ISBN-13: 978-0321305503
• Product Dimensions: 9.2 x 7.5 x 1.2 inches
• Shipping Weight: 2 pounds (View shipping rates and policies)
• Average Customer Review: 4.0 out of 5 stars  See all reviews (2 customer reviews)
• Amazon Best Sellers Rank: #555,013 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

13 of 15 people found the following review helpful:

4.0 out of 5 stars Pushing the STL envelope to the limit (and maybe beyond), December 18, 2007

By 

Giyora Sayfan "Gigi" (Davis, CA United States) - See all my reviews
(REAL NAME)   

This review is from: Extended STL, Volume 1: Collections and Iterators (Paperback)

Extended STL is a remarkable book. Matthew Wilson explores new C++ horizons. He invents new concepts and idioms and demonstrates them in real code, which is used in production (via the various STLSoft libraries). I've never read a book before that covers the spectrum from very high-level conceptual innovations to the most low-level implementation details.

The book is perfect for library writers that wish to create portable C++ libraries that work across compilers and platforms. It is not very useful for application developers (even STLSoft users).

The flow is very good and the important points are explained thoroughly. I also liked the concise tips that are sprinkled throughout the book and highlight key points like:

---------------

Tip: Check class invariants at the start (and end) of all public methods, including non-mutating ones, to maximize early detection of overwrites in errant code elsewhere in the process

---------------

I read the book cover to cover, but in small portions. Towards the middle, I started to skip over the implementation details, because it was too much for me.

Wilson's approach is to provide the ultimate performance and expressiveness (along with other important properties like modularity, robustness, flexibility and discoverability). This sometimes leads to libraries that platform-specific. Wilson justifies it by saying that the platforms differences are too great to encapsulate without seriously reducing one or more of the other desirable properties. So, there is a UNIXSTL and WINSTL with different interfaces that you can't use directly if you write code that needs to run on multiple platforms. There is also a PLATFORMSTL that has cross-platform components, but I'm not sure what are the relations between them. There are also several high-level libraries that are fully platform-independent and are built on top of the STLSoft libraries.

Note, that I have never used the STLSoft libraries, so I may be gravely wrong and in this case I apologize.

What I took from this book is that C++ is even richer and more complex than I have imagined. I dabbled in templates and I'm fairly educated about meta-programming, but I don't think I'll write any STL extensions myself anytime soon. I will definitely consider the STLSoft libraries (and the high-level libraries) for my next cross-platform C++ project. I'm also looking forward to the next book to see what Wilson is going to unearth.

Gigi

3 of 6 people found the following review helpful:

4.0 out of 5 stars Well written, July 6, 2008

By 

Cumhur Guzel (Sydney, NSW, Australia) - See all my reviews

This review is from: Extended STL, Volume 1: Collections and Iterators (Paperback)

This book explains container and iterator concepts very well and applies STL way of programming to different set of problems. It does provide somehow different point of angle to STL programming however in many parts reiterates the things said in the past. Anyway I recommend to the readers who has an interest on advanced STL programming.