Apakah perpustakaan standar C++ memiliki kumpulan yang diurutkan berdasarkan urutan penyisipan?

Tidak ada struktur data tunggal dan homogen yang memiliki sifat ini, karena sifatnya yang berurutan (yaitu elemen disusun dalam urutan penyisipan) atau asosiatif (elemen disusun dalam urutan tertentu bergantung pada nilainya).

Pendekatan terbaik dan bersih mungkin seperti Boost.MultiIndex, yang memungkinkan Anda menambahkan beberapa indeks, atau "tampilan", pada sebuah wadah, sehingga Anda dapat memiliki indeks yang berurutan dan terurut.

Daripada membuat std::set dengan tipe apa pun yang Anda gunakan, mengapa tidak memberikannya std::pair objek dan indeks yang bertambah pada setiap penyisipan?

Tidak.

Wadah seperti itu mungkin memerlukan dua iterator yang berbeda, satu untuk melakukan iterasi dalam urutan yang ditentukan oleh urutan penambahan, dan satu lagi untuk melakukan iterasi dalam urutan set biasa. Tidak ada hal semacam itu di perpustakaan standar.

Salah satu opsi untuk mensimulasikannya adalah dengan memiliki set dari beberapa tipe yang berisi node daftar tertaut yang mengganggu selain data aktual yang Anda pedulikan. Setelah menambahkan elemen ke set, tambahkan elemen tersebut ke daftar tertaut. Sebelum menghapus elemen dari set, hapus elemen tersebut dari daftar tertaut. Ini dijamin OK, karena pointer ke elemen set tidak dibatalkan oleh operasi apa pun selain menghapus elemen tersebut.

Saya pikir jawabannya cukup sederhana, gabungkan set dengan struktur lain yang dapat diulang (misalnya, antrian). Jika Anda ingin mengulangi himpunan sesuai urutan penyisipan elemen, dorong elemen ke dalam antrian terlebih dahulu, lakukan pekerjaan Anda pada elemen depan, lalu keluarkan, masukkan ke dalam himpunan.

[Penafian: Saya telah memberikan jawaban serupa untuk pertanyaan ini sudah]

Jika Anda dapat menggunakan Boost, solusi yang sangat mudah adalah dengan menggunakan pustaka khusus header Boost.Bimap (peta dua arah).

Pertimbangkan contoh program berikut yang akan menampilkan beberapa entri dummy dalam urutan penyisipan (coba di sini ):

#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;
  }
}

Alias ​​tipe funky di insertByOrder() diperlukan untuk menyisipkan elemen ke dalam boost::bimap di baris berikut (lihat dokumentasi referensi).

Ya, itu disebut vektor atau daftar (atau array). Cukup tambahkan ke vektor untuk menambahkan elemen ke set.