วิธีหาค่ามัธยฐานของ "std :: set` [ซ้ำ]

Question

ฉันพยายามหาค่ามัธยฐานของไฟล์std::set. เนื่องจากstd::setจัดเรียงทุกอย่างเรียบร้อยแล้วฉันก็ต้องเลือกองค์ประกอบตรงกลาง ความคิดของฉันคือการก้าวไปสู่ครึ่งทาง: std::advance(e, rtspUrls.size() / 2);แต่ฉันไม่แน่ใจว่ามันจะเป็นอย่างไร แล้วตัวเลข1.5ล่ะ? จะก้าวไปสู่บางสิ่งหรือไม่?

ฉันกำลังพยายามจับเพื่อพยายามที่จะไม่ก้าวไปสู่สิ่งที่ไม่ได้กำหนด ปลอดภัยหรือไม่?

ตาม http://www.cplusplus.com/reference/algorithm/min_element/?kw=min_element, std::advanceพ่นถ้า iterator พ่น ฉันไม่แน่ใจว่าตัววนซ้ำสำหรับ std :: set จะพ่นเมื่อเราพยายามหรือ++ไม่ (https://en.cppreference.com/w/cpp/named_req/BidirectionalIterator ไม่พูดอะไรเลย)

std::set<RTSPUrl, decltype(compare_rtsp_url)*> rtspUrls(compare_rtsp_url);
std::set<RTSPUrl, decltype(compare_rtsp_url)*>::iterator e = rtspUrls.begin();
for (const RTSPUrl &rtspUrl : stream.rtsp_urls())
{
    if (rtspUrl.has_resolution())
    {
        rtspUrls.push_back(rtspUrl);
    }
}
try
{
    std::advance(e, rtspUrls.size() / 2);
    return *e;
}
catch (std::exception &e)
{
    return std::nullopt;
}

Answer 1

ด้วยstd :: setคุณถูก จำกัด ให้ใช้ตัววนซ้ำเพื่อวนซ้ำไปยังองค์ประกอบกลาง (ในกรณีที่มีรายการจำนวนคี่ในชุดของคุณ) หรือวนซ้ำไปที่กลาง -1 และกลางและหาค่าเฉลี่ย (int กรณีของจำนวนคู่ ของรายการ) เพื่อกำหนดค่ามัธยฐาน

การวนซ้ำธรรมดาและตัวนับเป็นเรื่องตรงไปข้างหน้าเท่าที่จะทำได้ ตัวอย่างสั้น ๆ จะเป็น:

#include <iostream>
#include <set>

int main (void) {
    
#ifdef ODD
    std::set<std::pair<char,int>> s {{'a',1}, {'b',2}, {'c',3}, {'d',4}, {'e',5}};
#else
    std::set<std::pair<char,int>> s {{'a',1}, {'b',2}, {'c',3}, {'d',4}, {'e',5}, {'f',6}};
#endif
    double median = 0.;
    size_t n = 0;
    
    for (auto iter = s.begin(); iter != s.end(); iter++, n++) {
        if (n == s.size() / 2 - 1 && s.size() % 2 == 0) {
            median += iter->second;
            std::cout << iter->first << "  " << iter->second << '\n';
        }
        if (n == s.size() / 2) {
            median += iter->second;
            if (s.size() % 2 == 0)
                median /= 2.;
            std::cout << iter->first << "  " << iter->second
                    << "\n\nmedian " << median << '\n';
            break;
        }
    }
}

(แน่นอนว่าคุณจะต้องปรับเปลี่ยนประเภทให้ตรงกับข้อมูลของคุณ)

ตัวอย่างการใช้ / ผลลัพธ์

รวบรวมด้วยODDกำหนด:

$ ./bin/set_median
c  3

ค่ามัธยฐาน 3

รวบรวมโดยไม่มีคำจำกัดความเพิ่มเติมสำหรับกรณี EVEN:

$ ./bin/set_median
c  3
d  4

median 3.5

std :: ถัดไป

คุณสามารถใช้มาตรฐาน :: ถัดไปล่วงหน้าเพื่อที่ n ^TH iterator หลังจากปัจจุบัน คุณต้องกำหนดผลลัพธ์:

    median = 0.;
    auto iter = s.begin();
    
    if (s.size() % 2 == 0) {
        iter = std::next(iter, s.size() / 2 - 1);
        median += iter->second;
        iter = std::next(iter);
        median += iter->second;
        median /= 2.;
    }
    else {
        iter = std::next(iter, s.size() / 2);
        median += iter->second;
    }
    std::cout << "\nmedian " << median << '\n';

std :: advance

มาตรฐาน :: ล่วงหน้าก้าวหน้า iterator ที่ให้ไว้เป็นพารามิเตอร์ n ที่^TH iterator หลังจากที่ปัจจุบัน:

    median = 0.;
    iter = s.begin();
    if (s.size() % 2 == 0) {
        std::advance(iter, s.size() / 2 - 1);
        median += iter->second;
        std::advance(iter, 1);
        median += iter->second;
        median /= 2.;
    }
    else {
        std::advance(iter, s.size() / 2);
        median += iter->second;
    }
    std::cout << "\nmedian " << median << '\n';

