ما وظيفة في المكتبة الأمراض المنقولة جنسيا هناك لبحث ثنائي ناقل وإيجاد عنصر؟

Question

ولقد حصلت على البنية عقدة

struct Node{CString text, int id;};

وفي ناقلات فرزها.

وأنا أتساءل عما إذا كان هناك وظيفة في الخوارزمية التي من شأنها القيام بعملية بحث ثنائي ناقلات وإيجاد عنصر.

Answer 1

وstd::binary_search() سوف اقول لكم في حالة وجود قيمة في الحاوية.

وstd::lower_bound()/std::upper_bound() سيعود مكرر إلى أول حدوث / الأخير من القيمة.

والأشياء الخاصة بك حاجة لتنفيذ operator< لهذه الخوارزميات للعمل.

Answer 2

نعم، هناك وظيفة تسمى "binary_search" الأمراض المنقولة جنسيا :: binary_search

وأنت تعطي لأول مرة، مشاركة وقيمة أو المسند.

هنا لعينة

ومع أن الجمع بين <لأ href = "https://stackoverflow.com/questions/369211/is-there-a-search-in-algorithm-ive-got-a-sorted-vector-and-im-looking ، للحصول على-SPECI # 369237 "> مشغل مارتن يورك == ويجب أن تكون على OK (بدلا من ذلك يمكنك كتابة functor المسند

Answer 3

وبدلا من ناقل فرزها <عقدة>
لماذا لا تستخدم الخريطة. هذا هو حاوية تم فرزها. لذلك فإن أي بحث القيام به على هذا عن طريق الأمراض المنقولة جنسيا :: تجد () لديه نفس الخصائص كما بحث ثنائي تلقائيا.

Answer 4

استخدم std::equal_range العثور على مجموعة من العناصر في ناقلات فرزها. std::equal_range إرجاع std::pair من المكررات، مما يتيح لك مجموعة في ناقلات العناصر يساوي الحجة التي تقدمها. إذا كان النطاق فارغ، ثم البند الخاص بك ليس في ناقلات، وطول المدى يخبرك كم عدد المرات التي يظهر فيها البند الخاص بك في ناقلات.

وهنا مثال باستخدام [إينتس] بدلا من struct Node:

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

int main(int argc, const char * argv[])
{
    std::vector<int> sorted = { 1, 2, 2, 5, 10 };

    auto range = std::equal_range(sorted.begin(), sorted.end(), 20);
    // Outputs "5 5"
    std::cout << std::distance(sorted.begin(), range.first) << ' '
              << std::distance(sorted.begin(), range.second) << '\n';

    range = std::equal_range(sorted.begin(), sorted.end(), 5);
    // Outputs "3 4"
    std::cout << std::distance(sorted.begin(), range.first) << ' '
              << std::distance(sorted.begin(), range.second) << '\n';

    range = std::equal_range(sorted.begin(), sorted.end(), -1);
    // Outputs "0 0"
    std::cout << std::distance(sorted.begin(), range.first) << ' '
              << std::distance(sorted.begin(), range.second) << '\n';

    return 0;
}

لجعل هذا العمل مع struct Node عليك إما أن توفر operator < لstruct Node أو تمر في مقارنة لstd::equal_range. يمكنك القيام بذلك عن طريق توفير امدا كحجة لstd::equal_range مقارنة البنيات الخاصة بك.

std::vector<Node> nodes = { Node{"hello", 5}, Node{"goodbye", 6} };
Node searchForMe { "goodbye", 6 };
auto range = std::equal_range(nodes.begin(), nodes.end(), searchForMe,
                               [](Node lhs, Node rhs) { return lhs.id < rhs.id; });