Using :: std :: vector <> as the preferred choice of the dynamic array of management: wangtianxing Submitted by: eastvc Date: 2003-9-19 17:34:41 ORIGINAL:
http://www.cpphelp.net/issue/Vector.html
Summary: This article describes the container vectors in the C standard library, analyzes its advantages, and it is recommended to use it as a priority selection of dynamic arrays in the application, rather than other class templates such as MFC Carray <>. Finally, introduce the interface and precautions when using the Vector.
In some programs that use the MFC, many programs often use Carray <>, due to the design problem of Carray <>, resulting in the complication of its code, increasing the maintenance difficulty. So recommendations :: std :: vector <> instead of Carray <>.
In addition, some programs are manually managed by malloc / realoc / free / new [] / delete []. In the application, manual management memory is easy to cause errors, and should be used to manage dynamic arrays with :: std :: vector <>.
Due to the less content between :: std :: vector, we do some introductions here for reference.
It doesn't matter if you are not familiar with Carray <> / Win32, it is not much here to mention them.
Carray <> vs :: std :: vector <>?
Carray <> and :: std :: Vector <> is a template class for managing the dynamic arrays of any type of object. All managed dynamic memory is released during deconstruction. It can therefore be used instead of manual dynamic array management.
However, Carray <> is designed for many years (VC 2.0 era), which is designed to design, object-oriented program design, template program design, etc., especially for object-oriented technology at the time. Error faith and propaganda, resulting in major errors in Carray <>.
After C language standardization (1998), and VC 6.0, there is a standard :: std :: vector <> template, basically better than Carray <>. Microsoft has always retained Carray <> due to the support of the old program, but it is clear that it is not intended to develop it in accordance with new ideas (at least Operator = (Carray Const &).
In summary, Carray <> :: std :: vector <> is below:
1) Carray <> is MFC, :: std :: vector <> exists in any standard C implementation. Therefore, you can use Carray <>, you can only use it in the MFC, if you use :: std :: Vector <>, you can use it under any C compiler of any platform. The use of standard components is also beneficial to others understand your procedure. CARRAY <> Inherited COBJECT, just in order to achieve serialization, this is inappropriate, violates the C design principle of "you don't pay what you don't use." :: std :: Vector <> Without inherit anything, just implementing a dynamic array. 2) Carray <> is not an appropriate value type, such as the following operations are illegal:
Carray
Carray
B = a; // error, MUST USE COPY ().
B == a; // error, You Must Write Your Own.
B In contrast to Carray <>, :: std :: vector <> is a serious design value type, naturally a copy constructor and can be assigned. If t is comparable, then :: std :: Vector In addition, since four special member functions are involved; T (); // Default Constructionor) (DEFAULT CONSTRUctor) ~ T (); // deconstruction function (Destructor) T (t const &); // copy constructor T & operator = (t const "; // copy assignment function Automatic generation, if Carray () is used as a member variable of T, then the last two of the above four special functions will not be automatically generated, and manually is written: Struct t { T () {} T (t const & t) { A_.copy (t.a_); i_ = T.I_; D_ = T.d_; S_ = T.s_; } T & operator = (t const & t) { IF (this! = & t) { A_.copy (t.a_); i_ = T.I_; D_ = T.d_; S_ = T.s_; } RETURN * THIS; } Private: Carray INT i_; Double D_; :: std :: string s_; } If you use :: std :: vector <>: Struct t { Private: :: std :: Vector INT i_; Double D_; :: std :: string s_; } The three special member functions listed above do not need to be written. The advantage is obvious: When you increase or decrease the member variables of T, you don't have to increase or decrease in T (T const &) and Operator = (). 3) There is no ready-made algorithm to operate Carray <>, and most standard algorithms in standard C can run directly at :: std :: vector <>. For example: static int covest init_vals [] = {3, 1, 4, 1, 6, 9}; Vector * Find (A.BEGIN (), a.End (), 6) = 5; // Turn 6 to 5 Sort (A.BEGIN (), A.End ()); // Sort. It can be said that the main design error of Carray <> is to design one of a simple "value" type to a difficulty "object" type. All "Value" has been lost, but those derivatives from carray <> inherited? The issues such as CBYTEARRAY are the same as Carray <>, or even more (for example, CPTRARRAY, never use). Similarly, other MFC Container templates, like CMAP <>, clist <>, there is a similar problem, you should use :: std :: map <>, :: std :: list <> and other designs better things instead . 2. :: std :: vector <> Where? :: std :: Vector <> Definition in header file (Note that the standard C header file is not. H suffix, there is .h file is compatible with C, or supports old unshireless things, like Namespace STD { Template Struct Vector { // Detailed content will be discussed later } Template Bool Operator == (Vector Template Bool Operator! = (Vector Template Bool Operator <(Vector Template Bool Operator> = (Vector Template BOOL Operator> (Vector Template Bool Operator> = (Vector Vector <> Definition in NameSpace STD, in order to reduce the number of keystrokes, usually use a type definition to shorten the type name: #include Typedef :: std :: vector INTVECTOR A; INTVECTOR B (A); INTVECTOR C; C = B; Assert (a == c); Note that six vector In addition, a = alloctor 3. :: std :: Vector <> Type Definition Some types are defined in vector <>, and only commonly used: Typedef t value_type; Typedef t0 iterator; TypedEf T1 Const_Ipectrator; Typedef t2 reverse_iterator; Typedef T3 const_reverse_iterator; Value_type is the element type of Vector Iterator / const_iterator is an unknown type for two vector <>, used to access elements in Vector <>, similar to the T * / T Const * pointer, their difference is that a pointed element can be modified, the other Can only read: Typedef :: std :: vector INTVECTOR :: Iterator; INTVector :: const_iterator c_iter; // ... iTer; Iter ; // ok: increment, post-inccess. --ither; item ---; // ok: Decrement, Post-Decrement. C_ITER; C_ITER ; // OK: Increment, Post-Increment. --c_iter; c_iter ---; // ok: Decrement, Post-Decrement. * iter = 123; // ok. INT k = * iter; // ok. K = * - c_iter; // ok. * c_iter = k; // error. C_ITER = iter; // ok: Iterator is convertible to const_iterator. iter = c_iter; // error: can't Convert Const_Iterator to iterator. In fact, Iterator / const_iterator and t * / t const * are basically the same, in fact, there are some vector <> implementations to implement Iterator / const_iterator, but can not regard iterator / const_iterator as true T * / t const *: t * p = iter; // may fail to compile. T const * q = c_itor; // may fail to compile. Reverse_iterator / const_reverse_iterator is similar to Iterator / const_iterator, but accesses the elements in the vector in the opposite order (from the tail to the head). A variety of Iterator has a particular important meaning in STL, but here we do not do specific introductions. As long as it understands the elements in the Vector of the VECTOR, it is probably equivalent to a pointer to an indication location. 4. :: std :: vector <> Vector <> provides the following constructor: (ignore the allocator parameter) Vector (); VECTOR (size_t n, t const t = t ()); Vector (Vector Const &); Vector (const_iterator first, const_iterator last); 1). Construct an empty vector without any elements. INTVECTOR V1; // Empty integer vector. 2) VECTOR (size_t n, t const t = t ()); Constructed a Vector of n identical T. If you do not give T, then use T () to make the default value: INTVECTOR V2 (100, 1234); // 100 1234. INTVECTOR V3 (100); // 100 0. 3) Vector (Vector const & other); Copy the constructor, copy the contents in Other: INTVECTOR V4 (V2); // 100 1234. 4) VECTOR (const_iterator first, const_iterator last); In fact, this constructor should be Template VECTOR (ITER First, Iter Last); That is, copy any sequence [first, last) into the vector. Due to the restrictions of the VC 6SP0 compiler, the iter is changed to const_iterator. However, happens that const_iterator is t const *, so you can use it as follows: INT A [] = {1, 2, 3, 4, 5}; INTVECTOR V5 (A, A 5); // {1, 2, 3, 4, 5} INTVECTOR V6 (v5.begin () 2, v5.end ()); // {3,4,5} 5. Access the elements in Vector <> The following member function / operator is used to access one of the elements in the Vector: T & AT (SIZE_T N); T Const & At (SIZE_T N) Const; T & Operator [] (SIZE_T N); T Const & Operator [] (size_t n) const; T & front (); (); T & back (); T Const & Back () Const; Note that due to the vector is a "value" semantic object, all operation functions must strictly guarantee the correctness of Const. Therefore, all element access methods have const and non-constings. Both AT (n) and operator [] (n) returns a reference to the elements of the subscript N, and their difference is that at () performs the subscript crossed check. If the offline is found, the Range_Error exception is found, Operator [] is not The subscript is checked. Front () returns a reference to the element of the subscript 0, and back () returns a reference to the last element. INT A [] = {4, 1, 4, 1, 5, 8}; INTVECTOR V (a, A 6); // Use front (), back (): v.front () = 3; v.back () = 9; // Use Operator [] (): For (SIZE_T I = 0; i :: std :: cout << v [i] << '/ n'; 6.:: Std :: Vector <> Storage Management The following member functions are used to store management: Void Reserve (size_t n); SIZE_T CAPACITY () Const; Void Resize (SIZE_T N, T T = T ()); Void clear (); SIZE_T SIZE () Const; BOOL EMPTY () const {return size () == 0;} SIZE_T MAX_SIZE () Const; In addition, push_back (), insert (), etc. also involves storage management, and will be described later. 1) max_size () Returns the number of up to T> the theoretical one. This is just a theoretical number, probably 4Gb / sizeof (t), there is no practical value. Do not use it in the program. 2) size () Returns the number of T> actually installed in Vector 3) EMPTY () Returns true if there is no T object in Vector 4) CLEAR (); Clear all T objects in Vector 5) Resize (size_t n, t t = t ()); Set the number of elements in the vector to N, N can be greater than size () or less than size. If N is less than size (), then the product in the vector is N..size () - 1 will be deconstructed. If n> size (), then N - size () of the same element T will be added later in the vector. When you increase the vector, you may have a storage re-allocation. In summary, after calling Resize (N, T), (Size () == n) is established. Note that if resize (n) does not with parameter T, T must be default. 6) RESERVE (SIZE_T N); Save at least N T objects can be saved in advance. After the call (Capacity ()> = n) is established. 7) Capacity (); Returns the number of T-type objects that have been assigned in allocated storage spaces. Subsequent increased element operations (such as push_back (), insert ()) If the number of total elements in the Vector of the Element does not exceed Capacity (), the VECTOR implementation guarantees that the storage space is not reassigned. The dynamic storage space of Vector Management is continuous. Execute operation INTVECTOR V (7, 1); // seven office. v.reserve (12); After the state of V can be represented by the following figure: / - Size () --- / | 1 | 1 | 1 | 1 | 1 | 1 | 1 | - | - | - | - | - | / - CAPACITY () --------- / Among them, 1 is an object that has been constructed, - is an object that can be constructed, but there is no constructed original space. Execute again v.push_back (2); v.push_back (3); The state of V is available in the picture below: / ---- Size () ----- / | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 3 | - | - | / ---- Capacity () ------- / Execute Resize (11, 4); / ---- Size () --------- / | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 3 | 4 | 4 | / ---- Capacity () ------- / Capacity ()> = size () is always established. For the subscript of [size () .. capacity () - 1] is not accessible: v [11] = 5; // undefined behavior - Anything CAN Happen. 7. Add elements to vector The following operations add an element to the vector and may cause storage assignments: Void Push_Back (t const & t); Void Insert (Iterator POS, T (); Void INSERT (Iterator POS, SIZE_T N, T Const & T); Template Void Insert (Iterator POS, ITER First, Iter Last); Push_back () is to add an element to the end of the Vector. INSERT () is before the POS indication is inserted into a position of T, or N t, or from the first start to the end of the Last. When the size () will be greater than Capacity () when the element is inserted, it will cause automatic storage allocation. Vector will allocate a new storage area that is larger than the required storage area (usually 1.5 to 2), copy the old element, and complete the addition or insert, then release the old memory area. That is to say, the space size of the Vector automatic storage allocation is an exponential growth, which ensures that when the elements are added multiple times, the average is close to constant. INTVECTOR V; // Add 0, 1, ..., 99 to v: For (int i = 0; i <100; i) v.push_back (i); // Append 9, 8, 7, ..., 0 to the end: INT A [] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; v.insert (v.end (), a, a 10); 8. Delete elements The following member functions complete the element deletion: void eraSe (Iterator); Void Erase (Iterator First, Iterator Last); Void pop_back (); Void clear (); These functions delete one, a string, last, or all element. INTVECTOR V; For (int i = 0; i <100; i) v.push_back (i); // Delete 50, 51, ..., 89: v.ras (v.begin () 50, v.end () - 10); // Delete 49, 48: v.pop_back (); v.pop_back (); // delete all: v.clear (); Note that the delete operation does not cause storage allocation, so Capacity () is unchanged. 9. Accessing the elements in the vector as a sequence Sequence is a very important concept in STL, all container types and algorithms involved, and all algorithms are built on "sequence" concept. "Sequence" is a linear structure that is determined by a superposition (Iterator) indicating its start and an indication. If first and last are some type of stacked, it is often used in [first, last) to represent a sequence. Note that the element points to the element is an element of this sequence, while the Last indicates the position after the last element of this sequence, which may not be accessed at all. This semi-closed interval represents the convention in the entire C standard, and it is indeed simplified the program. The superposition is the abstraction of the traditional C / C pointer and further classification. In C , the item is divided into ITERATOR, OUTPUT ITERATOR, FORWARD ITERATOR, FORWARD ITERATOR, five categories. The randomaccess iterator is the strongest class, that is, the most operation allowed. The pointer type in C and the version / const_iterator / revrse_iterator / const_reverse_iterator of the Random Access Iterator are met. The following functions are defined in VECTOR <> to obtain various superfine sons that are controlled (managed) sequences (dynamic arrays): Iterator begin (); Iterator end (); Const_iterator begin () const; Const_iterator End () const; REVERSE_ITERATOR RBEGIN (); REVERSE_ITERATOR REND (); Const_reverse_iterator rbegin () const; Const_reverse_iterator rend () const; Here we don't discuss the general concept of the superfine, only to mention a few Random Access Iterator: INT A [] = {1, 2, 3, 4, 5, 6}; [A, A 6) is a random access sequence indicating all elements in A []. The type of the stack is int *. [A 2, A 4) is also a sequence indicating 3, 4 elements in A []. The type of superposition is still int *. INTVECTOR V (100, 1); // 100 1. [v.begin (), v.end ()) is a random access sequence indicating all elements in V, and the type of superposition is intVector :: itemarator. [v.begin () 10, v.End () - 20) is also a random access sequence refers to other elements of the head 10 and 20 elements outside the V. [v.rbegin (), V.Rend ()) is a random access sequence refers to all elements in V, but is different from [v.begin (), v.end ()), this sequence is from the end Go to the head to traverse all elements. [v.rbegin () 20, V.Rend () - 10) is the same as the elements indicated by [V.BEGIN () 10, V.End () - 20), but the traversal order is opposite. The following figure shows the archive () / end () / rbegin () / end () / end () of the product: Begin () ----------> End () | | | v v | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ^ ^ | | | Rend () <---------- Rbegin () INTVECTOR V; For (int i = 0; i <10; i) v.push_back (i); // Print 0, 1, 2, ..., 9: For (intVector :: item i = v.begin (); i! = v.end (); i) :: std :: cout << * i << '/ n'; // Print 9, 8, ..., 0: For (intVector :: reverse_iterator i = v.rbegin (); i! = v.rend (); i) :: std :: cout << * i << '/ n'; In addition to using Begin () / end () / rbegin () / rend () to traverse the elements in the vector, because the space management space is continuous, you can take the address directly to process: :: Std :: Vector Handles.push_back (handle1); Handles.push_back (handle2); :: WaitFormultipleObjects (Handles.Size (), & Handles [0], True, Infinite; This is especially useful when connecting to the C library function. 10. Assignment and exchange Vector <> is the value that can be assigned, which is also the average "value" type must be provided: INTVECTOR V (100, 123); INTVECTOR V1; V1 = V; Vector also provides Template Void Assign (Iter First, Iter Last); Void Assign (SIZE_T N, T ()); Used to assign a value: INT A [] = {1, 3, 5, 7}; v.assign (A, A 4); // v will include 1, 3, 5, 7. V.ssign (100); // 100 0. There is also a very important operation: Void Swap (Vector & V) through (); used to exchange two values of two kinds of vectors. It is characterized by fast (only three pointers in the inside), do not produce an exception. This is very useful when writing some programs that guarantee an abnormal security. In fact, swap () is basically used as a basic operation that is similar to the "value" type similar to Operator = (), :: std :: swap () should also be specialized, call for user-defined types The corresponding class member SWAP () function: Struct MyVal { // Blah Blah. Void swap (myval&); } Namespace std { Template <> Void Swap (MyVal & A, MyVal & B) {a.swap (b);} } Regarding SWAP (), it is worthwith discussion. Here we only point out, Vector 11. Storage management strategy when using VECTOR As can be seen from the previous introduction, the automatic storage assignment of the Vector is an exponentially added storage space and never reduces the assigned space. This is suitable in most cases. If the application knows the number of elements you want to use in advance, you can call RESERVE () to keep (assign) space, which avoids unnecessary redistribution and element copy when adding elements in advance: INTVECTOR V; v.reserve (100); For (int i = 0; i <100; i) v.push_back (i); Please note that reserve () and resize () are essentially different. Reserve (n) remains unused and the original space that can be used, and resize (n) is really created N objects: INTVECTOR V; v.resize (100); // V already contains 100 0. For (int i = 0; i <100; i) v [i] = i; / / can assign Sometimes, a Vector may grow to a more elements, then reduce the number of elements, then, it may be desirable to reduce the space allocated by the VECTOR to save memory. Freeextra () is provided in Carray <>, but Vector <> does not provide a corresponding function. Copy must be performed at this time: INTVECTOR (V) .SWAP (V); There is a view that the copy constructor also copies Capacity (), and the standard is not clearly pointed out in this, so the safer method is IntVector (v.begin (), v.end ()). Swap (v); If you have a number of elements that may be stored in a Vector (for example, more than 100), and you cannot determine the number in advance (therefore unable to call RESERVE ()), then usually the vector is not an appropriate data structure, should be considered :: std :: deve <>. Compared with Vector <>, the storage space behind it is continuous (so the application in WaitFormultipleObjects () above cannot be replaced by demine
