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.That¡¯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, iterators, 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 withsomething 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, e.g., 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 it, 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.¡±That¡¯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 only vector supports that (see Item 16). You can¡¯t instantiateyour container with bool asthe type of objects to be stored,because,as Item 18 explains, vector<bool> doesn¡¯t always behave like a vector,and it never actually stores bools. You can¡¯t assume list¡¯s constant-ഊtime insertions and erasures, because vector and deque take lineartime to perform those operations. When all is said and done, you¡¯re left with a ¡°generalized sequencecontainer¡± where you can¡¯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¡¯t be stored. Is 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 codethat can work with different associative containers, the situation isn¡¯tmuch better. Writing for both set and map is close to impossible,because sets store single objects while maps storepairs of 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 weaknesses that vary in significantways. They¡¯re not designed to be interchangeable, and there¡¯s littleyou can do to paper that over. If you try, 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¡¯ll need to use a different containertype. You now know that when you change container types, you¡¯ll notonly need to fix whatever problems your compilers diagnose, you¡¯llalso need to examine all the code using the container to see whatneeds to be changed in light of the new container¡¯s performance char-acteristicsand rules for invalidation of iterators, pointers, and refer-ences.If you switch from a vector to something else, you¡¯ll also have tomake sure you¡¯re no longer relying on vector¡¯s C-compatible memorylayout, and if you switch to a vector,you¡¯llhave 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<Widget> vw;Widget bestWidget;... // give bestWidget a valuevector<Widget>::iterator i = // find a Widget with thefind(vw.begin(), vw.end(), bestWidget); // same value as bestWidgetwrite this:class Widget { ... };typedef vector<Widget> 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 that¡¯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<typename T> // see Item 10 for why thisSpecialAllocator { ... }; // needs to be a templatetypedef vector<Widget, SpecialAllocator<Widget> > 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 likely to appreciate the work they can save. For example, if youhave an object of typeഊmap<string,vector<Widget>::iterator,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<string, vector<Widget>::iterator, CIStringCompare>::const_iteratormore than once? Once you¡¯ve used the STL a little while, you¡¯ll realizethat typedefs are your friends.A typedef is just a synonym for some other type, so the encapsulationit affords is purely lexical. A typedef doesn¡¯t prevent a client fromdoing (or depending on) anything they couldn¡¯t already 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<Customer> CustomerContainer;typedef CustomerContainer::iterator CCIterator;CustomerContainer customers;public: // limit the amount of list-specific... // information visible through}; // this interfaceAt first, this may seem silly. After all a customer list is a list,right?Well, maybe. Later you may discover that you don¡¯t need to insert orerase customers from the middle of the list as often as you¡¯d antici-pated,but you do need to quickly identify the top 20% of your cus-tomers¡ª a task tailor-made for the nth_element algorithm (seeItem 31). But nth_element requires random access iterators. It won¡¯twork with a list. In that case, your customer ¡°list¡± might be betterimplemented as a vector or a deque.When you consider this kind of change, you still have to check everyCustomerList member function and every friend to see how they¡¯ll beaffected (in terms of performance and iterator/pointer/referenceinvalidation, etc.), but if you¡¯ve done a good job of encapsulating Cus-ഊtomerList¡¯s implementation details, the impact on CustomerList clientsshould be small. You can¡¯t write container-independent code, but theymight be able to.
