Examples of use :std::vector<std::string> xmlNodeList;

Let's introduce --

vector( vector ): C++ A data structure in , It's exactly a class . It is equivalent to a dynamic array , When programmers can't know the size of the array they need , Using it to solve the problem can achieve the purpose of saving the most space .

usage :

1. File contains :

First add... At the beginning of the program #include<vector> To include the required class files vector

And it must be added using namespace std;

2. Variable declarations :

2.1 example : Make a statement int Vector to replace one-dimensional array :vector <int> a;( It's like declaring a int Array a[], The size is not specified , It can be added and deleted dynamically ).

2.2 example : use vector Instead of a two-dimensional array . In fact, just declare a one-dimensional array vector , The name of an array actually represents its first address , So just declare a vector of addresses , namely :vector <int *> a. It's the same as ideal vector instead of three-dimensional array ,vector <int**>a; And so on and so on .

3. Specific usage and function call :

3.1 How to get the elements in a vector ? Its usage is the same as array :

for example :

vector <int *> a

int b = 5;

a.push_back(b);// This function is explained in detail below

cout<<a[0];       // The output is 5

1.push_back   Add a data at the end of the array
2.pop_back    Remove the last data of the array  
3.at                Get the data of the number position
4.begin           Get a pointer to the array header
5.end             Get the last cell of the array +1 The pointer to
6.front        Get a reference to the array header
7.back            Get a reference to the last cell of the array
8.max_size     obtain vector The biggest is how big
9.capacity       At present vector The size of the allocation
10.size           The size of the data currently used
11.resize         Change the size of the currently used data , If it's bigger than what's currently in use , Fill in the default value
12.reserve      To change the current vecotr The size of the space allocated
13.erase         Delete the data item that the pointer points to
14.clear          Clear the current vector
15.rbegin        take vector The reverse start pointer returns ( In fact, it is the original end-1)
16.rend          take vector The end pointer of the reverse construct returns ( In fact, it is the original begin-1)
17.empty        Judge vector Is it empty
18.swap         And another vector Exchange data

3.2   Detailed function implementation function : among vector<int> c.

c.clear()          Remove all data from container .

c.empty()          Judge whether the container is empty .

c.erase(pos)         Delete pos Location data

c.erase(beg,end)  Delete [beg,end) Interval data

c.front()          Send back the first data .

c.insert(pos,elem)   stay pos Insert a elem Copy

c.pop_back()      Delete the last data .

c.push_back(elem)  Add a data at the end .

c.resize(num)      Reset the size of the container

c.size()          Number of actual data returned to the container .

c.begin()            Returns the iterator that points to the first element of the container

c.end()              Returns the iterator pointing to the last element of the container

4. Memory management and efficiency

1》 Use reserve() Function sets the capacity in advance , Avoid inefficiency caused by multiple capacity expansion operations .

About STL Containers , One of the most laudable features is that as long as they don't exceed their maximum size , They can automatically grow enough to hold the data you put in .( To know the maximum value , Just call max_size Member function of .) about vector and string, If more space is needed , Just like realloc To grow in size .vector The container supports random access , So in order to improve efficiency , It's implemented internally using dynamic arrays . Through reserve() To apply for a specific size, the internal buffer is always increased according to the exponential boundary . When doing insert or push_back And so on , If the memory of dynamic array is not enough at this time , It is necessary to reallocate the current size dynamically 1.5~2 Times of new memory , Then copy the contents of the original array . therefore , In general , Its access speed is the same as that of general arrays , Only when redistribution happens , The performance will be degraded . As the code above tells you . And pop_back In operation ,capacity Not because vector The elements in the container decrease and then decrease , It also maintains the size before the operation . about vector For containers , If there's a lot of data to do push_back, Should be used reserve() Function sets its capacity in advance , Otherwise, there will be many capacity expansion operations , It leads to inefficiency .

reserve Member functions allow you to minimize the number of redistribution that must be made , Thus, the overhead of true allocation and iterators can be avoided / The pointer / Citation failure . But before I explain reserve Why can you do that before , Let me briefly introduce four related member functions that are sometimes confusing . In standard containers , Only vector and string All of these functions are provided .

(1) size() Tell you how many elements are in the container . It doesn't tell you how much memory the container allocates for the elements it holds . 
(2) capacity() Tells you how many elements the container can hold in its allocated memory . That's how many elements the container can hold in that memory , It's not how many more elements it can hold . If you want to know one vector or string How much unoccupied memory is in , You have to go from capacity() Subtract from size(). If size and capacity Return the same value , There's no space left in the container , And the next insert ( adopt insert or push_back etc. ) Will trigger the redistribution step above .
(3) resize(Container::size_type n) Force the container to hold n Elements . call resize after ,size Will return n. If n Smaller than the current size , The elements at the end of the container are destroyed . If n Larger than the current size , The elements of the new default construction are added to the end of the container . If n Greater than current capacity , Redistribution occurs before elements are added .
(4) reserve(Container::size_type n) Force the container to change its capacity to at least n, Provided n Not less than the current size . This generally forces a redistribution , Because the capacity needs to be increased .( If n Less than the current capacity ,vector Ignore it , This call does nothing ,string Maybe reduce its capacity to size() and n Medium and large numbers , but string There's no change in the size of . In my experience , Use reserve Come from a string In general, it is not as good as using the surplus capacity in the process of trimming “ Exchange skills ”, That's the clause 17 The theme of .)

This introduction indicates that reallocation occurs whenever there are elements to be inserted and the capacity of the container is insufficient ( Including the raw memory allocation and recycling they maintain , Copy and Deconstruction of objects and iterators 、 Invalidation of pointers and references ). therefore , The key to avoiding redistribution is to use reserve Set the capacity of the container as large as possible , It's best to do it immediately after the container is constructed .

for example , Suppose you want to build an accommodation 1-1000 It's worth it vector<int>. Not used reserve, You can do it like this :

vector<int> v;
for (int i = 1; i <= 1000; ++i) v.push_back(i);
In most STL In the implementation , This code will result in 2 To 10 Redistribution .(10 There's nothing strange about this number . remember vector When reallocation occurs, capacity is usually doubled , and 1000 About equal to 210.)

Change the code to use reserve, We get this :

vector<int> v;
v.reserve(1000);
for (int i = 1; i <= 1000; ++i) v.push_back(i);
This is not reallocated in the loop .

The relationship between size and capacity allows us to predict when insertion will cause vector or string Perform redistribution , and , You can predict when the insertion will point to the iterator in the container 、 Pointer and reference failure . for example , Give this code ,

string s;
...
if (s.size() < s.capacity()) {
s.push_back('x');
}
push_back The call to will not point to this string Iterators in 、 Invalid pointer or reference , because string Its capacity is guaranteed to be larger than its size . If it's not execution push_back, Code in string Any position of a insert, We can still guarantee that there is no reallocation during insertion , however , Accompany with string The general rule of iterator invalidation at insertion time is the same , All from insertion position to string The iterator at the end / The pointer / The reference will be invalid .

Back to the main idea of this clause , There are usually two situations to use reserve To avoid unnecessary redistribution . The first available case is when you know exactly or approximately how many elements will end up in the container . In that case , Just like up here vector Code , You're just ahead of time reserve The right amount of space . The second is to keep as much space as you may need , then , Once you've added all the data , Trim out any excess capacity .

2》 Use “ Exchange skills ” To fix it vector Excess space / Memory

There's a way to reduce it from its maximum capacity to the capacity it needs now . This method of reducing capacity is often called “ Shrink to fit (shrink to fit)”. This method only needs one statement :vector<int>(ivec).swap(ivec);
expression vector<int>(ivec) Create a temporary vector, It is ivec A copy of :vector The copy constructor of does this work . however ,vector The copy constructor of allocates only the memory needed by the copied elements , So this temporary vector There's no extra capacity . And then we let the temporary vector and ivec Exchange data , And then we finished ,ivec Only the trimmed capacity of the temporary variable , And this temporary variable holds what used to be in ivec Unused excess capacity in . ad locum ( This statement ends with ), temporary vector Be destroyed , So let go of the old ivec Memory used , Shrink to fit .

3》 use swap Methods to force release STL Vector Memory occupied

template < class T> void ClearVector( vector<T>& v )

    vector<T>vtTemp;
    vtTemp.swap( v );

Such as  
    vector<int> v ;
    nums.push_back(1);
    nums.push_back(3);
    nums.push_back(2);
    nums.push_back(4);
    vector<int>().swap(v);

/* perhaps v.swap(vector<int>()); */

/* perhaps { std::vector<int> tmp = v;   v.swap(tmp);   }; // Parentheses { } It's Jean tmp sign out { } It's automatically destructed */

5.Vector Behavior test of memory management member function

C++ STL Of vector Very widely used , But there has been a lot of speculation about its memory management model , Next, use the example code test to understand its memory management mode , The test code is as follows :

#include <iostream>
#include <vector>
using namespace std;

int main()
{
vector<int> iVec;
cout << " Containers The size is : " << iVec.size() << endl;
cout << " Containers Capacity of : " << iVec.capacity() << endl; //1 Elements , The capacity of the container is 1

iVec.push_back(1);
cout << " Containers The size is : " << iVec.size() << endl;
cout << " Containers Capacity of : " << iVec.capacity() << endl; //2 Elements , The capacity of the container is 2

iVec.push_back(2);
cout << " Containers The size is : " << iVec.size() << endl;
cout << " Containers Capacity of : " << iVec.capacity() << endl; //3 Elements , The capacity of the container is 4

iVec.push_back(3);
cout << " Containers The size is : " << iVec.size() << endl;
cout << " Containers Capacity of : " << iVec.capacity() << endl; //4 Elements , The capacity of the container is 4

iVec.push_back(4);
iVec.push_back(5);
cout << " Containers The size is : " << iVec.size() << endl;
cout << " Containers Capacity of : " << iVec.capacity() << endl; //5 Elements , The capacity of the container is 8

iVec.push_back(6);
cout << " Containers The size is : " << iVec.size() << endl;
cout << " Containers Capacity of : " << iVec.capacity() << endl; //6 Elements , The capacity of the container is 8

iVec.push_back(7);
cout << " Containers The size is : " << iVec.size() << endl;
cout << " Containers Capacity of : " << iVec.capacity() << endl; //7 Elements , The capacity of the container is 8

iVec.push_back(8);
cout << " Containers The size is : " << iVec.size() << endl;
cout << " Containers Capacity of : " << iVec.capacity() << endl; //8 Elements , The capacity of the container is 8

iVec.push_back(9);
cout << " Containers The size is : " << iVec.size() << endl;
cout << " Containers Capacity of : " << iVec.capacity() << endl; //9 Elements , The capacity of the container is 16
/* vs2005/8 Capacity growth is not doubling , Such as  
    9 Elements    Capacity 9 
    10 Elements Capacity 13 */

/* test effective stl A special exchange in swap() */
cout << " At present vector The size is : " << iVec.size() << endl;
cout << " At present vector The capacity of is : " << iVec.capacity() << endl;
vector<int>(iVec).swap(iVec);

cout << " temporary vector<int> object The size is : " << (vector<int>(iVec)).size() << endl;
cout << " temporary vector<int> object The capacity of is : " << (vector<int>(iVec)).capacity() << endl;
cout << " After exchanging , At present vector The size is : " << iVec.size() << endl;
cout << " After exchanging , At present vector The capacity of is : " << iVec.capacity() << endl;

return 0;
}

6.vector Other member functions of

c.assign(beg,end): take [beg; end) The data in the interval is assigned to c.
        c.assign(n,elem): take n individual elem The copy of is assigned to c. 
        c.at(idx): Return index idx The data , If idx Transboundary , Throw out out_of_range. 
        c.back(): Send back the last data , Don't check if this data exists .
        c.front(): Return a data . 
        get_allocator: Use the constructor to return a copy . 
        c.rbegin(): Returns the first data in a reverse queue . 
        c.rend(): Returns the next location of the last data in a reverse queue . 
        c.~ vector <Elem>(): Destroy all data , Free memory .

7. remarks : In use vector Some of the problems in the process , Here is a list of the discussions :

1)

vector <int > a;

int  b = 5;

a.push_back(b);

If you are right at this time b In addition, the assignment does not affect a[0] Value

2)

