Example
C++
#include <iostream>
#include <map>
int main() {
std::map<int, std::string> exampleMap;
exampleMap[1] = "Apple";
exampleMap[2] = "Banana";
exampleMap[3] = "Cherry";
auto it = exampleMap.find(2);
if (it != exampleMap.end()) {
std::cout << "Found: " << it->second << std::endl;
} else {
std::cout << "Key not found." << std::endl;
}
return 0;
}
You can also try this code with Online C++ Compiler
Output
Found: Banana
In this example, we search for the key 2. Since it exists, the output will be "Found: Banana". If we searched for a key that doesn't exist, such as 4, the output would be "Key not found."
Parameters
The map.find() function takes a single parameter:
key: The key value to search for in the map. The key parameter is of type const key_type&, where key_type is the type of the keys stored in the map. The key is passed by constant reference to avoid unnecessary copying.
When calling the find() function, you need to provide the key value that you want to search for in the map. The function will then traverse the map & try to find an element with a matching key.
It's important to note that the key type used in the map must support comparison operations, such as the less-than operator (<), to ensure proper ordering & searching within the map.
Example
C++
#include <iostream>
#include <map>
int main() {
std::map<int, std::string> fruitMap;
fruitMap[1] = "Apple";
fruitMap[2] = "Banana";
fruitMap[3] = "Cherry";
// Searching for key 3 in the map
auto search = fruitMap.find(3);
if (search != fruitMap.end()) {
std::cout << "Key found: " << search->first << " -> " << search->second << std::endl;
} else {
std::cout << "Key not found in the map." << std::endl;
}
return 0;
}
You can also try this code with Online C++ Compiler
Output
Key found: 3 -> Cherry
In this example, we search for the key 3. The function checks if this key exists in fruitMap. Because the key exists, it prints "Key found: 3 -> Cherry". This demonstrates the role of the key parameter in the map.find function and how it directs the search process within the map.
Return Value
The map.find() function returns an iterator pointing to the element with the specified key if found, or an iterator pointing to the end of the map if the key is not found.
- If the key is found: The returned iterator points to the key-value pair in the map where the key matches the provided key. You can access the key & the corresponding value using the iterator.
- If the key is not found: The returned iterator points to the end of the map, indicating that the key was not found in the map. The end of the map is represented by the map.end() iterator.
It's crucial to check the return value of the find() function to determine whether the key was found or not. You can compare the returned iterator with map.end() to check if the key exists in the map.
Example
std::map<int, std::string> myMap;
// ... populate the map ...
auto it = myMap.find(10);
if (it != myMap.end()) {
// Key found, iterator points to the key-value pair
std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
} else {
// Key not found, iterator points to the end of the map
std::cout << "Key not found in the map." << std::endl;
}
In the above code, the find() function is called on the map myMap with the key 10. The returned iterator it is then compared with myMap.end() to check if the key was found or not. If the key is found, the iterator points to the key-value pair, & you can access the key & value using it->first & it->second, respectively.
Time Complexity for Searching Element
The map.find() function has a time complexity of O(log n) on average, where n is the number of elements in the map.
Maps in C++ are typically implemented as balanced binary search trees, such as red-black trees. The balanced nature of these trees ensures that the height of the tree is logarithmic in relation to the number of elements. This logarithmic height allows for efficient search operations.
When you call the find() function & provide a key, the map performs a binary search to locate the element with the matching key. The binary search algorithm divides the search space in half at each step, resulting in a logarithmic time complexity.
Let’s see how complexity works:
- Best case: O(1) - When the key is found at the root of the tree or near the top levels, the search operation can be completed in constant time.
- Average case: O(log n) - On average, the search operation takes logarithmic time, as the map is balanced & the height of the tree is proportional to the logarithm of the number of elements.
- Worst case: O(log n) - Even in the worst case, where the key is located at the deepest level of the tree, the search operation still takes logarithmic time due to the balanced nature of the tree.
The logarithmic time complexity of map.find() makes it an efficient operation for searching elements in a map, especially when dealing with large datasets.
Note : It's important to note that the time complexity of map.find() is based on the assumption that the keys are unique & the map is balanced. If there are duplicate keys or if the map becomes unbalanced, the time complexity may degrade.
Code to print all the elements after finding a element
Let’s how to use the map.find() function to search for an element in a map & print all the elements after the found element:
C++
#include <iostream>
#include <map>
#include <string>
int main() {
std::map<int, std::string> myMap;
// Inserting elements into the map
myMap[1] = "Apple";
myMap[2] = "Banana";
myMap[3] = "Cherry";
myMap[4] = "Date";
myMap[5] = "Elderberry";
// Finding an element in the map
int searchKey = 3;
auto it = myMap.find(searchKey);
if (it != myMap.end()) {
std::cout << "Elements after the found element (" << searchKey << "):" << std::endl;
// Printing all elements after the found element
for (; it != myMap.end(); ++it) {
std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
}
} else {
std::cout << "Key not found in the map." << std::endl;
}
return 0;
}
You can also try this code with Online C++ Compiler
In this code:
- We create a map called myMap that stores key-value pairs, where the key is of type int & the value is of type std::string.
- We insert some elements into the map using the square bracket operator ([]).
- We define a searchKey variable with the value we want to search for in the map.
- We use the find() function to search for the searchKey in the map. The returned iterator it points to the found element if it exists, or to the end of the map if the key is not found.
- We check if the key is found by comparing it with myMap.end().
- If the key is found, we print a message indicating that we will print all elements after the found element.
- We start a loop from the found element (it) & iterate until the end of the map (myMap.end()). In each iteration, we print the key & value of the current element using it->first & it->second, respectively.
If the key is not found, we print a message indicating that the key was not found in the map.
Output
Elements after the found element (3):
Key: 3, Value: Cherry
Key: 4, Value: Date
Key: 5, Value: Elderberry
This code demonstrates how to use map.find() to search for an element & print all the elements after the found element. You can modify the searchKey variable to search for different keys & see the corresponding output.
Frequently Asked Questions
What happens if the key is not found in the map when using map.find()?
If the key is not found in the map, map.find() returns an iterator pointing to the end of the map (map.end()). You can check if the key is found by comparing the returned iterator with map.end().
Can map.find() be used with maps that have custom key types?
Yes, map.find() can be used with maps that have custom key types. However, the custom key type must support comparison operations, such as the less-than operator (<), to ensure proper ordering & searching within the map.
Is map.find() a constant-time operation?
No, map.find() has a logarithmic time complexity of O(log n) on average, where n is the number of elements in the map. This is because maps in C++ are typically implemented as balanced binary search trees, which provide efficient search operations.
Conclusion
In this article, we discussed the map.find() function in C++, which is used to search for elements in a map container. We covered the syntax of map.find(), its parameters, return value, & time complexity. We also provided a code example showing how to use map.find() to search for an element & print all the elements after the found element. The knowledge of map.find() is essential for efficient searching & manipulation of elements in a map.
You can refer to our guided paths on Code 360. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry.
117+ registered 