Effective STLITEM2 is a code that is not related to container (container-independent) this illusion
STL is based on generic ideas, and arrays are generally used as Container and parameterized according to the types of objects they contain. The function is flush into Algorithms and parameterized according to the ITERATORS type they use. The pointer is lycope to Iterators and parameterized according to the type of objects they point to. But this is just a start. A single Container type is generally used as a sequence container and an associated container (Associative Container), similar Container has a similar function. Standard continuous memory Container provides random access Iterators; and standard node-based Container provides two-way iTerators. Sequence Containers supports push_front and / or push_back, and Associative Containers does not support. Associative Containers provide time-operation (translation: This is my understanding, don't know the logarithm "LOWER_BOUND, UPPER_BOUND, and Equal_Range Member Functions, and Sequence Containers is not available. As the entire extension process, we naturally want to join. This emotion is worthy of appreciation, and when you write your own Container, Iterators, and Algorithms, you certainly want to pursue this generalization process. It is a pity that many programmers are carried out in a different way. Usually, they are not in their software to implement a specific type of Container, but trying to generalize a Container concept for easy use, still retaining future options (such as a Deque or Is a list) - all this does not have to change the code using this Container. In other words, they try to write code-independent code that is not related to Container. This type of generalization, although it is a kind of consideration for goodwill, it is still wrong. Even the most enthusiastic about writing the code that is not related to the CONTAINER, soon, he will recognize that it is almost meaningless to write a software that allows Sequence Containers and Associative Containers. Many member functions are only existing in a CONTAINER. For example, only Sequence Container supports PUSH_FRONT or PUSH_BACK, and only Associative Containers supports count and lors_bound, and more. Even with the basic characteristics and semantic operations like INSERT and ERASE, it is also different from the Container type. For example, when you insert an object to a Sequence Containers, it is inserted. But when you insert an object into an Associative Containers, the Container moves this object to a location arranged in the index order in this object in Container. Another example is that this ERASE operation is entered with an Iterators, and a new iTerators are returned in a Sequence Containers, but when they call in Associative Containers, they do not return (Item 9 gives an example, explain How will this affect the code you wrote).
Then we assume that you want to write this code, which can use the most common Sequence Containers, such as Vector, Deque, and List. Obviously, you have to program the intersection of their functions, which means you can't use RESERVE or CAPACITY (see Item 14), because DEQUE and LIST do not provide such a member function. The existence of List also means that you have to give up Operator [], and you have to limit your code to the capabilities of the two-way Iterators. Conversely, this means you have to use your code to use Algorithms that is randomly access to Iterators, including sort, stable_sort, partial_sort, and nth_element (see Item 31). On the other hand, you want vector without using push_front and pop_front, and Vector and Deque cannot use Splice and Sort forms of member functions. In the above two limitations, the latter means that there is no Sort form in the SEQUENCE Containers in your generalized Sequence Containers. This is a clear situation. If you violate any of the above restrictions, your code will not compile because at least one of the Container you want to use. There will be more hidden dangers that will be compiled. The main criminal is applied to different Sequence Containers, making the rules of Iterators, pointers, and reference failures. In order to make the code written as Vector, Deque, and List, you must assume that the Container you are using in any one of such a Conta, or reference fails for any of the Container you are using for any of the Container you are using. of. Thus, you must assume that the call to INSERT is always invalid, because Deque :: INSERT makes all Iterators fail, and must be confident that the vector :: INSERT operation makes all pointer and reference failure due to lack of Capacity's capabilities. 1 Explanation DEQUE is very unique at some time, it will make it ITERATORS fail to make its pointer and reference implementation). The same reason can be concluded that every call to ERAS will be invalidated. Also want more examples? Ok, you can't pass the data in the Container to the interface of C, because only Vector supports this feature (see Item 16); you can't use Bool as the type of container, because, as Item 18 is explained In the case, Vector
After the end of the saying, I left you, it is such a generalized Sequence Containers: You can't call reserve, capacity, operator [], push_front, pop_front, splice, or any one requires random memory Take the Algorithms of Iterators; each INSERT and ERASE calls of this Container are linear, and it makes all Iterators, pointers, and references; and this Container cannot be compatible with C, and cannot store bools. Is this Container you want to use in your app? I don't think it is. If you press your ambition, decide to give up support for List. But you still have to give up Reserve, Capacity, Push_Front and Pop_front; you still have to assume that all calls (complexity complexity) for INSERT and ERASE (operation complexity) are linear and make everything fails; you still have to lose the same C-compatible memory layout (translation note : I think it should be a memory layout); and you still can't store bools if you want to give up Sequence Containers, and prepare to change to different Associative Containers, the situation is not there. Write such a code for SET and MAP is basically impossible, because SETS stores a single object and the MAPS stores a pair of objects. Although this can be made for SET and MULTISET (or MAP and Multimap), it is compared to other forms of form (translation: sorry, not seeing source code, I guess is the parameter) INSERT member. The function of the function is not the same for the return value of SETS / MAPS. And you have to carefully avoid any assumptions for any copy of how much values in Container. For MAP and MULTIMAP, you must avoid using Operator [], because this member function is only MAP. Faced with reality: This is not worth it. Different Container have their own advantages and disadvantages in different situations. They are not designed to be interchangeable, you basically can't cover them. If you want to try, then you are just a dream of spring and autumn, but this dream is not so sweet. Despite this, when you recognize what kind of Container you should choose, it is also dawn. Well, despite not the best, you need to use a different Container type. Now you understand, when you change the Container type, you must not only fix all your compiler diagnosis. You also need to check the code used to use Container, on the one hand, see if it needs to make changes in the performance characteristics of the new Container; on the one hand, look at the rules that make iterators, pointers, and references. If you don't have to use other Container, you must make sure you no longer rely on Vetor's and C-compatible memory layout; if you turn it by other Container to use Vector, you must make sure you don't use it to store Bools. Although inevitably change the Container type, you can easily make such changes, packages, packages, or packages in a usual way.
Among them, the easiest way is to use TypeDefs freely to Container and Iterators, so don't include: class widget {...}; vector
Class widget {...}; typedef vector
This will make it easy to change the Container type, which will bring you very convenient, if the problem changes, just simply add a custom allocator. (This change does not affect the rules that make itrators, pointers, and reference fails)
class Widget {...}; template
If the Typedefs package layer is meaningless, you may still recognize this effort to do this. For example, if you have such an object type map
And you want to traverse the entire map with const_iterators, do you really want to spell more than once? Map
After you have used STL for a while, you will realize that typedefs is a nice friend. A typedef is just some other type of synonym, so it is provided completely on the literal package. But a Typedef can't prevent it from doing (or dependent) any of them unprepared (or dependent). If you want to limit the choice of Container you exposed to the user, you need to strengthen encapsulation, you need to use the class. If you want to use another Container instead of the existing one, in order to limit the code you need to modify, you can package the Container into a class and limit the number of information related to the class accessible to the interface. For example, if you need to create a custom List, don't use List directly. You should create a CustomerList class and encapsulates a portion of the list in its private: class CustomerList {private: typedef list
At first, this may look a bit awkward. After all, a custom List is still a list, is it? Well, it may be. You will then find that you don't have to insert or delete customers in the middle of the List, you just need to quickly find 20% of your customers' top 20% - a special special for nth_elementalgorithms (see Item 31) Task. But nth_elementalgorithms needs to be randomly accessing Iterators, which cannot be used in one list. In this case, your custom "list" may be better with a Vector or a Deque. When you consider this type of change, you must still check each CustomerList member function and every friend, see how they are affected (depending on performance and Iterators / pointer / reference, etc.). But if you have made a good package for the implementation of CustomerList, then the impact on the CustomerList user will be small. You can't write code-independent code, but these codes may be unrelated to Container.
(Translation: This is the new book of Scott Meyers "Effective STL: 50 strokes in STL use technology", one of them published in the Addison-Wesley website, good stuff dare not exclusive, let's take a look, I hope help, let this translation are my first attempt, many places I feel unsatisfactory, please let you advice?)
The following is the original text:
Item 2:
Beware the illusion of container-independent code.The STL is based on generalization. Arrays are generalized into containers and parameterized on the types of objects they contain. Functions are generalized into algorithms and parameterized on the types of iterators they use. Pointers are generalized into iterators and parameterized on the type of objects they point to.That's just the beginning. Individual container types are generalized into sequence and associative containers, and similar containers are given similar functionality. Standard contiguous-memory containers (see Item 1) offer random-access iterators, while standard node-based containers (again, see Item 1) provide bidirectional iterators. Sequence containers support push_front and / or push_back, while associative containers do not. associative containers offer logarithmic-time lower_bound, upper_bound, and equal_range member functions, But Sequence Containers Don't.with All this generalization going on, it's nature to want to join the movement. This sentiment is laudable, and when you write your own containers, iterators, and algorithms, you'll certainly want to pursue it. Alas, many programmers try to pursue it in a different manner.Instead of committing to particular types of containers in their software, they try to generalize the notion of a container so that they can use, say, a vector, but still preserve the option of replacing it with something like a deque or a list later - all without changing the code That Uses It. That IS, The Strive To Write Container-Independnt Code.This Kind of Generalization, Well-Intentioned Though IS, IS Almost Always Misguided.
Even the most ardent advocate of container-independent code soon realizes that it makes little sense to try to write software that will work both sequence and associative containers. Many member functions exist for only one category of container, eg, only sequence containers support push_front with or push_back, and only associative containers support count and lower_bound, etc. Even such basics as insert and erase have signatures and semantics that vary from category to category. For example, when you insert an object into a sequence container, it stays where you put it, but if you insert an object into an associative container, the container moves the object to where it belongs in the container's sort order. For another example, the form of erase taking an iterator returns a new iterator when invoked on a sequence container, But it Returns Nothing When Invoked on An Associative Container. (Item 9 Gives An Example of How this can affect the code you write.) Suppose, thr to write code that can be used with the most common sequence containers:. vector, deque, and list Clearly, you must program to the intersection of their capabilities, and that means no uses of reserve or capacity (see Item 14), because deque and list do not offer them. The presence of list also means you give up operator [], and you limit yourself to the capabilities of bidirectional iterators. that, in turn, means you must stay away from algorithms that demand random access iterators, including sort, stable_sort, partial_sort, and nth_element (see Item 31) .On the other hand, your desire to support vector rules out use of push_front and pop_front, and both vector and deque put the kibosh on splice and the member form of sort.
In conjunction with the constraints above, this latter prohibition means that there is no form of sort you can call on your "generalized sequence container." That's the obvious stuff. If you violate any of those restrictions, your code will fail to compile with at least one of the containers you want to be 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, and list, you must assume that any operation invalidating iterators, pointers, or references in any of those containers invalidates them in the container you're using. Thus, you must assume that every call to insert invalidates everything , Because Deque :: Insert Invalidates All Iterators and, Lacking The Ability To CAPACITY, Vector :: Insert Must Be Assumed to Invalidate All Pointers and References (Item 1 Explains That Deque I s unique in sometimes invalidating its iterators without invalidating its pointers and references.) Similar reasoning leads to the conclusion that every call to erase must be assumed to invalidate everything.Want more? You can not pass the data in the container to a C interface , because only vector supports that (see Item 16). You can not instantiate your container with bool as the type of objects to be stored, because, as Item 18 explains, vector
When all is said and done, you're left with a "generalized sequence container" where you can not call reserve, capacity, operator [], push_front, pop_front, splice, or any algorithm requiring random access iterators; a container where every call to insert and erase takes linear time and invalidates all iterators, pointers, and references; and a container incompatible with C where bools can not be stored Is that really the kind 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 support for list, you still give up reserve, capacity, push_front, and pop_front; you still must assume that all calls to insert and erase take linear time and invalidate everything; you still lose layout compatibility with C; and you still can not store bools.If you abandon the sequence containers and shoot instead for code that can work with different associative containers, the situation is not much better Writing for both set and map. IS CL ose to impossible, because sets store single objects while maps store pairs 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 return types for sets / maps than for their multi cousins, and you must religiously avoid making any assumptions about how many copies of a value are stored in a container. With map and multimap, you must avoid using operator [], because that member function exists only for map.Face the truth : it's not worth it The different containers are different, and they have strengths and weaknesses that vary in significant ways They're not designed to be interchangeable, and there's little you can do to paper that over...
If you try, you're merely tempting fate, and fate doesn't like to be tempted. Still, the day will dawn when'll realize That a Container You Made Was, ER, Suboptimal, And You'll Need To use a different container type. you now know that when you change container types, you'll not only need to fix whatever problems your compilers diagnose, you'll also need to examine all the code using the container to see what needs to be changed in light of the new container's performance characteristics and rules for invalidation of iterators, pointers, and references.If you switch from a vector to something else, you'll also have to make sure you're no longer relying on vector's C-compatible memory layout, and if you switch to a vector, you'll have to ensure that you're not 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 : by Encapsulating, Encapsulating, Encapsulating. One of the easie St Ways to do this is through the liberts. hence, instead of write this, class widget {...}; vector
Class widget {...}; typedef vector
This makes it a lot easier to change container types, something that's especially convenient if the change in question is simply to add a custom allocator. (Such a change does not affect the rules for iterator / pointer / reference invalidation.) Class Widget { ...}; template
If the encapsulating assects of typedefs mean nothing to you, you're still likely to appreciate the work the can save. For example, if you have an Object of Type
map
Map
more than once? Once you've used the STL a little while, you'll realize that typedefs are your friends. A typedef is just a synonym for some other type, so the encapsulation it affords is purely lexical. A typedef does not prevent a client from doing (or depending on) anything they could not already do (or depend on). you need bigger ammunition if you want to limit client exposure to the container choices you've made. you need classes.To limit the code that may require modification if you replace one container type with another, hide the container in a class, and limit the amount of container-specific information visible through the class interface. For example, if you need to create a customer list, don ' t use a list directly Instead, create a CustomerList class, and hide a list in its private section: class CustomerList {private: typedef list
AT 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 Or Erase Customers from the middle of the list as offen as you ' anticipated, but you do need to quickly identify the top 20% of your customers -. a task tailor-made the nth_element algorithm (see Item 31) for But nth_element requires random access iterators It will not work with a list In that.. Case, Your Customer "List" might be better implemented as a vector or a deque.