(เอาต์พุตสำหรับmedianเหมือนกับลูปด้านบน)

ตรวจสอบสิ่งต่างๆและแจ้งให้เราทราบหากคุณมีคำถามเพิ่มเติม

Answer 2

ฉันต้องเลือกองค์ประกอบตรงกลาง ความคิดของฉันคือการก้าวไปสู่ครึ่งทาง: std::advance(e, rtspUrls.size() / 2);แต่ฉันไม่แน่ใจว่ามันจะเป็นอย่างไร แล้วตัวเลขเช่น 1.5 ล่ะ? จะก้าวไปสู่บางสิ่งหรือไม่?

std::setดัชนีใช้ค่าจำนวนเต็มไม่ได้ลงนาม ( size_t) ดังนั้นจะถูกแปลงเป็นdouble 1.5size_t 1

ฉันไม่แน่ใจว่าตัววนซ้ำสำหรับstd::setพ่นเมื่อเราพยายามหรือไม่++

ไม่มันจะไม่ แต่การก้าวไปไกลกว่าend()นั้นไม่ได้กำหนดไว้

มัธยฐานจริงสำหรับชุดที่มีจำนวนขององค์ประกอบแม้จะใช้เวลาเฉลี่ยของทั้งสององค์ประกอบกลาง - แต่ที่ต้องว่าประเภทที่คุณเก็บไว้ในของคุณstd::setทั้งสนับสนุนและ+ /ตัวอย่าง:

std::set<double> foo{1., 2., 3., 10.};

if(foo.empty()) throw std::runtime_error("no elements in set");

double median;

if(foo.size() % 2 == 0) {                 // even number of elements 
    auto lo = std::next(foo.begin(), foo.size() / 2 - 1);
    auto hi = std::next(lo);
    median = (*lo + *hi) / 2.;
} else {                                  // odd number of elements
    median = *std::next(foo.begin(), foo.size() / 2);
}

std::cout << median << '\n'; // prints 2.5

ในกรณีของคุณประเภทในชุดดูเหมือนจะไม่รองรับ+และ/สร้างค่าเฉลี่ยสองRTSPUrlวินาทีในกรณีที่คุณมีองค์ประกอบจำนวนเท่ากันดังนั้นคุณควรเลือกหนึ่งในสององค์ประกอบกลางในกรณีที่คุณมี จำนวนคู่ โดยการส่งคืนตัววนซ้ำ (เพื่อให้ผู้ใช้ตรวจสอบได้ว่าเป็นrtspUrls.end()):

return std::next(rtspUrls.begin(), rtspUrls.size() / 2);

หรือโดยการส่งคืนข้อมูลอ้างอิงหรือสำเนาขององค์ประกอบ:

if(rtspUrls.empty()) throw std::runtime_error("no elements in set");
return *std::next(rtspUrls.begin(), rtspUrls.size() / 2);

Answer 3

ฉันต้องเลือกองค์ประกอบตรงกลาง

เฉพาะเมื่อชุดนั้นมีองค์ประกอบจำนวนคี่ มิฉะนั้นเมื่อขนาดเท่ากันค่ามัธยฐานจะถูกกำหนดให้เป็นค่ากลางของค่ากลางสองค่าซึ่งบางครั้งเรียกว่าค่ามัธยฐานบนและล่าง

แล้วตัวเลขเช่น 1.5 ล่ะ?

คุณจะไม่ได้รับสิ่งนั้นเลยเนื่องจากrtspUrls.size() / 2เป็นการหารจำนวนเต็มที่ตัดทอนตำแหน่งทศนิยมใด ๆ

ฉันคิดว่าการส่งพารามิเตอร์floatหรือdoubleเป็นพารามิเตอร์ที่สองเช่นstd::advance(e, 1.5)ไม่ควรคอมไพล์ เท่าที่ฉันเห็นการอ้างอิงไม่ได้ระบุประเภทของพารามิเตอร์ที่สอง อย่างไรก็ตาม - ส่วน "การใช้งานที่เป็นไปได้" จะใช้ประเภทความแตกต่างที่เฉพาะเจาะจงกับพารามิเตอร์แรกเสมอซึ่งโดยปกติจะเป็นประเภทอินทิกรัลและดูสมเหตุสมผล

ฉันกำลังพยายามจับเพื่อพยายามที่จะไม่ก้าวไปสู่สิ่งที่ไม่ได้กำหนด ปลอดภัยหรือไม่?

ไม่การยกเลิกการอ้างอิงหรือการเพิ่มตัววนซ้ำที่ไม่ถูกต้องเป็นพฤติกรรมที่ไม่ได้กำหนดไว้และไม่จำเป็นต้องทิ้งข้อยกเว้นใด ๆ แม้ว่าการใช้งานจำนวนมากจะให้การตรวจสอบข้อผิดพลาดอย่างกว้างขวางในการสร้างการแก้ไขข้อบกพร่องและเป็นเรื่องดีที่จะมีข้อยกเว้นเกิดขึ้น แต่การก้าวไปจนครึ่งหนึ่งของขนาดชุดจะไม่กลายเป็นปัญหา