vector definition
Vector: a data structure in C + +, specifically a class It is equivalent to a dynamic array. When programmers cannot know the size of the array they need, using it to solve the problem can achieve the purpose of maximum space saving
Usage:
1. The document includes:
First, add #include at the beginning of the program to contain the required class file vector
Add using namespace std;
2. Variable declaration:
2.1 example: declare an int vector to replace a one-dimensional array:
vector a; (it is equal to declaring an int array a [], the size is not specified, and can be dynamically added and deleted).
2.2 example: replace two-dimensional array with vector In fact, just declare a one-dimensional array vector, and the name of an array actually represents its first address, so just declare a vector of an address, that is: vector < int > A. It is the same as replacing a three-dimensional array with an ideal vector, vector < int * > A; Then go up and so on
3. Specific usage and function call:
3.1 how to get the elements in the 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 adds a data at the end of the array
2.pop_back removes the last data of the array
3.at get the data of the number position
4.begin to get the pointer of the array header
5.end get the pointer of the last cell + 1 of the array
6. front get the reference of array header
7.back get the reference of the last cell of the array
8.max_size gets the maximum size of the vector
9.capacity the size allocated by the current vector
10.size size of currently used data
11.resize changes the size of the currently used data. If it is larger than the currently used data, the user fills in the default value
12.reserve changes the size of the space allocated by the current vecotr
13.erase deletes the data item pointed to by the pointer
14.clear clear the current vector
15.rbegin returns the start pointer after reversing the vector (in fact, it is the original end-1)
16.rend returns the end pointer of the vector inversion construct (in fact, it is the original begin-1)
17.empty judge whether the vector is empty
18.swap exchanges data with another vector
3.2 detailed functions:
Where vector c
c.clear() removes all data from the container.
c.empty() determines whether the container is empty.
c.erase(pos) deletes the data at the pos location
c.erase(beg,end) deletes the data in the [beg,end) interval
c.front() returns the first data.
c.insert(pos,elem) inserts an elem copy in the pos position
c.pop_back() deletes the last data.
c.push_back(elem) adds a data to the tail.
c.resize(num) resizes the container
c.size() returns the number of actual data in the container.
c.begin() returns an iterator that points to the first element of the container
c.end() returns an iterator that points to the last element of the container
4. Memory management and efficiency
1>use reserve()Function to set the capacity in advance to avoid inefficiency caused by multiple capacity expansion operations.
about STL Containers, one of the most praiseworthy features is that they can automatically grow enough to hold the data you put in as long as they do not exceed their maximum size. (to know the maximum value, just call max_size Member functions of.) about vector and string，If more space is needed, use a similar realloc To grow in size. vector The container supports random access, so in order to improve efficiency, it is implemented internally by using dynamic array. In passing reserve() To apply for a specific size, always increase its internal buffer according to the exponential boundary. When carried insert or push_back When adding elements, if the memory of the dynamic array is not enough at this time, it is necessary to dynamically reallocate 1 of the current size.5~2 Times the new memory area, and then copy the contents of the original array. Therefore, in general, its access speed is the same as that of general arrays. Its performance will decline only when reallocation occurs. As the code above tells you. And carry out pop_back During operation, capacity Not because vector The number of elements in the container decreases, and it will maintain the size before operation. about vector For containers, if there is a large amount of data to be processed push_back，Should use reserve()Function sets its capacity in advance, otherwise many capacity expansion operations will occur, resulting in low efficiency.
reserve Member functions allow you to minimize the number of reallocations that must be made, thus avoiding the overhead of true allocation and iterators/Pointer/Invalid reference. But before I explain reserve Before I explain why I can do that, 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() tells 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, not how many more. If you want to know how much unused memory is in a vector or string, you must subtract size() from capacity(). If size and capacity return the same value, there will be no space left in the container, and the next insertion (through insert or push_back, etc.) will trigger the above reallocation step.
(3) resize(Container::size_type n) forces the container to hold n elements. After calling resize, size will return n. If n is smaller than the current size, the element at the end of the container will be destroyed. If n is larger than the current size, the new default constructed element is added to the end of the container. If n is greater than the current capacity, reallocation occurs before the element is added.
(4) reserve(Container::size_type n) forces the container to change its capacity to at least N, and the provided n is not less than the current size. This typically forces a reallocation because capacity needs to be increased. (if n is smaller than the current capacity, vector ignores it and the call does nothing. String may reduce its capacity to the larger number in size() and N, but the size of string does not change. In my experience, using reserve to trim excess capacity from a string is generally not as good as using the "exchange technique", which is the subject of Clause 17.)
This introduction shows that as long as there are elements to be inserted and the capacity of the container is insufficient, reallocation will occur (including the original memory allocation and recycling maintained by them, the copy and destruction of objects, and the invalidation of iterators, pointers and references). Therefore, the key to avoiding reallocation is to use reserve Set the capacity of the container to be large enough as soon as possible, preferably immediately after the container is constructed.
For example, suppose you want to create a vector that holds 1-1000 values. Instead of using reserve, you can do something like this:
vector v;
for (int i = 1; i <= 1000; ++i) v.push_back(i);
In most STL implementations, this code will result in 2 to 10 reassignments during the loop. (there's nothing strange about the number of 10. Remember that vector usually doubles the capacity when reallocation occurs, and 1000 is about 210.)
Change the code to use reserve, and we get this:
vector v;
v.reserve(1000);
for (int i = 1; i <= 1000; ++i) v.push_back(i);
This does not reallocate in the loop.
The relationship between size and capacity allows us to predict when insertion will cause vector or string reallocation, and when insertion will invalidate iterators, pointers and references to containers. For example, given this code,
string s;
...
if (s.size() < s.capacity()) {
s.push_back('x');
}
push_ The call to back does not invalidate iterators, pointers, or references to this string, because the capacity of the string is guaranteed to be greater than its size. If not, execute push_back, if the code inserts a string at any position, we can still ensure that there is no reallocation during the insertion. However, consistent with the general rule of iterator failure during string insertion, all iterators / pointers / references from the insertion position to the end of the string will fail.
Returning to the main idea of this article, there are usually two cases where reserve is used to avoid unnecessary redistribution. The first available case is when you know exactly or approximately how many elements will last appear in the container. In that case, like the vector code above, you just reserve an appropriate amount of space in advance. The second scenario is to reserve the maximum space you may need, and then trim any excess capacity once you have added all the data.
2>Use the "exchange technique" to trim vector Excess space/Memory There is a way to reduce it from its once maximum capacity to the capacity it needs now. This method of reducing capacity is often referred to as "shrink to fit."( shrink to fit)". This method requires only one statement: vector<int>(ivec).swap(ivec);
The expression vector(ivec) creates a temporary vector, which is a copy of ivec: the copy constructor of vector does this work. However, the copy constructor of vector only allocates the memory required by the copied elements, so this temporary vector has no extra capacity. Then we let the temporary vector and ivec exchange data. At this time, we have completed that the ivec has only the trimmed capacity of the temporary variable, and the temporary variable holds the unused excess capacity in the ivec. Here (at the end of this statement), the temporary vector is destroyed, thus freeing the memory previously used by ivec and shrinking to the appropriate size.
3>use swap Method forced release STL Vector Memory occupied
template < class T> void ClearVector( vector& v )
{
vectorvtTemp;
vtTemp.swap( v );
}
as
vector v ;
nums.push_back(1);
nums.push_back(3);
nums.push_back(2);
nums.push_back(4);
vector().swap(v);
/*Or v.swap(vector())*/
/Or {std::vector tmp = v; v.swap(tmp);}// The parenthesis {} is used to automatically destruct tmp when it exits {}/
5. Behavior test of vector memory management member function
C++ STL of vector It is widely used, but there have been many guesses about its memory management model. The following example code test is used to understand its memory management mode. The test code is as follows:
#include
#include
using namespace std;
int main()
{
vector iVec;
Cout < < container size is: < < ivec size() << endl;
Cout < < container capacity is: < < ivec capacity() << endl; // 1 element, container capacity 1
iVec.push_back(1);
Cout < < container size is: < < ivec size() << endl;
Cout < < container capacity is: < < ivec capacity() << endl; // 2 elements, container capacity 2
iVec.push_back(2);
Cout < < container size is: < < ivec size() << endl;
Cout < < container capacity is: < < ivec capacity() << endl; // 3 elements, container capacity 4
iVec.push_back(3);
Cout < < container size is: < < ivec size() << endl;
Cout < < container capacity is: < < ivec capacity() << endl; // 4 elements, container capacity 4
iVec.push_back(4);
iVec.push_back(5);
Cout < < container size is: < < ivec size() << endl;
Cout < < container capacity is: < < ivec capacity() << endl; // 5 elements, container capacity 8
iVec.push_back(6);
Cout < < container size is: < < ivec size() << endl;
Cout < < container capacity is: < < ivec capacity() << endl; // 6 elements, container capacity 8
iVec.push_back(7);
Cout < < container size is: < < ivec size() << endl;
Cout < < container capacity is: < < ivec capacity() << endl; // 7 elements, container capacity 8
iVec.push_back(8);
Cout < < container size is: < < ivec size() << endl;
Cout < < container capacity is: < < ivec capacity() << endl; // 8 elements, container capacity 8
iVec.push_back(9);
Cout < < container size is: < < ivec size() << endl;
Cout < < container capacity is: < < ivec capacity() << endl; // 9 elements, container capacity 16
/*vs2005/8 capacity growth is not doubled, such as
9 elements capacity 9
10 elements capacity 13*/
/*Test special swap() in effective stl*/
Cout < < current vector size is: < < ivec size() << endl;
Cout < < current vector capacity is: < < ivec capacity() << endl;
vector(iVec).swap(iVec);
Cout < < the size of the temporary vector object is: < < (vector (ivec)) size() << endl;
Cout < < the capacity of the temporary vector object is: < < (vector (ivec)) capacity() << endl;
Cout < < after the exchange, the size of the current vector is: < < ivec size() << endl;
Cout < < after switching, the capacity of the current vector is: < < ivec capacity() << endl;
return 0;
}
6. Other member functions of vector
c.assign(beg,end): take[beg; end)The data in the interval is assigned to c.
c.assign(n,elem): take n individual elem Assign a copy of to c.
c.at(idx): Return index idx The data referred to, if idx Cross the line, throw out_of_range.
c.back(): Return the last data without checking whether the 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 and free up memory.
Other uses of vector
Internal sorting
Sort function is used to sort the internal elements of the entire vector variable
eg:
vector<string> classesname_x_second; //Forward sort: sort from small to large sort(classesname_x_second.begin(), classesname_x_second.end()); //Reverse sort: sort from large to small sort(classesname_x_second.rbegin(), classesname_x_second.rend());
Internal element exchange location
Swap (initial position, new position)
eg:
result_up[j] and result_up[j+1] exchange position
swap(result_up[j], result_up[j+1]);
Delete element
erase() can delete either the element indicated by an iterator or an element of a specified range.
You can also use the general algorithm remove() to delete the elements in the vector container,
The difference is that using remove generally does not change the size of the container, but pop_ Member functions such as back () and erase() change the size of the container.
erase
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
erase:
The erase function can be used to delete one or a segment of elements in the vector container. When deleting an element, its parameters are iterators pointing to the corresponding element, while when deleting a segment of elements, its parameters are iterators pointing to the beginning of a segment of elements and iterators pointing to the next element of the end element.
After a single element is deleted, the direction of the incoming iterator remains unchanged and still points to the position of the deleted element, while all elements after the deleted element move forward by one bit, that is, the iterator actually points to the next element of the original deleted element. In fact, the vector also maintains a last pointer. At the beginning, it = end. With deletion, the last moves forward. Finally, the size of the vector is last begin, or we can think that the end value has changed, but the initially passed in end has not changed.
Use case:
vector<int>::iterator itr = v.begin();
while (itr!=v.end())
{
if (*v==1)
{
v.erase(itr);
}
itr++;//Here, the iterator will update error after deletion
}
The above code is wrong,
Because after deleting an element, the iterator has pointed to the next element of the deleted element, and then itr + + will appear a wild pointer.
That is, VECI After erase (iter), the state of iter is uncertain. Is there any reason why it doesn't crash when you use + + again?!
The correct code is
vector<int>::iterator itr = v.begin();
while (itr!=v.end())
{
if (*v==1)
{
itr=v.erase(itr);
}
else
itr++;
}
That is, if there is no erase operation, point the iterator to the next element.
After deleting an element, the direction of the passed iterator remains unchanged, still pointing to the original position when it was passed in. What is modified is the position of the element behind the deleted segment. The elements after the deleted segment are moved forward. The deleted segment is replaced by the next element of the deleted segment.
remove:
The remove() algorithm is generated by the template defined in the algorithm header file, which can delete a segment of elements that match a specific value
iterator remove(iterator first, iterator last，val);
The remove function moves all values equal to val in the range
In STL, remove () only moves the element after the element to be deleted to the front end of the vector, not deletes it. To actually remove, you need to use erase() in conjunction with it.
The function of remove in vector is to put the element equal to value at the end of the vector, but does not reduce the size of the vector. STL and vector express the same meaning.
After removing, a new end () iterator is returned, but the value of the end () iterator of the original array is not changed. The element with a value equal to Val in the range is replaced by the latter element. That is, the values from the new end() to the original end() in the original array are still the values of the original array (equal to the value of VAL), but this part of the state is unreliable. The part from begin() to the new end () is not equal to val.
difference:
That is, the difference between erase and remove lies in whether the size of the executed vector will change due to the different return values after the function is executed
The function of erase in vector is to delete the element in a position or a section of area (begin, end), reduce its size, and return the position of the next element of the deleted element.
The function of remove in vector is to remove all the values in the range of val to the back and return a new end() value (end of non val part), but the end of the original vector passed in has not changed, so the size has not changed
Combined application of the two:
Delete the element with the value x in the vector
vec.erase(remove(vec.begin(),vec.end(),x),vec.end());
See leetcode26 for details
Only one duplicate element is reserved, and the duplicate element is removed in place.
Idea: you can replace the duplicate elements with a special value, and then delete the special value uniformly.
class Solution {
public:
int removeDuplicates(vector& nums) {
if(nums.size()==0)
return 0;
int res=1;
int flag=nums[0];
for(int i=1;i<nums.size();i++)
{
if(nums[i]==flag)
nums[i]=INT_MAX;
else
{
flag=nums[i];
}
}
nums.erase(remove(nums.begin(),nums.end(),INT_MAX),nums.end());
return nums.size();
}
};
pop_back()
Delete the element at the end of the container. For example:
std::vector data(100, 99); // Contains 100 elements initialized to 99
data.pop_back(); // Remove the last element
clear()
Delete all elements. For example:
std::vector data(100, 99);// Contains 100 elements initialized to 99
data.clear(); // Remove all elements
eg:
#include <algorithm>
#include <vector>
#include <iostream>
#include <iterator>
using namespace std;
typedef struct rect //Define structure
{
int id;
int length;
int width;
rect(int i,int l ,int w):id(i),length(l),width(w){};
} Rect;
int main()
{
Rect rect(1,2,3);
vector<Rect> vec(2,rect);//Define a vec container with 2 elements rect
Rect rect2(3,3,4);
vec.push_back(rect2);
Rect rect3(4,5,7);
vec.push_back(rect3);
Rect rect4(6,3,4);
vec.push_back(rect4);
/**********************Traverse output before deleting****************************/
for(vector<Rect>::iterator it=vec.begin();it!=vec.end();++it){
cout<<(*it).id<<','<<(*it).length<<','<<(*it).width<<endl;
}
/**********************Delete****************************/
for(vector<Rect>::iterator it=vec.begin();it!=vec.end();){
Rect temp=*it;
if(temp.id==4){
it=vec.erase(it); //Delete the element, and the return value points to the next position of the deleted element
}
else
++it;
}
cout<<"/***********split*************/"<<endl;
/**********************Traverse the output after deletion***************************/
for(size_t i=0;i!=vec.size();++i){
cout<<vec[i].id<<" "<<vec[i].length<<" "<<vec[i].width<<endl;
}
return 0;
}
actual combat
The meaning of the question is the ranking system of acm.
#include <bits/stdc++.h>
using namespace std;
typedef struct node {
int date,peer;
} ty;
bool rule( ty a, ty b ) // Simple custom function of sort
{
if ( a.date!=b.date ) {
return a.date>b.date;
}
return a.peer<b.peer;
}
int main()
{
vector <node> a;
int n;
ty t;
cin >> n;
for ( int i=0; i<n; i++ ) {
cin >> t.date>>t.peer;
a.push_back(t); // Insert in vector
}
sort(a.begin(),a.end(),rule); // Sort sort of vector
vector<node>::iterator p; // Iterator for vector
for ( p=a.begin(); p!=a.end(); p++ ) {
cout << p->date << " " << p->peer << endl; // Use of iterators
}
return 0;
}
Original link: https://blog.csdn.net/weixin_43828245/article/details/90243175
vector<bbox_t> result_vec;
//Screening test results with accuracy greater than 90%
vector<bbox_t>::iterator itr = result_vec.begin();
for (itr = result_vec.begin(); itr != result_vec.end(); itr++)
{
bbox_t temp = *itr;
if(temp.prob < 0.9)
result_vec.erase(itr); //Delete the second element
}
Deletes the specified id element
int id_prob;
for (int k2 = 0; k2 < classesname_xup_second.size(); k2++)
{
if (classesname_xup_second[k2 + 1] - classesname_xup_second[k2] < 8) //The same character is judged twice
{
if (result_up_prob[k2] < result_up_prob[k2 + 1])
id_prob = k2;
else
id_prob = k2+1;
result_up.erase(result_up.begin() + id_prob);
}
}
CString insert element
v2.insert(v2.begin()+4, L"3"); //Inserts an element at a specified location, such as before the fifth element v2.insert(v2.end(), L"3"); //Insert an element at the end v2.push_back(L"9"); //Insert an element at the end v2.insert(v2.begin(), L"3"); //Insert an element at the beginning
Some problems in the process of using vector are listed and discussed:
1)
vector <int > a;
int b = 5;
a.push_back(b);
At this time, if yes b In addition, assignment will not affect a[0]Value of
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; //Free b's address space
for(int i=0 ; i <3 ; i++)
{
cout<<a[0][i]<<endl;
}
The output value at this time is not the beginning b Array initialization value,But some unpredictable values.
analysis:According to 1) 2)Results,Can think of,At 1)in, to a What the vector pushes in is b Value of,Namely a[0]=b,here a[0]and b Is stored in two different addresses.So change b The value of does not affect a[0];And in 2)in,Because it's an address(Pointer)Press in vector a,Namely a[0]=b,So it was released b Your address will be released a[0]Address of,therefore a[0]The value stored in the array is also unknown.