All about vector STL in c++ for competitive programming( initialization, traversal and methods/functions ) :
vector STL
Important Points:
- It is a sequence container and also known as dynamic array.
- It's size can grow and shrink dynamically.
- There's no need to provide size at compile time.
- Remember to use the header file #include<vector> before using vector STL.
Advantages of using vector over array:
- vector is dynamic in nature so, size automatically increases with insertion of elements.
- array is fixed size, once initialized can't be resized but vector can.
- Reserve space can be given for vector, whereas for arrays you cannot give reserved space.
- vectors can store any type of objects, whereas an array can store only homogeneous values.
- Multiple objects can be stored in vector.
- Elements can be deleted in vector.
Disadvantages of vector over array:
- vector occupies more memory.
- vector takes more time in accessing elements.
- array is more appropriate for storing a fixed no. of elements.
- array support efficient random access to the members.
- It is easy to sort an array.
Different ways to initialize a vector STL
1. declaring a vector and using push_back( ) method to put elements into it :
vector < int > vec ;
vec.push_back( 10 ) ;
vec.push_back( 20 ) ;
vec.push_back( 30 ) ;
vec.push_back( 10 ) ;
vec.push_back( 20 ) ;
vec.push_back( 30 ) ;
2. filling a vector with the same specified element :
Suppose we want a vector of size 3 and it's every element is 10
Therefore,
vector < int > vec( 3, 10 ) ;
3. Initializing like arrays:
vector < int > vec{ 10, 20, 30 } ;
4. Initializing from an array:
int arr[ ] = { 10, 20, 30 };
int n = sizeof(arr) / sizeof(arr[0]);
vector < int > vec(arr, arr + n) ;
5. Initializing from another vector:
vector < int > vec1{ 10, 20, 30 } ;
vector <int>vec2( vec1.begin( ), vec1.end( ));
6. Using [ ] operator :
vector < int > vec(3) ;
vec[0] = 10;
vec[1] = 20;
vec[2] = 30;
7. using assign( ) function :
vector < int > vec ;
vec.assign( { 10, 20, 30 } ) ;
8. Using other containers :
using array STL, let the array be a
vector < int > vec( a.begin( ), a.end( ) ) ;
using set STL, let the set be s
vector < int > vec( s.begin( ), s.end( ) ) ;
**don't worry about the methods / functions used above, i am going to explain each and every function associated with vector STL below.
All vector STL methods/ functions
1. vector STL important iterator functions:
Iterator definition: An iterator is something which helps in moving within the container. It points to a specific element and it moves according to our commands from one element to another.
1. begin( ) : returns an iterator pointing to the first element of the vector.
2. end( ) : returns an iterator pointing to the theoretical element after the last element of the vector.
Other functions:
- rbegin( )
- cbegin( )
- crbegin( )
- rend( )
- cend( )
- crend( )
2. vector STL important capacity related functions:
1. size( ) : returns the number of elements in the vector (works correctly when elements are put into vector using the push_back( ) method and size of the vector is not declared in it's initialization).
2. capacity( ) : returns the max. number of elements vector can hold (as vector is dynamic in nature, capacity automatically increases on putting elements through push_back( ) method.
3. resize( ) : resizes the container to the size specified in brackets.
4. empty( ) : returns true if the container is empty otherwise, false.
5. reserve( ) : makes the size or capacity of the vector equal to the value specified in the brackets.
Other functions:
- max_size( )
- shrink_to_fit( )
3. vector STL important element access functions:
1. operator [ ] or at( ) : returns the element at the specified index number in brackets.
2. front( ) : returns the first element of the vector.
Other functions:
- data( )
4. vector STL important modifying functions or modifiers:
1. push_back( ) or emplace_back( ) : used to put elements into a vector from back.
2. insert( ) or emplace( ) : used to insert a new element into a vector at the specified position i.e index number.
4. clear( ) : used to remove all elements from the vector container.
5. swap( ) : used to exchange the content of two vectors of a same type (size may differ).
6. erase( ) : used to remove a single element or a list of elements from the vector.
7. assign( ) : assigns new elements to the vector, replacing its current elements (if exists) and modifying its size accordingly.
emplace( ) vs insert( ) which to use?
- emplace() avoids unnecessary copy of objects.
- for primitive data types it does not matter which one to use but for objects or bigger objects use emplace() for efficiency.
- unlike insert(), no copy or move operation are performed in emplace().
5. vector STL other important functions (may come handy during competitions) :
1. accumulate( ) : used to find the sum of all the vector elements.
2. *min_element( ) : to directly find the minimum element in the vector.
4. find( ) : used to find the position or index number of the element specified in the brackets.
5. merge( ) : to merge two vectors into a new specified vector.
List of all vector STL important functions with example
1. Initializing vector : vector< int > v ;
2. Putting elements into it :
v.push_back( 10 ) ;
v.push_back( 30 ) ;
v.push_back( 20 ) ;
Therefore,
v = { 10, 30, 20 }
3. cout << v.size( ) ; // 3
4. cout << v.capacity( ) ; // 4
5. Checking whether vector is empty or not :
if( v.empty( ) = = false )
cout << "not empty" ; //it will be printed
else
cout << "empty" ;
6. cout << v[1] ; // 30
7. cout << v.at(1) ; // 30
8. cout << v.front( ) ; // 10
9. cout << v.back( ) ; // 20
10. v.pop_back( ) ;
// last element removed i.e 20
11. v.pop_front( ) ;
// first element removed i.e 10
Therefore,
v = { 30 }
12. v.assign( { 1, 2, 4, 3, 2, 3 } ) ;
Therefore,
v = { 1, 2, 4, 3, 2, 3 }
13. v.insert( v.begin( ), 10 ) ;
or
v.emplace( v.begin( ), 10 ) ;
// 10 is inserted at front
14. sort( v.begin( ), v.end( ) ) ;
Therefore,
17. cout << *min_element( v.begin( ), v.end( ));
v = { 1, 2, 2, 3, 3, 4, 10 }
15. cout << accumulate( v.begin( ), v.end( ) , 0 );
// 25 i.e the sum
16. cout<< *max_element(v.begin( ), v.end( ));
//10 i.e the max. element
17. cout << *min_element( v.begin( ), v.end( ));
//1 i.e the min. element
18. //setting up an iterator named it
vector < int > : : iterator it ;
it = v.begin( ) ;
//iterator now pointing to the first element
cout << *it ; // 1
19. v.clear( ) // all elements are removed from the vector
vector STL traversal methods
Let our vector be v :
vector < int > v ;
1. for ( auto &i : v)
{
cout << i << " ";
}
2. for ( auto i = v.begin( ) ; i ! = v.end( ) ; i++)
{
cout << *i << " " ;
}
3. declaring an iterator it :
vector < int > : : it ;
for ( it = v.begin( ) ; it!=v.end( ) ; it++)
{
cout << *it << " " ;
}4. for ( int i = 0 ; i < v.size( ); i++ )
{
cout << v[ i ] << " " ;
} This method above will work fine when size of the vector is not declared in it's initialization and elements are pushed into the vector using push_back( ) method.
5. In case you already know the size of the vector STL or you have declared the size of the vector during it's initialization:
vector < int > v( n ) ;
for (int i = 0 ; i < n ; i++ )
{
cout << v[ i ]<< " " ;
}
Comments
Post a Comment