vector <int*> a;
                     int *b;
                     b= new int[4];
                     b[0]=0;
                     b[1]=1;
                     b[2]=2;
                     a.push_back(b);
                     delete b;          // Release b Address space of
                     for(int i=0 ; i <3 ; i++)
                     {
                           cout<<a[0][i]<<endl;
                     }

The output value is not at the beginning b The value of array initialization , It's some unexpected value .

analysis : according to 1) 2) Result , You can think of , stay 1) in ,   Go to a The vector press in is b Value , namely a[0]=b, here a[0] and b It's stored in two different addresses . So change b The value of does not affect a[0]; And in the 2) in , Because it's putting an address ( The pointer ) Press in the vector a, namely a[0]=b, So released b The address of is also released a[0] The address of , therefore a[0] The value stored in the array is unknown .

c++ Of vector More articles about

  1. c++ vector Use

    1. Contains a header file : 1 #include <vector> 2. Declare and initialize : std::vector<int> first; // empty vector of in ...

  2. Vector Tile

    Mapbox Vector Tile Specification A specification for encoding tiled vector data. <?XML:NAMESPACE ...

  3. ArrayList、Vector、LinkedList The difference between ?

    1.ArrayList.Vector.LinkedList Classes are java.util In bag , Are all scalable arrays . 2.ArrayList and Vector The bottom layer is implemented by arrays , therefore , Index data fast , Delete . Insert data slowly . ...

  4. ArrayList、Vector、HashMap、HashSet Default initial capacity of 、 Load factor 、 Expansion increment

    When the underlying implementation involves expansion , Container or reallocate a larger contiguous memory ( In the case of discrete allocation, there is no need to reallocate , Discrete allocation is the dynamic allocation of memory when new elements are inserted ), To copy all the original data of the container to the new memory , This undoubtedly reduces efficiency greatly . Load because ...

  5. Java in Vector and ArrayList The difference between

    Let's start with the realization of both types List Interface , and List There are three implementation classes for the interface , Namely ArrayList.Vector and LinkedList.List Used to store multiple elements , Be able to maintain the order of elements , And allow the repetition of elements .3 Specific ...

  6. C++ Use vector

    #include <iostream> #include <string> #include <vector> using namespace std; void ...

  7. [LeetCode] Flatten 2D Vector Flatten the two-dimensional vector

    Implement an iterator to flatten a 2d vector. For example,Given 2d vector = [ [1,2], [3], [4,5,6] ] ...

  8. C++ Array array And vector Comparison

    turn :http://blog.csdn.net/yukin_xue/article/details/7391897 1. array When defining, you must define the number of elements in the array ; and vector Unwanted : And can only pack ...

  9. vector Define initialization

    The header file #include<vector> using std::vector; vector<T> v1; vector<T> v2(v1); vector< ...

  10. vector Iterator usage

    #include<iostream> #include<vector> using namespace std; int main() { vector<int> ...

