Effective STL Terms 2: Beware of the illusion of the container independent code

zhaozj2021-02-12  147

Effective STL

Terms 2: Beware of the illusion of the container independent code

(Item2: BEWARE The Illusion of Container-Independent Code.)

STL is constructed on the basis of generization. The container is generalized by an array, and parameterized is parameted according to the object type therebetween. The algorithm is described in a function (Generalized), and parameterized is parameted according to the iterators type. The iterators is described in a Pointers, and parameterized is parameted according to the type of object (Objects), which is pointed.

This is just a start. The individual vessel types are generally used as sequence and associated (Associative) containers, and similar containers have similar functions. Standard Continuous Memory-Memory Container (See Terms 1) Provides random access iterators, and standard node-based-based containers (see clauses 1) provide bidirectional iterators ). Sequence containers supports PUSH_FRONT and / or PUSH_BACK, and Associative Containers is not supported. Associative Containers provides a member function for the logarithmic time: Lower_Bound, Upper_Bound and Equal_Range, but the sequence containers are not available. (Translation: Standard algorithm provides three template functions for Lower_Bound, Upper_Bound, and Equal_RANGE, but requires the iterator intervals required as parameters must be orderly, in other words, first sort the elements in the container.)

As all of these generalization processes continue, it is natural to easily generalize. Oh, this attitude is worthy of saying that when you write your own container, iterator, and algorithm, it should be used as much as possible. In addition, many programmers try to use generalization in a different way. They are not in their software to increase specific container types, but try to go to the concept of generalized containers, so they can, while using the vector, they also replace the manufacture of DEQUE or LIST. The option - all of these do not have to change any related code. That is to say, they strive to write the container independent code (Container-Independent Code). Although this generally derived from a good purpose, it is almost always misleaded.

Even the most enthusiastic container unrelated code will quickly realize that the software that attempts to work in a sequence and related containers will have little significant. Many member functions exist only in a container type, such as only the sequence container supports PUSH_FRONT or PUSH_BACK, and the associated container only supports count and lower_bound, and more. Even the basic operations like INSERT and ERASE will also have their own features (Semantics) as the (container) type. SIGNATURES. For example, when you insert an object in a sequence container, the object is inserted in the inserted position, but when you insert an object in the associated container, the container moves the object, depending on the container Sort order. Another, for example, an overload version of ERASE (this version is used as a parameter as a parameter), and a new Iterator is returned when the member function of the serial container is called, but the member function as the associated container is called void. . (Terms 9 Examples This is how this is how you write code.) Suppose you are eager to write code that can be used with the most common sequence container (VECTOR, DEQUE, and LIST). Obviously, you can only write code that is suitable for their ability (ie, the intersection of their support), which means you can't use RESERVE or CAPACITY (see Terms 14), because DEQUE and LIST do not provide these two operations. Similarly, the use of List means you want to give up Operator [], and you can only use the two-way iterators that supported by the Bidirectional Iterators. In this way, it means that you must stay away from algorithms that need to be supported by Random Access Iterators, including sort, stable_sort, partial_sort, and nth_element (see Terms 31).

On the other hand, you have to support the use of Vector, and the use of PUSH_FRONT and POP_FRONT, VECTOR and DEQUE are ignored to Splice and Sort members (Vector and Deque do not have SPLICE and SORT two member functions). In conjunction with the constraints mentioned above, the latter restriction means you can't adjust the member function sort on your "generic sequence container".

It can be easily concluded: If you violate any restrictions, then there is at least one of you want to use the container that can cause compilation failure, as long as this container is used in your code. The code to be compiled will also be more difficult.

(The problem mentioned earlier) The culprit is different sequence containers with their own iterators, pointers, and reference to failure rules. To write the code that works correctly with Vector, Deque, and List, you must assume that if there is an operation in a container to make iterators, pointers, and references, then this operation should also make other containers Iterator, pointer, and reference failure. In this way, you must assume that INSERT will make anything fails, because Deque :: INSERT makes all iterator invalidates, and the ability to lose Capacity, you must assume that call vector :: INSERT will make all Pointer and reference failure. (Terms 1 explain Deque is the only container that will sometimes make iterators without making pointers and reference failures.) Similar reasons You must also assume that the call ERASE will make anything to fail. Do you want more example? You cannot transfer data in the container to the C interface because only Vector supports this operation (see clause 16). You can't instantiate the container that as Bool as a storage object type, because (as explained in Terms 18) VECTOR behavior is not always like vector, in fact it never stores bools. You can't assume that the insertion of the constant time of the List (ERASURES), because Vector and Deque need to spend linear time to perform these operations.

When all constraints are considered, you have a "generalized sequence container". To use this container, you can't call Rest, Capacity, Operator [], PUSH_FRONT, POP_FRONT, SPLICE, or randomly access iteration Random Access Iterators supported algorithm; each call INSERT and ERASE spend linear time and makes all iterators, pointers, and references; it is not compatible with C, and BOOLs cannot be stored. Is this really what you want to use in your app? I doubt n't.

