Как найти переменную вектора

In this article, we have explained Different Ways to find element in Vector in C++ STL which includes using std::find(), std::find_if, std::distance, std::count and Linear Search.

Table of contents:

1. Introduction to Vector in C++ and STL
2. How do we find an element using STL?
3. Approach 1: Return index of the element using std::find()
4. Use std::find_if() with std::distance()
5. Use std::count()
6. Linear search

Let us get started with Different Ways to find element in Vector in C++ STL.

Introduction to Vector in C++ and STL

A vector in C++ is just like an array in any other language but it is dynamic which means its size is not static. Why vectors? Well, arrays in C++ are static and once declared we cannot change their sizes which is not favourable when we need to store a data set whose size we are unsure of.

Unlike arrays we can determine the size of a vector at runtime and that is what makes vectors a perfect choice for these types of scenarios, they are dynamically allocated which means they can be resized.

The STL stands for Standard Template Library. Basically STL contains some generic functions that we shall need for this tutorial.

How do we find an element using STL?

There are three ways in which we can approach this problem:

Approach 1: By returning the index position of the element in the vector. Here we use std::find() and std::find_if()

Approach 2: By returning a boolean value, true if element is in the vector and false otherwise. Here we use std::count().

Approach 3: No STL here, we use linear search where by we go all through the vector elements making comparisons between the elements and key k.

Approach 1: Return index of the element using std::find()

std::find() searches for an element equal to the value that is passed as a parameter and returns an iterator pointing to that element in the vector.
In our case it will look like the following:

it = std::find(arr.begin(), arr.end(), k)

The parameter passed here is key k, the function call will return an iterator pointing to key k in the vector.

#include<bits/stdc++.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;
}

Code Explanation

This piece of code returns the index for the element we are trying to find and -1 if the element is not present in the vector.

Line 1: The header file declared includes every standard library in c++ and it contains the find function we need.
Line 2: We declare a function that takes a vector and key to be searched as parameters.
Line 3: We declare an iterator for our vector. It points at the memory address of the vector. We will use it for traversing the vector.
You can read up on iterators on the link provided at the end of this post.
Line 4: We make a function call to std::find that will return an iterator containing the position of key k in the vector.
Line 5 — 8: Here we do an if check, if the element is in the vector, we return its position otherwise we return -1 denoting that it is not in the vector.

The time complexity is linear O(n), this is because the function call goes through n items in the vector inorder to find the key we are searching for.
The space complexity is constant O(1), no extra space is used, just going through the vector and making comparisons.

2. Use std::find_if() with std::distance()

This is a recommended approach to finding an element in a vector if the search needs to satisfy a specific logic eg, finding an index of element in the vector that is a prime number using prime number logic.

std::find_if() returns an iterator to the first element in the first to last range for which our predicate(compare struct) returns true. If there is no such key, the function will return end(last), point past last.

std::distance() returns the number of hops from first to last. In our case it returns hops from begining of vector upto the iterator which points to the key k, this is the positional index of the element we are searching for. The number of hops will be the index of key k.

#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;
}

Code Explanation

The function searchResult() returns index of element in the vector or -1 denoting the absence of the element in the vector.
Line 2 — 8: We have declared a structure compare that compares the int k to values passed in its arguments.
You can read up on C++ structures at the external link provided at the end of this post.
Line 9: We declare a searchResult function that will take a vector and key as its parameters.
Line 10: Again we call the find_if function from STL libray but in this case we pass constant random access iterators that point to the begining (arr.cbegin()) and point past the end of the vector (arr.cend()) and the compare structure with key k as its parameter.
The auto keyword here specifies that the declared variable type will be automatically deducted from its initializer.
Line 10 — 13: We perform an if check to see if the iterator returned a value.
std::distance will perform as discussed above.
At this point it number of hops will be pointing to the index of key k in the vector.

The time complexity here is also linear O(n) because we got through the entire vector inorder to find the element.
The Space complexity is Constant O(1), no extra space is used.

Approach 2: Returning boolean value

3: Use std::count()

std::count() returns the number of occurences of an element in a vector.
We can apply it in situations where we need to check occurences of an element in the vector and return the number of times the element shows up in the vector.

#include<bits/stdc++.h>

bool searchResult(std::vector<int> arr, int k){
    return std::count(arr.begin(), arr.end(), k);
}

int main(){
    std::vector<int> arr = {1, 2, 3, 4, 5, 6};
    int k = 4;
    std::cout << searchResult(arr, k) << std::endl;
    return 0;
}

Code Explanation

Line 2: The function searchResult() takes the vector arr and key k as its parameters.
It returns 1 denoting true and 0 denoting false.
Line 3: Count STL function counts occurences of key k, if there are any, it returns the number of element occurences.
We can do an if check, if the count is greater than 0 then tha element exists otherwise it doesnt.

The time complexity is linear O(n) as we go through the entire vector.
The space complexity is constant O(1) as no extra space is used.

Approach 3: Linear search

In this case we dont use any STL function but rather we traverse the vector using a for loop element by element and make comparisons between target and each element, if an element matches our target we return its index.

#include<bits/stdc++.h>

int searchResult(std::vector<int> arr, int k){
    for(int i = 0; i < arr.size(); i++){
        if(arr[i] == k){
            return i;
        }
    }
    return -1;
}

int main(){
    std::vector<int> arr = {1, 4, 33, 44, 5, 6, 100, 4, 5, 7, 9, 0};
    int k = 4;
    std::cout << searchResult(arr, k) << std::endl;
    return 0;
}

Code Explanation

The function takes a vector and key k as its parameters, if the element exists, it returns the index, otherwise it returns -1 denoting absence of the element.

Line 3: We use a for loop where we go through the vector making element and target comparisons.
Line 4: We do an if check, if the element at the index is equal to our target, we return the index, otherwise we exit the loop and return -1.

Question

What is the running time and space complexity of the above approach by linear search?

Can you explain why the time and space complexity is so?

References

• Iterators in C++
• Structures in C++