A std :: map yang melacak urutan penyisipan?

Saat ini saya memiliki std::map<std::string,int>yang menyimpan nilai integer ke pengenal string unik, dan saya mencari dengan string tersebut. Itu sebagian besar melakukan apa yang saya inginkan, kecuali untuk itu tidak melacak urutan penyisipan. Jadi ketika saya mengulang peta untuk mencetak nilai, mereka diurutkan sesuai dengan string; tetapi saya ingin mereka diurutkan menurut urutan penyisipan (pertama).

Saya berpikir untuk menggunakan a vector<pair<string,int>>sebagai gantinya, tetapi saya perlu mencari string dan menaikkan nilai integer sekitar 10.000.000 kali, jadi saya tidak tahu apakah a std::vectorakan jauh lebih lambat.

Adakah cara untuk menggunakan std::mapatau adakah stdwadah lain yang lebih sesuai dengan kebutuhan saya?

[Saya menggunakan GCC 3.4, dan saya mungkin tidak memiliki lebih dari 50 pasang nilai di std::map].

Terima kasih.

Jika Anda hanya memiliki 50 nilai di std :: map Anda dapat menyalinnya ke std :: vector sebelum mencetak dan mengurutkan melalui std :: sort menggunakan functor yang sesuai.

Atau Anda bisa menggunakan boost :: multi_index . Ini memungkinkan untuk menggunakan beberapa indeks. Dalam kasus Anda, ini akan terlihat seperti berikut:

struct value_t {
      string s;
      int    i;
};
struct string_tag {};
typedef multi_index_container<
    value_t,
    indexed_by<
        random_access<>, // this index represents insertion order
        hashed_unique< tag<string_tag>, member<value_t, string, &value_t::s> >
    >
> values_t;

Anda bisa menggabungkan a std::vectordengan std::tr1::unordered_map(tabel hash). Berikut tautan ke dokumentasi Boost untuk unordered_map. Anda dapat menggunakan vektor untuk melacak urutan penyisipan dan tabel hash untuk melakukan pencarian yang sering. Jika Anda melakukan ratusan ribu pencarian, perbedaan antara pencarian O (log n) std::mapdan O (1) untuk tabel hash mungkin signifikan.

std::vector<std::string> insertOrder;
std::tr1::unordered_map<std::string, long> myTable;

// Initialize the hash table and record insert order.
myTable["foo"] = 0;
insertOrder.push_back("foo");
myTable["bar"] = 0;
insertOrder.push_back("bar");
myTable["baz"] = 0;
insertOrder.push_back("baz");

/* Increment things in myTable 100000 times */

// Print the final results.
for (int i = 0; i < insertOrder.size(); ++i)
{
    const std::string &s = insertOrder[i];
    std::cout << s << ' ' << myTable[s] << '\n';
}

Jaga agar tetap paralel list<string> insertionOrder.

Ketika tiba waktunya untuk mencetak, lakukan iterasi pada daftar dan lakukan pencarian ke peta .

each element in insertionOrder  // walks in insertionOrder..
    print map[ element ].second // but lookup is in map

Tessil memiliki implementasi yang sangat bagus dari peta yang dipesan (dan set) yang merupakan lisensi MIT. Anda dapat menemukannya di sini: peta-dipesan

Contoh peta

#include <iostream>
#include <string>
#include <cstdlib>
#include "ordered_map.h"

int main() {
tsl::ordered_map<char, int> map = {{'d', 1}, {'a', 2}, {'g', 3}};
map.insert({'b', 4});
map['h'] = 5;
map['e'] = 6;

map.erase('a');


// {d, 1} {g, 3} {b, 4} {h, 5} {e, 6}
for(const auto& key_value : map) {
    std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
}


map.unordered_erase('b');

// Break order: {d, 1} {g, 3} {e, 6} {h, 5}
for(const auto& key_value : map) {
    std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
}
}

Jika Anda membutuhkan kedua strategi pencarian, Anda akan mendapatkan dua kontainer. Anda dapat menggunakan a vectordengan nilai aktual Anda int, dan meletakkan a di map< string, vector< T >::difference_type> sebelahnya, mengembalikan indeks ke dalam vektor.

Untuk menyelesaikan semua itu, Anda dapat merangkum keduanya dalam satu kelas.

Tapi saya yakin boost memiliki wadah dengan banyak indeks.

Apa yang Anda inginkan (tanpa menggunakan Boost) adalah apa yang saya sebut "hash yang dipesan", yang pada dasarnya adalah gabungan dari hash dan daftar tertaut dengan kunci string atau integer (atau keduanya pada saat yang sama). Hash terurut mempertahankan urutan elemen selama iterasi dengan kinerja hash yang absolut.

