Unleash Search Performance: Binary vs. Linear in C++ STL
Unlock peak algorithmic efficiency in your C++ applications. The choice between linear and binary search algorithms, specifically std::find versus std::lower_bound, profoundly impacts performance, particularly as data scales. Many developers instinctively reach for std::find, unaware of the immense computational leverage awaiting them by simply ensuring their data is sorted. This article decodes the critical performance disparity between these two fundamental search strategies.
We will journey through the algorithmic core of each, exposing their Big O complexities and revealing precisely when the upfront cost of sorting pays dividends in search speed. Prepare to revolutionize your approach to data retrieval, transforming bottlenecks into streamlined operations. Mastering these search dynamics is a cornerstone for any serious C++ developer focused on building high-performance systems and is integral to truly optimizing STL container and algorithm usage. We empower you to make informed, data-driven decisions that propel your software to the next frontier of speed and responsiveness.
Decode the Core: Linear Search (std::find) vs. Binary Search (std::lower_bound)
We initiate our exploration by firmly establishing the foundational differences between linear and binary search algorithms in the C++ Standard Template Library (STL). Linear search, embodied by std::find, operates by sequentially inspecting each element in a range until the target value is located or the range concludes. Its simplicity is its primary virtue, demanding no prerequisites on the data's organization. However, this simplicity carries a significant computational burden: a worst-case time complexity of O(N), meaning the time required scales linearly with the number of elements N. For small datasets, this overhead is negligible, but as N grows, std::find becomes a performance bottleneck.
Conversely, binary search algorithms, represented by std::lower_bound and std::binary_search, operate on a fundamentally different principle: divide and conquer. This strategy mandates a crucial prerequisite: the data range must be sorted. With a sorted range, binary search repeatedly halves the search interval, rapidly converging on the target or determining its absence. This algorithmic elegance yields a time complexity of O(log N). To illustrate, searching a million elements linearly might require a million comparisons, whereas binary search accomplishes the same task in approximately 20 comparisons (log2(1,000,000) ≈ 19.9). This exponential reduction in operations is transformative for large datasets. Understanding this core dichotomy empowers developers to strategically select the correct tool for the job, rather than defaulting to the path of least resistance. We unlock this performance leverage by first recognizing the inherent trade-offs.
/*
std::find vs std::lower_bound: Basic Illustration
This code demonstrates the conceptual difference and setup for each search type.
For accurate performance measurement, larger datasets and proper benchmarking tools are required.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
// --- Linear Search Example ---
void demonstrate_linear_search() {
std::vector<int> data = {1, 5, 8, 2, 7, 3, 9, 4, 6};
int value_to_find = 7;
std::cout << "\n--- Linear Search (std::find) ---\n";
auto start_time = std::chrono::high_resolution_clock::now();
auto it_linear = std::find(data.begin(), data.end(), value_to_find);
auto end_time = std::chrono::high_resolution_clock::now();
if (it_linear != data.end()) {
std::cout << "Value " << value_to_find << " found at index: " << std::distance(data.begin(), it_linear) << std::endl;
} else {
std::cout << "Value " << value_to_find << " not found." << std::endl;
}
std::cout << "Time taken (linear): " << std::chrono::duration_cast<std::chrono::nanoseconds>(end_time - start_time).count() << " ns\n";
}
// --- Binary Search Example ---
void demonstrate_binary_search() {
std::vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9}; // Data must be sorted for binary search
int value_to_find = 7;
std::cout << "\n--- Binary Search (std::lower_bound) ---\n";
auto start_time = std::chrono::high_resolution_clock::now();
// std::lower_bound returns an iterator to the first element not less than value_to_find
auto it_binary = std::lower_bound(data.begin(), data.end(), value_to_find);
auto end_time = std::chrono::high_resolution_clock::now();
if (it_binary != data.end() && *it_binary == value_to_find) {
std::cout << "Value " << value_to_find << " found at index: " << std::distance(data.begin(), it_binary) << std::endl;
} else {
std::cout << "Value " << value_to_find << " not found (or not exactly matched)." << std::endl;
}
std::cout << "Time taken (binary): " << std::chrono::duration_cast<std::chrono::nanoseconds>(end_time - start_time).count() << " ns\n";
}
int main() {
demonstrate_linear_search();
demonstrate_binary_search();
return 0;
}
Activate Binary Search: The Imperative of Sorted Data and its Cost
To harness the power of binary search, we must first confront its fundamental requirement: a sorted data range. This is non-negotiable. Attempting to apply std::lower_bound or std::binary_search to an unsorted container produces undefined or incorrect results, sabotaging the very performance gains we seek. Therefore, the strategic decision to employ binary search immediately introduces the overhead of sorting the data, typically via std::sort, which operates with an average time complexity of O(N log N).
This initial sorting cost is a critical factor in our performance equation. If we perform only a single search, the O(N log N) sort combined with an O(log N) binary search will almost certainly be slower than a straightforward O(N) linear search. The tipping point arrives when we anticipate multiple searches on the same dataset. For example, if we sort once (O(N log N)) and then execute M binary searches (M * O(log N)), the total cost becomes O(N log N + M log N). This aggregate cost quickly eclipses the M * O(N) cost of M linear searches as M increases, especially for large N. Forge a mental model where the initial sort is an investment; the more searches you conduct, the higher the return on that investment.
Maintaining a sorted state is equally vital for dynamic datasets. If elements are frequently inserted or deleted, we must either re-sort the entire container (which becomes prohibitive) or employ more sophisticated data structures like std::set or std::map, which inherently maintain sorted order at the cost of logarithmic insertion/deletion complexity. Ignoring the sorting imperative transforms a powerful optimization into a source of bugs and performance degradation. We must engineer our data management strategy to align with the chosen search algorithm, ensuring data integrity for optimal performance.
/*
Demonstrating the Sorting Prerequisite for Binary Search
This example shows how to sort a vector and then use std::lower_bound.
It also conceptually highlights the cost of sorting.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
void activate_binary_search_with_sort() {
std::vector<int> data;
const int DATA_SIZE = 100000; // Large dataset for illustrative purposes
// Populate with random data
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
std::uniform_int_distribution<int> dist(0, DATA_SIZE * 10);
for (int i = 0; i < DATA_SIZE; ++i) {
data.push_back(dist(rng));
}
int value_to_find = data[DATA_SIZE / 2]; // A value guaranteed to be in the vector
std::cout << "\n--- Activating Binary Search: Sorting Imperative ---\n";
std::cout << "Dataset size: " << DATA_SIZE << std::endl;
// 1. Measure Linear Search on unsorted data (baseline)
auto start_linear_unsorted = std::chrono::high_resolution_clock::now();
auto it_linear_unsorted = std::find(data.begin(), data.end(), value_to_find);
auto end_linear_unsorted = std::chrono::high_resolution_clock::now();
std::cout << "Linear search on unsorted data: "
<< std::chrono::duration_cast<std::chrono::microseconds>(end_linear_unsorted - start_linear_unsorted).count()
<< " µs\n";
// 2. Measure Sorting Cost
auto start_sort = std::chrono::high_resolution_clock::now();
std::sort(data.begin(), data.end());
auto end_sort = std::chrono::high_resolution_clock::now();
long long sort_time = std::chrono::duration_cast<std::chrono::microseconds>(end_sort - start_sort).count();
std::cout << "Sorting data (O(N log N)): " << sort_time << " µs\n";
// 3. Measure Binary Search on sorted data
auto start_binary_sorted = std::chrono::high_resolution_clock::now();
auto it_binary_sorted = std::lower_bound(data.begin(), data.end(), value_to_find);
auto end_binary_sorted = std::chrono::high_resolution_clock::now();
long long binary_search_time = std::chrono::duration_cast<std::chrono::microseconds>(end_binary_sorted - start_binary_sorted).count();
std::cout << "Binary search on sorted data (O(log N)): " << binary_search_time << " µs\n";
// Determine when sorting is worthwhile
std::cout << "\nAnalysis:\n";
if (sort_time + binary_search_time < (DATA_SIZE * binary_search_time) / (double)DATA_SIZE) {
// This is a rough estimation, actual crossover depends on constant factors
std::cout << "The initial sort cost of " << sort_time << " µs means you save time after a few binary searches if searches are frequent.\n";
}
std::cout << "If you perform many searches on this dataset, the O(log N) advantage of binary search quickly outweighs the initial sort cost.\n";
// Common Pitfall: Searching unsorted data with binary search algorithm
std::vector<int> unsorted_data_pitfall = {5, 1, 8, 2, 7};
int pitfall_value = 2;
// WARNING: This call is incorrect for unsorted data and may produce wrong results.
auto it_pitfall = std::lower_bound(unsorted_data_pitfall.begin(), unsorted_data_pitfall.end(), pitfall_value);
std::cout << "\nCommon Pitfall: Using std::lower_bound on unsorted data for value " << pitfall_value << ". Resulting iterator (if valid): ";
if (it_pitfall != unsorted_data_pitfall.end()) {
std::cout << *it_pitfall << " (Expected 2, got: " << *it_pitfall << "). Incorrect if not found at expected position.\n";
} else {
std::cout << "Not found (could be wrong). This illustrates why data must be sorted.\n";
}
}
int main() {
activate_binary_search_with_sort();
return 0;
}
Refine Search Strategy: std::lower_bound vs. std::binary_search and Custom Comparators
Deciphering the nuanced differences between std::lower_bound and std::binary_search is critical for precision engineering. While both leverage binary search principles, their return values dictate their application. std::binary_search is a predicate function; it simply returns a bool, indicating whether the target value exists within the sorted range. It's a quick 'yes' or 'no' answer, sufficient when mere presence is the goal. Conversely, std::lower_bound is a locator. It returns an iterator pointing to the first element in the range that is not less than the specified value. This iterator is crucial for retrieving the actual element, or for determining the correct insertion point if the element isn't present, maintaining the sorted order.
We further elevate our search capabilities by employing custom comparators. For complex user-defined types or when the default ordering (e.g., using operator<) is insufficient, we must provide a custom comparison function or functor to both the sorting algorithm (std::sort) and the binary search algorithm (std::lower_bound, std::upper_bound, std::binary_search). This comparator must establish a strict weak ordering. A common pitfall arises when developers sort a container using one comparison criterion but then attempt to search it using a different or implicit criterion. The comparator passed to the search function must precisely match the comparator used to sort the range. Failure to align these comparators will result in incorrect search outcomes, despite the data appearing 'sorted' by a different metric.
For instance, if we sort a vector of Product objects by their id, but then attempt to search for a Product by its name using a comparator that compares names, std::lower_bound will yield erroneous results because the underlying data is not sorted according to the search criterion. We activate this level of control to precisely navigate complex data structures, ensuring algorithmic correctness and unlocking the full potential of binary search for custom types and specialized ordering requirements.
/*
Refining Search: std::lower_bound vs. std::binary_search and Custom Comparators
This example illustrates the difference between these two algorithms and the use of custom comparators.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <functional>
// A custom struct for demonstration
struct Product {
std::string name;
double price;
int id;
bool operator<(const Product& other) const {
return id < other.id; // Default comparison by ID
}
};
// Custom comparator for Product by name
struct CompareProductByName {
bool operator()(const Product& a, const Product& b) const {
return a.name < b.name;
}
bool operator()(const Product& a, const std::string& name) const {
return a.name < name;
}
bool operator()(const std::string& name, const Product& b) const {
return name < b.name;
}
};
void refine_search_strategies() {
std::vector<int> numbers = {10, 20, 30, 40, 50};
int search_value = 30;
std::cout << "\n--- std::lower_bound vs. std::binary_search ---\n";
// Using std::binary_search (returns bool: existence check)
bool found_binary_search = std::binary_search(numbers.begin(), numbers.end(), search_value);
std::cout << "std::binary_search for " << search_value << ": " << (found_binary_search ? "Found" : "Not Found") << std::endl;
// Using std::lower_bound (returns iterator: location for retrieval)
auto it_lower_bound = std::lower_bound(numbers.begin(), numbers.end(), search_value);
if (it_lower_bound != numbers.end() && *it_lower_bound == search_value) {
std::cout << "std::lower_bound found " << search_value << " at index: " << std::distance(numbers.begin(), it_lower_bound) << std::endl;
} else {
std::cout << "std::lower_bound indicates " << search_value << " is not present (or would be inserted at index " << std::distance(numbers.begin(), it_lower_bound) << ")." << std::endl;
}
// Searching for a value not present
int non_existent_value = 35;
bool found_non_existent = std::binary_search(numbers.begin(), numbers.end(), non_existent_value);
std::cout << "std::binary_search for " << non_existent_value << ": " << (found_non_existent ? "Found" : "Not Found") << std::endl;
auto it_non_existent = std::lower_bound(numbers.begin(), numbers.end(), non_existent_value);
std::cout << "std::lower_bound for " << non_existent_value << " points to: ";
if (it_non_existent != numbers.end()) {
std::cout << *it_non_existent << " (index: " << std::distance(numbers.begin(), it_non_existent) << ")\n";
} else {
std::cout << "End of range (index: " << std::distance(numbers.begin(), it_non_existent) << ")\n";
}
std::cout << "\n--- Custom Comparators ---\n";
// Using custom struct and sorting by ID (default operator<)
std::vector<Product> products = {
{"Laptop", 1200.0, 101},
{"Mouse", 25.0, 103},
{"Keyboard", 75.0, 102}
};
std::sort(products.begin(), products.end()); // Sorts by ID due to operator<
std::cout << "Sorted Products (by ID):\n";
for (const auto& p : products) {
std::cout << " ID: " << p.id << ", Name: " << p.name << std::endl;
}
// Search for a product by ID (using default operator< for comparison)
Product search_product_by_id = {"", 0.0, 102}; // Only ID matters for search
auto it_product_id = std::lower_bound(products.begin(), products.end(), search_product_by_id);
if (it_product_id != products.end() && it_product_id->id == search_product_by_id.id) {
std::cout << "Found Product by ID " << search_product_by_id.id << ": " << it_product_id->name << std::endl;
} else {
std::cout << "Product with ID " << search_product_by_id.id << " not found.\n";
}
// Re-sort by name using a custom comparator
std::sort(products.begin(), products.end(), CompareProductByName());
std::cout << "\nRe-sorted Products (by Name):\n";
for (const auto& p : products) {
std::cout << " ID: " << p.id << ", Name: " << p.name << std::endl;
}
// Search for a product by name using custom comparator (note the search value type)
std::string search_name = "Mouse";
auto it_product_name = std::lower_bound(products.begin(), products.end(), search_name, CompareProductByName());
if (it_product_name != products.end() && it_product_name->name == search_name) {
std::cout << "Found Product by Name " << search_name << ": ID " << it_product_name->id << std::endl;
} else {
std::cout << "Product with Name " << search_name << " not found.\n";
}
// Common Pitfall: Mismatched comparator for sort and search
std::cout << "\nCommon Pitfall: Mismatched Comparators (example using ID sort, then Name search without proper comparator in lower_bound)\n";
std::sort(products.begin(), products.end()); // Sort by ID again
std::string wrong_search_name = "Keyboard";
// This call will likely fail to find 'Keyboard' because the vector is sorted by ID, but we search by name implicitly or with wrong comparator
auto it_wrong = std::lower_bound(products.begin(), products.end(), wrong_search_name, CompareProductByName()); // This would work if products were sorted by name!
if (it_wrong != products.end() && it_wrong->name == wrong_search_name) {
std::cout << "Found (unexpectedly correctly) " << wrong_search_name << " - depends on data distribution.\n";
} else {
std::cout << "'Keyboard' not found with mismatched sort/search criteria. Always ensure comparator used for search matches sort order!\n";
}
}
int main() {
refine_search_strategies();
return 0;
}
Engineer Strategic Implementation: Benchmarking and Real-World Scenarios
We culminate our analysis by engineering strategic implementation through rigorous benchmarking and an understanding of real-world scenarios. Accurate performance assessment demands more than theoretical Big O notation; it requires empirical measurement using tools like std::chrono. Conduct experiments with sufficiently large datasets to reveal the true overheads and benefits. Benchmark the time taken for: 1. Initial sorting (if applicable), 2. A single linear search, and 3. A single binary search. This empirical data will reveal the concrete 'tipping point' – the number of searches after which the upfront investment in sorting becomes more efficient than repeated linear searches.
Consider these critical scenarios: For static datasets, loaded once and queried extensively, the strategy is clear: sort once (O(N log N)) and then leverage binary search (O(log N)) repeatedly. The initial sorting cost amortizes across numerous searches, yielding substantial long-term gains. In contrast, for highly dynamic datasets where insertions and deletions are frequent, maintaining a sorted std::vector can be prohibitively expensive due to O(N) insertion/deletion costs. In such cases, consider inherently sorted containers like std::set or std::map, which offer O(log N) insertion, deletion, and search guarantees by employing balanced tree structures. Alternatively, if N remains small or searches are infrequent, an unsorted std::vector with std::find might be perfectly acceptable, as the O(N) linear search cost is tolerable.
Always activate profiling tools to identify actual performance bottlenecks in your application. Do not prematurely optimize based solely on theoretical models. The most performant solution arises from a blend of algorithmic rigor, system thinking, and data-driven decisions. We empower developers to forge systems that are not just functionally correct, but also computationally efficient, by strategically aligning data structures and algorithms with the operational demands of their applications. This comprehensive approach transforms complex programming challenges into actionable exploration on the frontier of high-performance computing.
/*
Strategic Implementation: Benchmarking and Real-World Scenarios
This code provides a template for benchmarking and illustrates the crossover point
between linear and binary search based on search frequency.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
// Function to perform linear search and measure time
long long measure_linear_search(const std::vector<int>& data, int value_to_find) {
auto start = std::chrono::high_resolution_clock::now();
std::find(data.begin(), data.end(), value_to_find);
auto end = std::chrono::high_resolution_clock::now();
return std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
}
// Function to perform binary search and measure time
long long measure_binary_search(const std::vector<int>& data, int value_to_find) {
auto start = std::chrono::high_resolution_clock::now();
std::lower_bound(data.begin(), data.end(), value_to_find);
auto end = std::chrono::high_resolution_clock::now();
return std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
}
void strategic_implementation() {
const int DATA_SIZE = 1000000; // 1 million elements
std::vector<int> data(DATA_SIZE);
std::iota(data.begin(), data.end(), 0); // Fill with sorted data 0 to DATA_SIZE-1
// Introduce some randomness for real-world simulation (not perfectly sorted anymore for find test)
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(data.begin(), data.end(), g);
int value_to_find = DATA_SIZE / 2; // Search for a middle element
std::cout << "\n--- Benchmarking Search Performance ---\n";
std::cout << "Dataset size: " << DATA_SIZE << std::endl;
// 1. Measure Linear Search on unsorted-like data
long long linear_time = measure_linear_search(data, value_to_find);
std::cout << "Linear search time (O(N)): " << linear_time << " ns\n";
// 2. Measure Sorting Cost
auto start_sort = std::chrono::high_resolution_clock::now();
std::sort(data.begin(), data.end());
auto end_sort = std::chrono::high_resolution_clock::now();
long long sort_time = std::chrono::duration_cast<std::chrono::nanoseconds>(end_sort - start_sort).count();
std::cout << "Sorting time (O(N log N)): " << sort_time << " ns\n";
// 3. Measure Binary Search on sorted data
long long binary_time = measure_binary_search(data, value_to_find);
std::cout << "Binary search time (O(log N)): " << binary_time << " ns\n";
std::cout << "\n--- Performance Crossover Analysis ---\n";
double average_linear_search_cost_per_query = static_cast<double>(linear_time);
double average_binary_search_cost_per_query = static_cast<double>(binary_time);
// Calculate the number of searches needed for binary search to break even
if (average_binary_search_cost_per_query > 0) { // Prevent division by zero
int num_searches_to_break_even = static_cast<int>(
sort_time / (average_linear_search_cost_per_query - average_binary_search_cost_per_query)
);
std::cout << "If (Linear Search Cost - Binary Search Cost) > 0, then: \n";
std::cout << "Binary search becomes beneficial after approximately "
<< num_searches_to_break_even << " searches (ignoring constant factors).\n";
std::cout << "This demonstrates the 'tipping point' where the initial sorting investment pays off.\n";
} else {
std::cout << "Binary search cost is zero, indicating immediate benefit or measurement anomaly.\n";
}
std::cout << "\n--- Real-World Scenario Guidelines ---\n";
std::cout << "1. Static Data: For data loaded once and searched many times, sort upfront. Leverage O(log N) repeatedly.\n";
std::cout << "2. Dynamic Data (Frequent Inserts/Deletes): Consider containers like std::set or std::map (logarithmic insertion/search) or an unsorted vector with linear search if N is small or searches are infrequent.\n";
std::cout << "3. Infrequent Searches, Large N: If data is large and searches are rare, the cost of sorting may never be recouped. Stick with linear search.\n";
std::cout << "4. Performance-Critical Sections: Benchmark thoroughly with real data profiles. Profile your application to identify actual bottlenecks.\n";
}
int main() {
strategic_implementation();
return 0;
}
Key Takeaways
Algorithmic Efficiency: O(N) vs O(log N)
Linear search (std::find) has O(N) complexity, inspecting each element. Binary search (std::lower_bound, std::binary_search) has O(log N) complexity, rapidly narrowing the search space. This difference is critical for large datasets, where O(log N) offers exponential speed-up.
The Sorting Prerequisite: An O(N log N) Investment
Binary search absolutely requires a sorted data range. The initial cost of sorting (O(N log N) for std::sort) must be weighed against the cumulative savings from multiple O(log N) searches. For static data or many searches, sorting upfront is a high-yield investment.
std::lower_bound vs. std::binary_search: Utility Defined
std::binary_search returns a boolean for existence. std::lower_bound returns an iterator to the potential location of the element or its insertion point. Choose std::lower_bound for element retrieval or precise insertion logic, and std::binary_search for simple presence checks.
Custom Comparators: Precision for Complex Types
When dealing with user-defined types or custom ordering, provide a consistent custom comparator (functor/lambda) to both the sorting algorithm (e.g., std::sort) and the binary search algorithm (e.g., std::lower_bound). Mismatched comparators will lead to incorrect search results.
Strategic Implementation: Benchmark and Context
Always benchmark performance with real data using tools like std::chrono. For static data or high search frequency, sort and use binary search. For dynamic data, consider inherently sorted containers (std::set, std::map) or accept linear search if N is small or searches are infrequent. Profile to identify true bottlenecks.
FAQ
-
When should I absolutely use binary search over linear search?
You should absolutely prioritize binary search (via
std::lower_boundorstd::binary_search) when you have a large dataset that is either already sorted or needs to be searched many times after an initial sort. The logarithmic time complexity (O(log N)) provides exponential performance gains over linear search (O(N)) as N grows, quickly outweighing the O(N log N) sorting cost for frequent lookups. -
What is the primary difference between std::lower_bound and std::binary_search?
std::binary_searchreturns abool, indicating only if an element exists in a sorted range.std::lower_boundreturns an iterator to the first element that is not less than the specified value. This iterator allows you to retrieve the element, or determine its correct insertion point if it's not present, offering more practical utility for data manipulation beyond a simple existence check. -
Can I use std::lower_bound on an unsorted vector?
No. Using
std::lower_bound(or any other binary search algorithm) on an unsorted range results in undefined behavior or incorrect results. The correctness of binary search algorithms relies entirely on the guarantee that the data range is sorted according to the comparison criterion used. -
How do I search for custom objects using binary search?
For custom objects, you must ensure two conditions: 1) The container is sorted based on your desired comparison criterion. 2) You provide a custom comparator (a function object or lambda) to both
std::sort(for sorting) and the binary search algorithm (std::lower_bound,std::binary_search) that defines the strict weak ordering for your objects. This ensures consistency between sorting and searching logic. -
Are there alternatives to sorting a vector if I need fast searches on dynamic data?
Yes. For dynamic data requiring fast searches, consider STL containers that inherently maintain sorted order:
std::setandstd::map: These are typically implemented as balanced binary search trees, offering O(log N) complexity for insertion, deletion, and search.std::unordered_setandstd::unordered_map: These use hash tables, providing average O(1) complexity for search, insertion, and deletion, but they do not maintain sorted order and have a worst-case O(N) complexity for these operations.