Dr. Dobb's Journal January 1999
The Standard Template Library (STL) represents a significantly, if not radically, new way of programming with data structures in C++. Using the STL, both built-in and user-defined data types can be stored in standard containers (vectors and queues, for instance) and manipulated using generic algorithms (search, sort, and the like) with type safety, performance guarantees, and reduced user code. Combining ideas from the field of generic programming and C++'s template mechanisms is thus very powerful.
Now that the STL is part of the standard library for C++, its availability should continue to improve. Some excellent tutorials and books have been written for experienced programmers. What we need are good textbooks to educate new programmers. Ideally, such a textbook would be thorough in its discussion of how to use the STL and in the language-independent fundamentals of data structures and algorithms.
In this vein, Timothy Budd's Data Structures in C++: Using the Standard Template Library is a qualified success. However, I would also recommend a supplementary textbook with additional material on the design and implementation of classic data structures and algorithms.
By design, Budd's book provides a thorough introduction on how to use a particular part of the STL and then discusses a simplified implementation. But I often found myself wishing that the discussion would go deeper and be more explicit on a topic. For instance, examples that are more thoroughly worked out are always appreciated by students. Also, the use of the deque (double-ended queue) container is, rightly, allotted 20 pages, but the implementation is quickly covered in five pages. In fact, the implementation of some methods in the class deque is not given at all and may not be obvious to new programmers. A simplified implementation is fine, but it should be complete.
Pedagogically, two other aspects of the book may also be problematic. First, the fragmentary way in which code is presented makes it difficult for readers to type in, compile, then run the examples. The required header files are not listed for each example (mentioning them once in Chapter 1 is insufficient), sample main() functions are not always given, and, as mentioned, some methods are not fully implemented. Second, a distracting number of typos, inconsistencies (such as indenting style), and layout choices (unnecessarily splitting code fragments across pages) may confuse novice programmers. I would have preferred self-contained, complete, and ready-to-run examples. (The errata and source code at the author's web page are helpful.)
Despite my criticisms, I do like the clear writing style, the coverage of object-oriented programming principles, and the interwoven discussions of algorithmic complexity and correctness. In fact, for the experienced programmer, Data Structures in C++ would be a good introduction to the STL, framed as a review of basic computer science. Down the road, I want to teach a data structures course that focuses on the STL and takes the same basic approach as this book. Therefore, I hope that there will be a second edition.
-- P.L.
For those of you who have not been paying attention since the days of 10-Mbps Ethernet, there have been significant changes in Ethernet technology. You may be surprised to learn that the move to 100 Mbps involved much more than cranking up the data rate. The CSMA/CD protocol and shared coaxial cable medium of traditional Ethernet do not scale well to the higher data rate. The 100-Mbps scheme introduces changes in the transmission medium, the topology, the signaling technique (no more Manchester), and even in the relevance of the CSMA/CD scheme. Furthermore, 100 Mbps involves numerous options. In addition, another order-of-magnitude crank on the data rate, to 1 Gbps, involves many additional changes in media and signaling techniques. So there is a lot to learn to master the 100-Mbps and 1-Gbps incarnations of Ethernet.
Gigabit Ethernet: Migrating to High-Bandwidth LANs, by Jayant Kadambi, Ian Crayford, and Mohan Kalkunte, begins with a solid overview of the traditional 10-Mbps Ethernet technology. Next is a lengthy chapter (80 pages) on 100-Mbps Ethernet. The heart of this chapter systematically examines the various media and topology options, including a clear explanation of the various signaling techniques. The chapter also contains a good explanation of switched Ethernet and the use of full-duplex transmission and flow control. This is followed by an even longer chapter (100 pages) on Gigabit Ethernet technology. Again, there is a discussion of media options, topologies, signaling techniques, and full-duplex operation. The remainder of the book looks at Gigabit Ethernet applications and future trends.
Had I read only the Kadambi et al. book, I would have recommended it wholeheartedly. But then I discovered Rich Seifert's Gigabit Ethernet, which is an exceptional book. It covers essentially the same material as the Kadambi et al. book, but the organization, detail, clarity, and writing style make Seifert's book an outstanding effort. Part I of the book (140 pages) covers Ethernet and 100-Mbps Ethernet. The author is intent on not only presenting the technical details, but in explaining why certain technical choices were made and illuminating the evolution of Ethernet technology. The topics covered include the evolution from bus-based coaxial layout to star-based structure wiring layout, the movement from shared to dedicated LAN strategies, and issues related to full-duplex operation and the use of flow control. In addition, basic elements such as the frame format and CSMA/CD protocol are treated clearly. In Part II (140 pages), Seifert tackles Gigabit Ethernet technology. This part begins with an overview of Gigabit Ethernet architecture. Then, the medium access control scheme is covered, which includes both half-duplex and full-duplex approaches. Seifert provides an excellent explanation of the rationale and target applications for the two approaches. The next chapter discusses the role and nature of repeaters, switching hubs, and routing hubs. The treatment of the physical layer follows. The final portion of the book covers applications.
Both books provide about the same level of technical detail. For example, autonegotiation is one of the more complicated topics to explain; Seifert devotes 11 pages to this topic, and Kadambi has 13 pages. Although both books provide technically sound, well-written treatments of the Gigabit Ethernet, my vote goes to the Seifert book. The Seifert book has some nice, useful touches, including a detailed timeline of Ethernet evolution that spreads over four pages (the front and back inside covers) and a two-page table (pp. 156-157) that provides an admirably concise summary of the technological ingredients of the three generations of Ethernet. Beyond these goodies, Seifert's style is enjoyable to read and always informative. Here is an example. Seifert talks about the difficulty of interpreting some passages in the standards document because of the quirky use of language:
A good example is the very careful use of the words "shall" and "shall not". These are the only words used in an IEEE standard to denote a conformance requirement. Words such as "must," "will," "has to," and similar have no effect on conformance requirements of the standard. Thus, the statement, "A device must always do so-and," creates no requirement for it to do so in order to comply with the standard! In the same vein, the term "may" (in an IEEE standard) is exactly synonymous with the term "may not." Really.
Such gems make for good and instructive reading. But, when all is said and done, my preference is just my opinion. You can't go wrong with either book. If you're an interested reader, who has the opportunity, you should go to a technical bookstore that stocks both books, do a comparison, and make your own choice.
-- W.S.
DDJ