Saya telah menyusun pustaka cuplikan C ++ yang relatif baru yang mengisi apa yang saya lihat sebagai lubang dalam bahasa C ++ untuk pengembang pustaka C ++. Kesini:

https://github.com/cubiclesoft/cross-platform-cpp

Mengambil:

templates/detachable_ordered_hash.cpp
templates/detachable_ordered_hash.h
templates/detachable_ordered_hash_util.h

Jika data yang dikontrol pengguna akan ditempatkan ke dalam hash, Anda mungkin juga ingin:

security/security_csprng.cpp
security/security_csprng.h

Panggil itu:

#include "templates/detachable_ordered_hash.h"
...
// The 47 is the nearest prime to a power of two
// that is close to your data size.
//
// If your brain hurts, just use the lookup table
// in 'detachable_ordered_hash.cpp'.
//
// If you don't care about some minimal memory thrashing,
// just use a value of 3.  It'll auto-resize itself.
int y;
CubicleSoft::OrderedHash<int> TempHash(47);
// If you need a secure hash (many hashes are vulnerable
// to DoS attacks), pass in two randomly selected 64-bit
// integer keys.  Construct with CSPRNG.
// CubicleSoft::OrderedHash<int> TempHash(47, Key1, Key2);
CubicleSoft::OrderedHashNode<int> *Node;
...
// Push() for string keys takes a pointer to the string,
// its length, and the value to store.  The new node is
// pushed onto the end of the linked list and wherever it
// goes in the hash.
y = 80;
TempHash.Push("key1", 5, y++);
TempHash.Push("key22", 6, y++);
TempHash.Push("key3", 5, y++);
// Adding an integer key into the same hash just for kicks.
TempHash.Push(12345, y++);
...
// Finding a node and modifying its value.
Node = TempHash.Find("key1", 5);
Node->Value = y++;
...
Node = TempHash.FirstList();
while (Node != NULL)
{
  if (Node->GetStrKey())  printf("%s => %d\n", Node->GetStrKey(), Node->Value);
  else  printf("%d => %d\n", (int)Node->GetIntKey(), Node->Value);

  Node = Node->NextList();
}

Saya menemukan utas SO ini selama fase penelitian saya untuk melihat apakah sesuatu seperti OrderedHash sudah ada tanpa mengharuskan saya untuk mampir di perpustakaan besar. Aku kecewa. Jadi saya menulis sendiri. Dan sekarang saya sudah membagikannya.

Anda tidak dapat melakukannya dengan peta, tetapi Anda dapat menggunakan dua struktur yang terpisah - peta dan vektor dan membuatnya tetap sinkron - yaitu saat Anda menghapus dari peta, mencari dan menghapus elemen dari vektor. Atau Anda dapat membuat map<string, pair<int,int>>- dan pada pasangan Anda menyimpan ukuran () dari peta saat penyisipan untuk merekam posisi, bersama dengan nilai int, dan kemudian saat Anda mencetak, gunakan anggota posisi untuk mengurutkan.

Cara lain untuk mengimplementasikannya adalah dengan a mapalih - alih a vector. Saya akan menunjukkan kepada Anda pendekatan ini dan membahas perbedaannya:

Buat saja kelas yang memiliki dua peta di belakang layar.

#include <map>
#include <string>

using namespace std;

class SpecialMap {
  // usual stuff...

 private:
  int counter_;
  map<int, string> insertion_order_;
  map<string, int> data_;
};

Anda kemudian dapat menampilkan iterator ke iterator data_dalam urutan yang benar. Cara Anda melakukannya adalah melalui iterasi insertion_order_, dan untuk setiap elemen yang Anda peroleh dari iterasi itu, lakukan pencarian data_dengan nilai frominsertion_order_

Anda dapat menggunakan cara yang lebih efisien hash_mapuntuk penyisipan_order karena Anda tidak peduli tentang pengulangan secara langsung insertion_order_.

Untuk melakukan penyisipan, Anda dapat memiliki metode seperti ini:

void SpecialMap::Insert(const string& key, int value) {
  // This may be an over simplification... You ought to check
  // if you are overwriting a value in data_ so that you can update
  // insertion_order_ accordingly
  insertion_order_[counter_++] = key;
  data_[key] = value;
}