Random recommendation

  1. PHP Turn on cURL function

    PHP Turn on cURL function stay php.ini In the open determine php The extended directory has php_curl.dll Class library stay php.int Find the directory of the extension library in Judge if there is any in the directory php_curl.dll If not, search and download ...

  2. ScrollMagic – cool ! Amazing page scrolling interaction effect

    ScrollMagic Is a jQuery plug-in unit , It allows you to use the scroll bar like a progress bar . If you want to start an animation at a specific roll position , And let the animation synchronize the action of the scroll bar , Or glue elements to a specific roll position , So this plug-in ...

  3. The first 10 Chapter Synchronous devices I/O And asynchronous devices I/O(2)_ Sync IO And asynchronous IO Basics

    10.3 Execute synchronization device I/O (1) Functions that read and write to the device ①ReadFile/WriteFile function Parameters describe hFile File handle pvBuffer Point to the buffer to receive the file data or write the buffer data to the setting ...

  4. chrome modify UserAgent, debugging

    chrome Browser emulation UserAgent, Debugging the mobile environment . https://chrome.google.com/webstore/detail/user-agent-switcher-for-c/dj ...

  5. to 360 Six pieces of advice ( No remote login , Ordinary users 500G Enough )

    Personally feel ,360 Even a small improvement of cloud disk , It's not as good as it is now , The last six suggestions ! 1. Get a real name system , Double binding of ID card and mobile phone number , Each person is limited to one account . 2. All sharing functions of cloud disk are prohibited , It's closed , Personal cloud disk data other people ...

  6. web In the process of development, the value is transferred from the front end to the back end

    stay JavaScript in , Pay attention to the value transfer between pages . such as , We go through url When passing a number to the next page , Go to the next page for parsing, and it may be a string . This leads to a phenomenon . During debugging , I found that the value I wanted to pass was indeed passed ...

  7. Use dns Batch management common host name related issues

    1.dns To configure In the process of daily management of the host , There will be many places where you need to use the host name , When there are so many hosts , It is not suitable for use hosts To manage and synchronize all hosts hosts 了 , It can be used at this time dns To manage host name mapping and changes dns ...

  8. be based on div Forms simulate right alignment

    be based on div Forms simulate right alignment --------------------------------------------------------- ----------------------------- ...

  9. Android Development Notes

    11.android Use global variables Definition Data Class inheritance Application stay manifest.xml In a statement http://blog.csdn.net/feiyangxiaomi/article/de ...

  10. Linux Subnet mask calculation , Binary to decimal conversion

    Look at the example below 192.168.0.1/24 192.168.0.1/32 192.168.0.1/28 above 24,32,28 What are the corresponding masks , How does it work 24,32,28, The corresponding number is the number of binary 1 ...