Effective Stl: Item 2: BEWARE The Illusion of Container-Independent

The STL is based on generalization. Arrays are generalized into con-tainersand parameterized on the types of objects they contain. Func-tionsare generalized into algorithms and parameterized on the typesof iterators they use. Pointers are generalized into iterators andparameterized on the type of objects they Point to.t¡ ¯s just the beginning. Individual container types are generalizedinto sequence and associative containers, and similar containers aregiven similar functionality. Standard contiguous-memory containers (see Item 1) offer random-access iterators, while standard node-basedcontainers (again, see Item 1 PROVIDE BIDIRECTIONAL ITERATORS. SEQUENCECONTAINERS Support Push_Front and / or Push_Back, While AssociativeContainers Don ¯T. Associative Containers Offer Logarithmic-TimeLower_Bound, Upper_Bound, Andequal_Range Member Functions, Butsequence Containers Don ¯t. With all this generalization going on, it. ¯S Natural to Want To Join Themovement. This Sentiment is laudable, and when you write your owncontainers, itrators, and algorithms, you. ¯ll certainly want to pursueit. Alas, many programmers try to pursue it in a different manner.Instead of committing to particular types of containers in their soft-ware, they try to generalize the notion of a container so that they canuse, say, A Vector, But Still Preserve The Option of Replacing It WITHSMETHING LIKE A Deque Or A List Later ª All without Changing The CodeThat Uses it. That IS, They Strive To Write Container-Independent Code.

This kind of generalization, well-intentioned though it is, is almostalways misguided. Even the most ardent advocate of container-independent code soonrealizes that it makes little sense to try to write software that will workwith both sequence and associative containers. Many member func- tionsexist for only one category of container, eg, only sequence con-tainerssupport push_front or push_back, and only associativecontainers support count and lower_bound, etc.Even such basicsasinsert and erase have signatures and semantics that vary from categoryto category. for example, when you insert An Object Into a Sequencecontainer, IT Stays Where You Put, But if you insert An Object Into An ഊ Associative Container The Container Moves The Object to Where Itbelongs in The Container¡¡ ¯s sort order. For another example, the form oferase taking an iterator returns a new iterator when invoked on asequence container, but it returns nothing when invoked on an asso-ciativecontainer. (Item 9 gives an example of how this can affect thecode you . write) Suppose, then, you aspire to write code that can be used with themost common sequence containers: vector, deque, andlist Clearly, you must program to the intersection of their capabilities, and thatmeans nouses ofreserve or capacity (see Item 14. Because Deque andList Don ¯T offer them.

The presence of list also means you give up opera-tor [], and you limit yourself to the capabilities of bidirectional itera-tors.That, in turn, means you must stay away from algorithms thatdemand random access iterators, including sort, stable_sort, partial_sort, andnth_element (see Item 31) .On the other hand, your desire to support vector rules out use ofpush_front and pop_front, andbothvector and deque put the kibosh onsplice and the member form of sort. In conjunction with the con-straintsabove, this latter Prohibition Means That there is no form ofsort you can call on Your ° generalized sequence container.. ± T¡ ¯s the obvious stuff. If you violate any of those restrictions, yourcode will fail to compile with at least one of the containers you want tobe able to use. The code that will compile is more insidious.The main culprit is the different rules for invalidation of iterators, pointers, and references that apply to different sequence containers.To write code that will work correctly with vector, deque, andlist, youmust assume that any operation invalidating iterators, pointers, orreferences in any of those containers invalidates them in the containeryou ¡ ¯re using. Thus, you must assume that every call to insert invali-dateseverything, because deque :: insert invalidates all iterators and, lacking the ability to call capacity, vector :: insert must be assumed toinvalidate all pointers and references. (Item 1 explains that deque isunique in sometimes invalidating its iterators without invalidating itspointers and references.) Similar reasoning leads to the conclusionthat every call to erase must be assumed to invalidate everything.

Want more? You can ¯T Pass the data in the container to a c interface, because online.. You can ¯t instantiateyour Container with Bool Asthe Type of Objects To Be Stored, Because, As Item 18 Explains, Vector Doesn ¡ ¯t always behave like a vector, and it never actually stores bools. You can ¯t assume list. ¯S constant- ഊ Time Insertions and deque Take Linertime to Perform Those Operations. When all is said and done, you ¡ ¯RE left with a ° Generalized SequenceContainer¡¡ ± WHERE you. ¯t call reserve, capacity, operator [], push_front, pop_front, splice, or any algorithm requiring random access iterators; acontainer where every call to insert and erase takes linear time andinvalidates all iterators, pointers, and references; and a containerincompatible with C WHERE BOOLS CAN ¡ ¯ That Really Thekind of Container You Want To Use in Your Applications? I Suspect Not.if You Rein in Your Ambition and Decide You. ¯re willing to drop supportfor list, you still give up reserve, capacity, push_front, andpop_front; youstill must assume that all calls to insert and erase take linear time andinvalidate everything; you still lose layout compatibility with C; andyou still can¡ ¯T store Bools. If you abandon the sequence containers and shoot instead for corethat Can Work with Different Associative Containers, The Situation ISN ¡ ¯TMUCH BOTTER. Writing for Both Set and Map Is Close To Impossible, Because Sets Store Single Objects.Even Writing for Both Set and MultiSet (or Map and Multimap) is Tough.

The insert member function taking only a value has different returntypes for sets / maps than fortheirmulti cousins, and you must reli-giouslyavoid making any assumptions about how many copies of avalue are stored in a container. With map and multimap, youmustavoid using operator [] , Because That Member Function EXISTS ONLY FORMAP. Face The Truth: IT¡ ¯S NOT WORTH IT. The Different Containers Are Different, and They Have Strengths and Weakness That Vary in Significantways. They¡ ¯re not designed to be interfaceableable, and there¡ ¯s littleyou can do to paper what over, you ¡ ¯re merely tempting fate, and fate doesn¡ ¯TLIKE to Be Tempted.still, The Day Will Dawn When You. ¯LL Realize That A Container Choice Youmade Was, ER, Suboptimal, and You. ¯ l n u u ¡¡k k k t ¡¡¡ ¯ll notonly need to fix whatver problem, you. ¯LLalso Need to Examine All The code Using the container to see whatneeds to be change in Light of the new container¡ ¯S Performance Char-Acteristics, PoInters, and Refer-Ences.if You Switch from a Vector To Something Else, You. ¯LL Also Have Tomake Sure You. ¯re no longer releating on vector ¡ ¯S c-compatible memorylet, and if you switch to a vector, you. ¯LHAVE TO ENSURE THAT You ¡ ¯renot using it to store bools ഊ Given the inevitability of having to change container types from time to time, you can facilitate such changes in the usual manner:. Byencapsulating, encapsulating, encapsulating.

One of the Easiest Waysto Do this Is Through The LibERAL USE OF TYPEDEFS for Container and iTer-atortypes. Hence, instead of writing this, class widget {...}; vector vw; widget bestwidget; ... // Give BestWidget a valueVector :: item I = // Find A Widget with thefind (vw.begin (), vw.end (), bestwidget); // Same Value As BestWidgetWrite this: class widget {...} ; typedef vector WidgetContainer; typedef WidgetContainer :: iterator WCIterator; WidgetContainer vw; Widget bestWidget; ... WCIterator i = find (vw.begin (), vw.end (), bestWidget); This makes it a lot easier To Change Container Types, Something Trum . ¯sespecially convenient if the change in question is simply to add a cus-tomallocator (Such a change doesn¡¯t affect the rules for iterator / pointer / reference invalidation.) Class Widget {...}; template // see Item 10 for why thisSpecialAllocator {...}; // needs to be a templatetypedef vector > WidgetContainer; typedef WidgetContainer :: iterator WCIterator; WidgetContainer vw; // still worksWidget bestWidget; .. .Wciterator i = find (vw.begin (), vw.end (), bestwidget); // still worksif the encapsulating aspects of typedefs mean nothing to you, you. ¯Restill Likey to Appreciate The Work They Can Save.

For example, if youhave An Object of Type ഊ Map :: item, cistringcompare> // cistringcompare IS ° Case - // INSENSITIVE STRING COMPARE; ± // Item 19 describes itand you want to walk through the map using const_iterators, do youreally want to spell outmap :: iterator, CIStringCompare> :: const_iteratormore than once? Once you¡ ¯VE Used The Stl a little while, you. ¯LL Realizet Typedefs Are Your Friends.a Typedef Is Just A Synynym for Some Other Type, So The EncapsulationIt Affords Is Purely Lexical. A typedef doesn¡ ¯T prevent a clomdoing (or depending on) Anything they couldn¡ ¯ THEDY DO (OR Dependon). You NEED BIGGER AMMUNITION IF You Want To Limit Client Exposureto the Container Choices You¡ ¯ve made. You need classes.To limit the code that may require modification if you replace one con-tainertype with another, hide the container in a class, and limit theamount of container-specific information visible through the classinterface. For example, if You need to create a customer list, don¡ ¯t usea list directly.Instead, create aCustomerList class, and hide a list in itsprivate section: class CustomerList {private: typedef list CustomerContainer; typedef CustomerContainer :: iterator CCIterator; CustomerContainer customers; public: // limit the amount of List-specific ... // information visible through}; // this interfacet first, this May seem slight is a list, right? Well, Maybe.