Ada banyak cara untuk membuat desain lebih baik dan mengkhawatirkan kinerja, tetapi ini adalah kerangka yang baik untuk membantu Anda mulai menerapkan fungsi ini sendiri. Anda dapat membuatnya menjadi template, dan Anda mungkin benar-benar menyimpan pasangan sebagai nilai dalam data_ sehingga Anda dapat dengan mudah mereferensikan entri di insertion_order_. Tapi saya biarkan masalah desain ini sebagai latihan :-).

Pembaruan : Saya kira saya harus mengatakan sesuatu tentang efisiensi penggunaan peta vs. vektor untuk penyisipan_order_

• pencarian langsung ke data, dalam kedua kasus adalah O (1)
• sisipan dalam pendekatan vektor adalah O (1), sisipan dalam pendekatan peta adalah O (logn)
• menghapus dalam pendekatan vektor adalah O (n) karena Anda harus memindai item yang akan dihapus. Dengan pendekatan peta mereka adalah O (logn).

Mungkin jika Anda tidak akan menggunakan penghapusan sebanyak mungkin, Anda harus menggunakan pendekatan vektor. Pendekatan peta akan lebih baik jika Anda mendukung urutan yang berbeda (seperti prioritas) daripada urutan penyisipan.

Berikut adalah solusi yang hanya membutuhkan pustaka template standar tanpa menggunakan multiindex boost:
Anda dapat menggunakan std::map<std::string,int>;dan vector <data>;di mana di peta Anda menyimpan indeks lokasi data dalam vektor dan vektor menyimpan data dalam urutan penyisipan. Di sini akses ke data memiliki kompleksitas O (log n). menampilkan data dalam urutan penyisipan memiliki kompleksitas O (n). penyisipan data memiliki kompleksitas O (log n).

Sebagai contoh:

#include<iostream>
#include<map>
#include<vector>

struct data{
int value;
std::string s;
}

typedef std::map<std::string,int> MapIndex;//this map stores the index of data stored 
                                           //in VectorData mapped to a string              
typedef std::vector<data> VectorData;//stores the data in insertion order

void display_data_according_insertion_order(VectorData vectorData){
    for(std::vector<data>::iterator it=vectorData.begin();it!=vectorData.end();it++){
        std::cout<<it->value<<it->s<<std::endl;
    }
}
int lookup_string(std::string s,MapIndex mapIndex){
    std::MapIndex::iterator pt=mapIndex.find(s)
    if (pt!=mapIndex.end())return it->second;
    else return -1;//it signifies that key does not exist in map
}
int insert_value(data d,mapIndex,vectorData){
    if(mapIndex.find(d.s)==mapIndex.end()){
        mapIndex.insert(std::make_pair(d.s,vectorData.size()));//as the data is to be
                                                               //inserted at back 
                                                               //therefore index is
                                                               //size of vector before
                                                               //insertion
        vectorData.push_back(d);
        return 1;
    }
    else return 0;//it signifies that insertion of data is failed due to the presence
                  //string in the map and map stores unique keys
}

Ini agak terkait dengan jawaban Faisal. Anda bisa membuat kelas pembungkus di sekitar peta dan vektor dan dengan mudah membuatnya tetap sinkron. Enkapsulasi yang tepat akan membiarkan Anda mengontrol metode akses dan karenanya wadah mana yang akan digunakan ... vektor atau peta. Ini menghindari penggunaan Boost atau semacamnya.

Satu hal yang perlu Anda pertimbangkan adalah jumlah kecil elemen data yang Anda gunakan. Mungkin saja akan lebih cepat menggunakan vektor saja. Ada beberapa overhead dalam peta yang dapat menyebabkan lebih mahal untuk melakukan pencarian dalam kumpulan data kecil daripada vektor yang lebih sederhana. Jadi, jika Anda tahu bahwa Anda akan selalu menggunakan elemen dengan jumlah yang sama, lakukan beberapa pembandingan dan lihat apakah kinerja peta dan vektor sesuai dengan yang Anda pikirkan. Anda mungkin menemukan pencarian dalam vektor dengan hanya 50 elemen yang hampir sama dengan peta.

// Seharusnya seperti pria ini!

// Ini menjaga kompleksitas penyisipan adalah O (logN) dan penghapusan juga O (logN).

class SpecialMap {
private:
  int counter_;
  map<int, string> insertion_order_;
  map<string, int> insertion_order_reverse_look_up; // <- for fast delete
  map<string, Data> data_;
};

Gunakan boost::multi_indexdengan peta dan daftar indeks.

Peta pasangan (str, int) dan int statis yang bertambah saat menyisipkan pasangan indeks data. Letakkan di struct yang dapat mengembalikan int val statis dengan anggota index () mungkin?