How to Find All Occurrences of an Element in a Deque in C++?
In C++, deques are data structures similar to queues provided by the STL library in C++ but unlike queues, deques allow the insertion and deletion of elements from both ends. In this article, we will learn how to find all occurrences of a specific element in a deque in C++.
Example
Input: deque<int>dq = {1, 2, 3, 4, 2, 5, 2, 6, 2} Target=2 Output: Element 2 found at index 1, 4, 6, 8
Finding All Occurrences of an Element in a Deque in C++
To find all occurrences of a specific element in a std::deque we can use the std::find() function, which returns the first occurrence of a given element in a queue and then keep searching for the given element repeatedly till the end to find all the occurrences.
Syntax of std::find()
find(first, last, target);
where,
- first: Iterator to the first element in the range.
- last: Iterator to the last element in the range.
- target: Element to search for.
C++ Program to Find All Occurrences of an Element in a Deque
The following program illustrates how we can find all occurrences of a specific element in a deque in C++.
// C++ Program to illustrate how we can find all occurrences
// of a specific element in a deque
#include <algorithm>
#include <deque>
#include <iostream>
using namespace std;
int main()
{
// Initialize a deque
deque<int> arr = { 2, 3, 2, 1, 5, 4, 2 };
// Element to search
int element = 2;
// Find the first occurrence of the element in the
// deque
auto it = find(arr.begin(), arr.end(), element);
// Check if the element was found
cout << "The element " << element
<< " occurred at indices: ";
while (it != arr.end()) {
// Print the index of the element
cout << it - arr.begin() << ", ";
// Search for the next occurrence and keeping
// beginning of the range after the currently found
// occurrence to avoid infinite loop
it = find(it + 1, arr.end(), element);
}
cout << endl;
return 0;
}
Output
The element 2 occurred at indices: 0, 2, 6,
Time Complexity: O(N), where N is the size of the deque.
Auxiliary Space: O(1)
Contact Us