Similar to an array in another programming language, a vector in C++ is flexible as its size can vary. Why use vectors? Because C++ arrays are fixed in size and cannot be resized once created, which is not suitable for storing data sets with unknown sizes.
Example:
#include < bits / stdc++.h >
#include < stdlib >
#include < stdio.h >
#include < vector >
#include < conio.h >
int searchResult ( std : : vector < int > arr , int k ) {
std : : vector < int > : : iterator it ;
it = std : : find ( arr . begin ( ) , arr . end ( ) , k ) ;
if ( it ! = arr . end ( ) )
return ( it - arr . begin ( ) ) ;
else
return -1 ;
}
int main ( ) {
std : : vector < int > arr = { 1 , 2 , 3 , 4 , 5 , 6 } ;
int k = 4 ;
std : : cout << searchResult ( arr , k ) << std : : endl ;
return 0 ;
}
Output:
3
.........................................
Process executed in 1.22 seconds
Press any key to continue.
Explanation
This piece of code returns the element's index if it is present in the vector; else, it returns -1.
- Line 1: The header file specified contains the locate function that we require, along with every C++ standard library.
- Line 2: We define a function that has two inputs: a vector and a key to be searched.
- Line 3: For our vector, we declare an iterator. It designates the vector's memory address. It will be utilized to traverse the vector. The link provided at the end of this post allows you to learn more about iterator.
- Line 4: We call the std::find method, which will return an iterator with the location of key k in the vector.
- Lines 5 through 8: Here, we do an if test to determine if the element is in the vector. If it is, we return its position; otherwise, we return -1, indicating that it is not.
The function call iterates through n elements within the vector to find the desired key, resulting in a time complexity of O(n) linear time.
Basic evaluations are executed by sequentially traversing the array with a consistent O(1) space complexity.
Taking Help of std::find_if with std::distance
Locating an item within an array using this approach is recommended when the search criteria involve specific conditions, like determining the index of an element in the array based on prime number principles.
If our predicate (compare struct) evaluates to true for any item within the initial to final range, std::find if will provide an iterator pointing to that specific item. In cases where there is no matching element, the function will return end(last), which points beyond the last element in the range.
The count of steps from the initial to final position is provided by std::distance. In our case, it indicates the steps from the start of the array to the iterator's key, k, representing the index of the element we are searching for. The index of the key will be determined by the count of steps.
Example:
# include < bits / stdc++.h >
struct compare {
int k ;
compare ( int const & i ) : k ( i ) { }
bool operator ( ) ( int const & i ) {
return ( i = = k ) ;
}
} ;
int searchResult ( std : : vector < int > arr , int k ) {
auto itr = std : : find_if ( arr . cbegin ( ) , arr . cend ( ) , compare ( k ) ) ;
if ( itr ! = arr . cend ( ) )
return std : : distance ( arr . cbegin ( ) , itr ) ;
return -1 ;
}
int main ( ) {
std : : vector < int > arr = { 1 , 2 , 3 , 4 , 5 , 6 } ;
int k = 4 ;
std : : cout << searchResult ( arr , k ) << std : : endl ;
return 0 ;
}
Output:
3
.........................................
Process executed in 1.33 seconds
Press any key to continue.
Explanation
- Line 2-8: We've declared a structure compare that evaluates the arguments' values against the int k.
- The external link provided at the bottom of this post allows you to learn more about C++ structures.
- Line 9: A searchResult function is declared, and its input parameters are a vector and a key.
- Line 10: This time, we're using the STL library's find if method and passing it a comparison structure with the key k as a parameter, along with constant random access iterators thacpp tutorial to the vector's beginning (arr.cbegin) and end (arr.cend).
