Szerkesztő:LinguisticMystic/cpp/AdvancedAlgorithms

🔍 Advanced STL Algorithms in C++

Building upon the foundation of basic STL algorithms like std::find, std::sort, and std::reverse, the C++ Standard Template Library offers a wide variety of advanced algorithms to handle more sophisticated data manipulation tasks. These algorithms are optimized, generic, and easy to integrate into your workflow, providing enhanced efficiency and expressive power.

---

📌 Binary Search – std::binary_search

When working with sorted containers, binary search is significantly faster than linear search.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> sortedNumbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int target = 7;

    bool found = std::binary_search(sortedNumbers.begin(), sortedNumbers.end(), target);

    if (found)
        std::cout << "Element " << target << " found." << std::endl;
    else
        std::cout << "Element " << target << " not found." << std::endl;

    return 0;
}

✅ Explanation

• std::binary_search works only on sorted ranges.
• Time complexity: O(log n)
• Returns a boolean indicating whether the target exists in the container.

📘 Try timing it against std::find using <chrono> to see performance differences.

---

🔗 Merge – std::merge

Merges two sorted sequences into one sorted output.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> first = {1, 3, 5, 7, 9};
    std::vector<int> second = {2, 4, 6, 8, 10};
    std::vector<int> result;

    std::merge(first.begin(), first.end(), second.begin(), second.end(), std::back_inserter(result));

    for (int num : result)
        std::cout << num << " ";

    return 0;
}

✅ Explanation

• Merges two sorted ranges into a new sorted range.
• Maintains the relative order of equivalent elements.
• Useful for implementing merge sort or combining sorted files.

---

🧹 Unique – std::unique (with erase idiom)

Removes consecutive duplicate elements from a sorted range.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> sortedNumbers = {1, 2, 2, 3, 3, 3, 4, 5, 5, 8};

    auto newEnd = std::unique(sortedNumbers.begin(), sortedNumbers.end());
    sortedNumbers.erase(newEnd, sortedNumbers.end());

    for (int num : sortedNumbers)
        std::cout << num << " ";

    return 0;
}

✅ Explanation

• std::unique moves duplicates to the end and returns an iterator to the new logical end.
• You must erase the tail for correct size.
• Works only on consecutive duplicates, so you typically sort before using.

⚠️ On Unsorted Data

If used on unsorted containers:

std::vector<int> unsorted = {5, 2, 5, 3, 2};
std::unique(unsorted.begin(), unsorted.end());  // Ineffective

Result won’t remove all duplicates unless sorted first.

---

🔀 Set Union – std::set_union

Combines elements from two sorted ranges into a union set (unique and sorted).

#include <iostream>
#include <set>
#include <algorithm>

int main() {
    std::set<int> set1 = {1, 2, 3, 4, 5};
    std::set<int> set2 = {3, 4, 5, 6, 7};
    std::set<int> unionSet;

    std::set_union(set1.begin(), set1.end(), set2.begin(), set2.end(),
                   std::inserter(unionSet, unionSet.begin()));

    for (int num : unionSet)
        std::cout << num << " ";

    return 0;
}

✅ Explanation

• Computes the set-theoretic union of two sorted ranges.
• Output is inserted via std::inserter into a std::set to preserve order and uniqueness.

---

🔗 Set Intersection – std::set_intersection

Finds common elements between two sorted containers.

#include <iostream>
#include <set>
#include <algorithm>

int main() {
    std::set<int> set1 = {1, 2, 3, 4, 5};
    std::set<int> set2 = {3, 4, 5, 6, 7};
    std::set<int> intersectionSet;

    std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(),
                          std::inserter(intersectionSet, intersectionSet.begin()));

    for (int num : intersectionSet)
        std::cout << num << " ";

    return 0;
}

✅ Explanation

• Finds common elements between two sorted ranges.
• Also maintains sorted order in the output container.
• Efficient for large datasets with sorted input.

---

🔚 Conclusion

The advanced STL algorithms empower you to write cleaner, faster, and more expressive C++ code. Here’s a quick summary:

Algorithm	Purpose	Requires Sorted Input	Output Container
std::binary_search	Efficient element lookup	✅	bool
std::merge	Merge two sorted ranges	✅	Appends to container
std::unique	Remove consecutive duplicates	🚫 (but more effective if sorted)	Trims in-place
std::set_union	Union of two sets	✅	Requires inserter
std::set_intersection	Intersection of two sets	✅	Requires inserter

🌟 Tip: Always sort your data if the algorithm requires it and you’re unsure of its state. Sorting upfront ensures correctness and allows many STL algorithms to work optimally.