If you want to control your ambition, decide no longer support List, you still have to give up the use of Reserve, Capacity, Push_Front and Pop_Front; you still have to assume that INSERT and ERASE take linear times and make all all failure; You still lose compatibility with the C layout; you still can't store bools.

If you give up the serial container, change the idea to write the code that can work with all associated containers, and the situation will not be better. It is almost impossible to write code for SET and MAP, because SET stores a single object (SINGLE Objects) and the MAP storage dual object (PAIRS OF Objects). It is also difficult to write code for SET and MULTISET (or MAP and MultiMap). Insert member functions in SETS / MAPS have an overload version (this version only needs a parameter value value) and its multi brothers (meaning MultiSets / Multimap) have different return types (translation: SETS / MAPS) : Pair INSERT (const value_type & _val); the prototype in MultiSets / Multimap is: Iterator INSERT (Const Value_Type & _Val);). At the same time, you must also avoid this assumption: how many of the same Value values ​​are stored in the container (SET and MAP do not allow repeated values). When Map and MultiMap are used together, you must avoid using Operator [], because Operator [] exists only in MAP. Face the fact: this is not worth doing (the write container is independent of code). Different containers are different, and they have their own advantages and disadvantages. They are designed not to interchange, don't want to ignore this. If you try, then you are provocating fate, while fate doesn't like to be provocative.

Similarly, when you realize that the selected container is not the most ideal, the sky is going to break, and you need to use a different container type. Now you know when changing the container type, you don't just solve the problem of compiler reports, but also check all the use of the container according to the performance characteristics of the new container and iterator, pointer, and reference for the failure rules, thus understand what needs to change . If you want to convert from a vector to another container, you must make sure you no longer rely on the Vector's C-compatible memory wrap, to convert to the vector, you want to make sure you will use it to save Bools.

Since the type of change in the container from time to time is inevitable, you can use a general method to make this change easier: by packaging, packaging, or packaging. The easiest way is to use the TypeDefs that uses containers and iterator types. So don't write this:

Class widget {...};

Vector VW;

Widget bestwidget;

... // Give BestWidget a Value

Vector :: item i = // Find a widget with the same

Find (vw.begin (), vw.end (), bestwidget; // value as bestwidget

Write like this:

Class widget {...};

Typedef Vector widgetContainer;

Typedef widgetcontainer :: items wciterator; widgetContainer CW;

Widget bestwidget;

...

Wcitrator i = Find (cw.begin (), cw.end (), bestwidget;

This makes it easy when changing the type of container, is especially convenient when you want to change just add a custom dispenser (allocator). (This change does not affect the failure rules for Iterator / Pointer / Reference.)

Class widget {...};

Template // See Item 10 for why this need

SpecialalLocator {...}; // a template

TypedEf Vector > WidgetContainer;

Typedef WidgetContainer :: item Works; // STILL WORKS

WidgetContainer CW;

Widget bestwidget;

...

Wciterator i = Find (cw.egin (), cw.end (), bestwidget; // still works

If you don't want TypeDefs package, you are likely to appreciate them to help you save. For example, you have this type of object:

MAP

Vector :: item,

CiStringCompare> // cistringcompare is "case-insensitive

// String Compare; "Item 19 Describes IT

And you want to use MAP's const_iterators, you really want to spell

Map :: item, CISTRINGCompare> :: Const_Iterator

How many times? Once you have used STL for a while, you will realize TypeDefs is your good friend.

Typedef is just a synonym of some type, so it provides the package that is purely literally. Typedef cannot prevent customer code (or dependence) anything they can no longer do (or dependent). If you want to limit the details of exposure to your customers, you need a better weapon. What you need is class.

If you want to replace the type of container, you should limit the code that may be modified, hide the container inside the class, minimizes the specific container information that can be accessed (passing through class interface). For example, if you want to build a customer list, don't use List directly. Instead, create a CustomerList class and hide one List in the private domain:

Class customerlist {

Private:

Typedef List CustomerContainer;

Typedef CustomerContainer :: item CCITERATOR;

CustomerContainer Customers; Public: PUBLIC:

... // limited the Amount of List-Specific

// Information visible throught this // interface

}

First of all, this seems to be a bit stupid. After all, the customer List is a list, right? Well, maybe. Not long ago, you may find that you don't need to have the frequent central insertion (INSERT) and erase (ERASE) customers who have expected, but you need to quickly access 20% of the customer - the task customized for the algorithm nth_element (See Terms 31). But NTH_ELEMENT needs to be randomly access iter (Random Access Iterators). It cannot be used with List. In this case, your customer "List" can be better implemented with Vector or Deque.

When you consider this change, you still have to check the member functions of each CustomerList, and figure out how they are influenced (in terms of performance and Iterator / Pointer / Reference failure, "if you are in encapsulation Customerlist The implementation details are very good, the impact of customer code for CustomerList should be small. You can't write a container-independent code, but they (packaged classes) may be available.

转载请注明原文地址:https://www.9cbs.com/read-6181.html

New Post(0)