ไลบรารีมาตรฐาน C ++ มีชุดที่เรียงลำดับตามคำสั่งการแทรกหรือไม่

ไม่มีโครงสร้างข้อมูลที่เป็นเนื้อเดียวกันเดี่ยวใดจะมีคุณสมบัตินี้ เนื่องจากเป็นแบบต่อเนื่อง (เช่น องค์ประกอบถูกจัดเรียงตามลำดับการแทรก) หรือแบบเชื่อมโยง (องค์ประกอบถูกจัดเรียงตามลำดับขึ้นอยู่กับค่า)

แนวทางที่ดีที่สุดและสะอาดที่สุดอาจเป็นเช่น Boost.MultiIndex ซึ่งช่วยให้คุณสามารถเพิ่มหลายรายการได้ ดัชนีหรือ "มุมมอง" บนคอนเทนเนอร์ เพื่อให้คุณสามารถมีดัชนีตามลำดับและลำดับได้

แทนที่จะสร้าง std::set ประเภทใดก็ตามที่คุณใช้อยู่ ทำไมไม่ลองส่ง std::pair ของอ็อบเจ็กต์และดัชนีที่จะเพิ่มขึ้นในการแทรกแต่ละครั้งล่ะ

ไม่มันไม่ได้

คอนเทนเนอร์ดังกล่าวน่าจะต้องใช้ตัววนซ้ำที่แตกต่างกันสองตัว ตัวหนึ่งเพื่อวนซ้ำตามลำดับที่กำหนดโดยลำดับการเพิ่ม และอีกตัวหนึ่งเพื่อวนซ้ำตามลำดับ set ปกติ ไม่มีอะไรแบบนั้นในไลบรารีมาตรฐาน

ทางเลือกหนึ่งในการจำลองคือการมี set บางประเภทที่มีโหนดรายการเชื่อมโยงที่ล่วงล้ำ นอกเหนือจากข้อมูลจริงที่คุณสนใจ หลังจากเพิ่มองค์ประกอบใน set แล้ว ให้ผนวกเข้ากับรายการที่เชื่อมโยง ก่อนที่จะลบองค์ประกอบออกจาก set ให้ลบออกจากรายการที่เชื่อมโยง รับประกันว่าจะใช้ได้ เนื่องจากตัวชี้สำหรับตั้งค่าองค์ประกอบจะไม่ทำให้ใช้งานไม่ได้โดยการดำเนินการใดๆ นอกเหนือจากการลบองค์ประกอบนั้น

ฉันคิดว่าคำตอบนั้นค่อนข้างง่าย รวมชุดเข้ากับโครงสร้างที่ทำซ้ำได้อื่น (เช่น คิว) หากคุณต้องการวนซ้ำชุดตามลำดับที่องค์ประกอบถูกแทรก ให้ดันองค์ประกอบในคิวก่อน ทำงานของคุณกับองค์ประกอบด้านหน้า จากนั้นจึงเด้งออกมา ใส่เข้าไปในชุด

[ข้อจำกัดความรับผิดชอบ: ฉันได้ให้คำตอบที่คล้ายกันกับคำถามนี้ แล้ว]

หากคุณสามารถใช้ Boost ได้ วิธีแก้ปัญหาที่ตรงไปตรงมามากคือใช้ไลบรารี่เฉพาะส่วนหัว Boost.Bimap (แผนที่แบบสองทิศทาง)

พิจารณาโปรแกรมตัวอย่างต่อไปนี้ที่จะแสดงรายการจำลองบางส่วนตามลำดับการแทรก (ลองที่นี่ ):

#include <iostream>
#include <string>
#include <type_traits>
#include <boost/bimap.hpp>

using namespace std::string_literals;

template <typename T>
void insertByOrder(boost::bimap<T, size_t>& mymap, const T& element) {
  using pos = typename std::remove_reference<decltype(mymap)>::type::value_type;
  // We use size() as index, therefore indexing the elements with 0, 1, ...
  mymap.insert(pos(element, mymap.size()));
}

int main() {
  boost::bimap<std::string, size_t> mymap;

  insertByOrder(mymap, "stack"s);
  insertByOrder(mymap, "overflow"s);

  // Iterate over right map view (integers) in sorted order
  for (const auto& rit : mymap.right) {
    std::cout << rit.first << " -> " << rit.second << std::endl;
  }
}

จำเป็นต้องใช้นามแฝงประเภท funky ใน insertByOrder() เพื่อแทรกองค์ประกอบลงใน boost::bimap ในบรรทัดต่อไปนี้ (ดูเอกสารอ้างอิง)

ใช่ มันเรียกว่าเวกเตอร์หรือรายการ (หรืออาร์เรย์) เพียงต่อท้ายเวกเตอร์เพื่อเพิ่มองค์ประกอบให้กับเซต