Effecective STL: Container (Terms 1: Carefully Choose your container)
[Geng] Recently I have been learning STL, from the "C Standard Library (The C Standard Library" to "STL source profiling" to "generic programming and STL (Generic Programming and the STL)", it is believed that STL has certain understanding. In order to make himself further improvement, try to translate this "Effective STL", there is a wrong mistake, welcome everyone to criticize, my email is smart_ttc@yahoo.com.cn, if there is any idea or error, please send me a message . In the translation process, I will have some addition to delete according to my own understanding, if you want the original taste, it is recommended to see the original version (the best reading method). I will translate all 50 terms, thank you for your support.
[Translator] SCOTT Meyers, C software development is the most authoritative, published works "Effective C ", "Move Effective C " and "Effective C CD". He was a column writer of "C Report", is a copy of "C / C Users Journal" and "Dr. Dobb's Journal", or a consultant all over the world. He is one of the members of the Advisory Committee of Numerix Llc and InfoCruiser Inc., has a Ph.D. in Computer Science in Brown University. "Effective STL" - 50 special methods used to improve standard template libraries are their latest works.
There is no doubt that STL has an iterators, algorithms, and Function Objects, but for most C programmers, STL is a container (Containers). They are more powerful than arrays, can dynamically grow and contract (sizes), can manage memory, know how many objects have been accommodated, and isolate the Algorithm Complexity of the Operations, and more and more. They are so popular is very easy to understand. They are better than their competitors, whether their competitors are containers from other libraries or the type of container yourself. The STL container is not just good, but it is really good - a bit of strong words (J).
The content of this chapter is mainly some guidelines that are applied to all STL containers. The following chapters will care about the specific container type. Here, the subject matter here includes selecting a suitable container in the face of a given constraint; avoiding such an illusion, that is, the code written for a® instrument type may also apply to other container types; the importance of copy operation Improvement of difficulty in saving pointers or auto_ptrs in the container; insertion and erase; using custom dispenser (Allocators) You can finish what and cannot complete; get the best efficiency; and in multithreading Precautions for using containers in an environment.
Well, there are many Dongdong, but please don't worry. All of this is divided into a small piece of a small piece of entry, row, you can get a few principles of (PICK UP) to apply to the code you wrote. Terms 1: Carefully choose your container (Choose Your Containers with Care.)
You know that in C , you can freely dispose of multiple containers, but how do you know how many of these containers do? In order to ensure that you have not ignored any possible choices, this is a short review.
n Standard STL Sequence Container (Sequence Containers), Vector, String, Deque, And List.
n Standard STL Relation Containing Container (Associative Containers), SET, MULTITISET, MAP, And MultiMap.
N Nonstandard Sequence Container (Nonstandard Sequence Containers) SLIST and ROPE. Slist is a one-way linked list, Rope is essentially a heavy String. (A "Rope" is a heavy "string". Do you understand?) (There is a metaphor, you can better understand the difference between ROPE and String, Rope is a rope, string is a thin line.) You can be in the first 50 short overview of these non-standard containers (these containers are generally available). (Translation: "Generally speaking" means that most STL standard libraries implement these non-standard containers.)
N Nonstandard Associative Containers Hash_SET, HASH_MULTITISET, HASH_MAP, HASH_MULTIMAP. I will carefully explain the various types (containers) that these conformationally-related containers based on the standard-enclosed containers.
N String alternative vector
n vector as a substitute for standard-related containers. In terms 13 you can see that in terms of time and space, VECTOR is sometimes done better than standard-related containers.
N Several standard non-STL containers include Arrays, BitSet, Valarray, Stack, Queue, and Priority_Queue. Because these are non-STL containers, in addition to the case of clause 16, use arrays to exceed STL containers and in terms 18 explains why BitSet may be better than Vector
This is all the choice, considering the various situations, you should take it from them when you choose a container. Unfortunately, the discussion of most STL is limited to a small part of the World of Containers, and many of the subjects on selecting the most suitable container are ignored. Even if the standard itself, only the following guidance is available in Vector, Deque, and List:
Vector, List and Deque provide a different complexity balance to programmers and should be used. Vector is a serial container as a default. List should be used frequently in inserting and deleting operations in the middle of the sequence. Select Deque when most insertion and deletion operations occur in the head and tail of the sequence. If your main concern is the complexity of algorithms, I think this charter is a reasonable suggestion, but there are more things to be concerned.
Now, let's consider important and container-related topics. This topic can better explain the complexity of algorithms, but first, I will introduce a method of container classification, which should be discussed frequently, but there is no (truth) Always master in the hands of a few people J). This is the difference between ContiUS-Memory Containers and Node-based Containers.
ContiUS-Memory Containers (called Array-based Containers) stores their elements in one or more consecutive memory blocks (dynamically allocated), any memory block holds more than One container element. If a new element is inserted or an existing element is erased (ERASED), other elements in the same memory block must be moved to the space occupied by the new element to provide space or the erased erase element. This move will affect performance (see clauses 5 and 14) and unusual security (so we will see). The standard continuous memory container is Vector, String, and Deque. Non-standard ROPE is also a ContiUS-Memory Containers.
Node-based containers (Node-based containers) only stores only a single element in each memory block (dynamically assigned). Insert and erase (EraSure) only affects the pointer to the node, does not affect the content of the node itself, so the element value does not need to move when performing insert or erase operation (meaning does not need to move the memory block). Indicates the containers such as List and SLISTs such as List and SLIST, and all related containers are node-based. (They are generally implemented with balanced trees.) Non-standard hash containers use a variety of node-based (Node-based)-based implementations, please see Terms 25.
Using this type of uncommon (out of the Way), we have begun to propose some questions that are most relevant when choosing containers. In the following discussion, I will ignore the container of non-STL (Non-Stl-Like) (for example, arrays, bitsets, etc.), after all, this is a book about STL.
n Do you need to insert new elements in any location in the container? If so, you need a sequence container, and the associated container does not have this feature.
n Do you care about how the elements in the container is sorted? If not, the Hashed Container is a possible option. Otherwise, avoid using a Hashed Container. Does the N container must be part of standard C ? If so, do not consider the Hashed Containers, SLIST, and ROPE.
n which type iterator do you need? If you must be Random Access Iterators, you can only use Vector, Deque, and String, of course, you might want to use ROPE. (About Rope More Information Terms 50.) If you need a two-way iterator, you must avoid using SLIST (see Terms 50) and the General Implementation of Hashed Container (implemented by ordinary methods) (See Terms 25).
N When performing insert or erase operation, avoid the elements already existing in the mobile container important? If yes, then leave a continuous memory-memory containers (see Terms 5).
Does the data in the N container need to keep layout compatibility with C? If so, you can only use vectors (see Terms 16).
N lookup speed is a key consideration? If so, you need to see a Hashed Container (see Terms 25), sorted Vectors, and standard related containers - select in this order.
n Do you mind that the underlying container uses a reference count (Reference Counting)? If so, you need to control String because many String implementation is based on reference count (see clause 13). You also want to avoid using ROPE because the determined Rope implementation is based on the reference count (see Terms 50). You must depict your own strings, of course, you should consider Vector
n Do you need a transactional semantics inserted and erase? That is to say, do you need a reliable back to insert and erase the ability? If so, you need to use node-based containers. If you need multi-element insertional transactional semantics, you should choose List because List is only a standard container that provides multi-element insertion transaction semantics. Transactional Semantics is especially important for programmers who are interested in writing an abnormal security code. (Transactional Semantics can also be reached with a continuous memory container, but there will be performance costs, code is not simple. For more, see the terms of Sutter's Exceptional C [8].) (Translation: Exceptional C has Published by the Power Press.) N Do you need to make iterator, pointer, and Reference failure? If so, you should use a node-based container because inserting and erase in these containers will never fail (unless they point to the elements you are erasing). Generally speaking, inserting or erasing on a continuous memory container may result in any of Neterators, Pointers, and References in the container.
N has a sequence container, which is the Random Access Iterator, as long as there is no erase operation, and always insert a new element in the end of the container, (in the iterator) pointer and reference not to fail Is there such a container help? This is a very special situation, but if this is your situation, Deque is the container in your dream. (Interestingly, when inserting an element in the tail of the Deque, it may fail. Deque is a standard STL container that can be expired and the pointer and reference will not be invalid.)
These issues are almost impossible to end all things. For example, they do not consider a wide variety of memory allocation strategies used in different container types. (Terms 10 and Terms 14 discusses some of these strategies.) Also, unless you are sorted, standard consistency, iterator compatibility, compatible with C, lookup speed, due to reference counting Rules, transaction semantics, or the level of iterators fail, they should be sufficient to make you believe, you don't just consider the algorithm complexity of the container operation, but more than this. Of course, this complexity is important, but it is just a small part of all issues.
In terms of containers, STL gave you a lot of choices. If you are not limited to STL, even more choices. Before selecting a container, make sure all the choices are considered. "Default container"? I don't think it is.
