2015-12-08 12 views
5

Perl adında bir yapıya sahiptirTie::IxHash "karma emretti". Bir hashtable/map olarak kullanılabilir. Girişler ekleme sırasına göre. C++, böyle bir şey varsaC++ karma siparişi verdi mi?

Wonder.

use Tie::IxHash; 

tie %food_color, "Tie::IxHash"; 
$food_color{Banana} = "Yellow"; 
$food_color{Apple} = "Green"; 
$food_color{Lemon} = "Yellow"; 

print "In insertion order, the foods are:\n"; 
foreach $food (keys %food_color) { 
    print " $food\n"; #will print the entries in order 
} 

Güncelleme @ gibi 1

kerrek-sb, tek Çoklu endeksi Konteynerleri Kütüphane Boost kullanabilirsiniz işaret: Burada

bir örnek Perl snippet'tir. Sadece STL ile yapmak mümkün olup olmadığını merak ediyorum.

+0

Boost.Multiindex için bir iş gibi görünüyor. –

+0

Teşekkürler. Bunu bilmek güzel. Harika C++ 11'de mevcut olduğunu merak ediyorum. – packetie

+0

Bunun anlamı nedir? C++ kütüphanesi, C++ ile kullanabilirsiniz. –

cevap

2

: Bir sırasız haritası Aradığınız Ne gibi görünüyor. Hayır, kesinlikle aynı işlevselliği sağlamayı amaçlayan hiç kimse yok. Ama evet, aynısını birkaç farklı şekilde yapabilirsiniz.

std::vector<std::string, std::string> food_colors; 

food_colors.push_back({"banana", "yellow"}); 
food_colors.push_back({"apple", "green"}); 
food_colors.push_back({"lemon", "yellow"}); 

for (auto const &f : food_colors) 
    std::cout << f.first << ": " << f.second << "\n"; 

Bu sadece sırayla öğeleri depolayarak düzeni korur: Öncelikli olarak eklenen sırayla verilere erişmek için bekliyorsanız, gitmek sonra bariz yolu çiftlerinin basit vektör olacaktır. Onlara anahtar ile erişmeniz gerekiyorsa, belirli bir öğe için doğrusal arama yapmak için std::find'u kullanabilirsiniz. Bu, çok fazla öğe alırsanız anahtarla yavaş erişim pahasına kullanılan ekstra belleği en aza indirir.

Çok sayıda öğeyle daha hızlı erişim istiyorsanız, bir Boost MultiIndex kullanabilirsiniz. Bundan gerçekten kaçınmak istiyorsanız, kolayca bir dizin oluşturabilirsiniz. Bunu yapmak için, öğelerinizi std::unordered_map (veya belki de bir std::map) içine ekleyerek başlarsınız. Bu, anahtara hızlı erişim sağlar, ancak ekleme siparişinde erişim yoktur. Bununla birlikte, her bir öğeye haritaya eklendikçe bir yineleyici döndürür. Ekleme sırasına erişmek için bu yineleyicileri bir vektöre basitçe kaydedebilirsiniz. Bu prensibi oldukça basit olmasına rağmen, kod sakar tarafında biraz, güzel koymak için:

std::map<std::string, std::string> fruit; 
std::vector<std::map<std::string, std::string>::iterator> in_order; 

in_order.push_back(fruit.insert(std::make_pair("banana", "yellow")).first); 
in_order.push_back(fruit.insert(std::make_pair("apple", "green")).first); 
in_order.push_back(fruit.insert(std::make_pair("lemon", "yellow")).first); 

Bu erişim sağlar ya anahtar tarafından:

// ripen the apple: 
fruit["apple"] = "red"; 

...veya ekleme sırayla: Şu an için

for (auto i : in_order) 
    std::cout << i->first << ": " << i->second << "\n"; 

, bunu yapmak için temel mekanizma gösterdik - Daha çok kullanmak istiyorsa, muhtemelen güzel bir sınıfa o kadar tamamlamayı isterdim çirkinliğin bazılarını gizleyin ve şeyleri normal kullanımda güzel ve temiz tutun.

+0

Siparişi saklamak için bir vektör kullanmak, rasgele bir anahtarı silmek için O (n) karmaşıklığı gerektirecektir. Bu pratikte bir sorun olmayabilir, ancak bu sınırlama örn. Python'un 'OrderedDict' içinde. (Tie :: IxHash'ın silme işlemini nasıl gerçekleştirdiğini kontrol etmedim.) – user4815162342

+0

Ayrıntılı cevap ve tartışma için herkes için jerry-coffin'e teşekkürler. Şimdi daha iyi anlıyorum. Bu arada, bu konu 'Tie :: IxHash' üzerinde silme durumunda etkili olmadığını gördüm: http://stackoverflow.com/questions/5344512/how-is-tieixhash-implemented-in-perl – packetie

+0

İlk durumda (çiftlerin vektörü) sanırım bir ikili arama olan anahtarlar üzerinde yineleme yaparak aradığınız öğenin dizinini almak için std :: lower_bound kullanmak mümkündür. – ChatterOne

1

C++ standart kütüphane ile gelmiyor kampanya siparişini hatırlar ilişkilendirilebilir bir konteyner, ancak mevcut STL kapları kullanarak bir uygulamaya basittir. Örneğin, std::map (hızlı arama için) ve std::list (anahtar sıralamasını korumak için) birleşimi, ekleme siparişi verilen bir haritaya öykünmek için kullanılabilir.

#include <unordered_map> 
#include <list> 
#include <stdexcept> 

template<typename K, typename V> 
class InsOrderMap { 
    struct value_pos { 
    V value; 
    typename std::list<K>::iterator pos_iter; 
    value_pos(V value, typename std::list<K>::iterator pos_iter): 
     value(value), pos_iter(pos_iter) {} 
    }; 

    std::list<K> order; 
    std::unordered_map<K, value_pos> map; 

    const value_pos& locate(K key) const { 
    auto iter = map.find(key); 
    if (iter == map.end()) 
     throw std::out_of_range("key not found"); 
    return iter->second; 
    } 

public: 
    void set(K key, V value) { 
    auto iter = map.find(key); 
    if (iter != map.end()) { 
     // no order change, just update value 
     iter->second.value = value; 
     return; 
    } 
    order.push_back(key); 
    map.insert(std::make_pair(key, value_pos(value, --order.end()))); 
    } 

    void erase(K key) { 
    order.erase(locate(key).pos_iter); 
    map.erase(key); 
    } 

    V operator[](K key) const { 
    return locate(key).value; 
    } 

    // iterate over the mapping with a function object 
    // (writing a real iterator is too much code for this example) 
    template<typename F> 
    void walk(F fn) const { 
    for (auto key: order) 
     fn(key, (*this)[key]); 
    } 
}; 

// TEST 

#include <string> 
#include <iostream> 
#include <cassert> 

int main() 
{ 
    typedef InsOrderMap<std::string, std::string> IxHash; 

    IxHash food_color; 
    food_color.set("Banana", "Yellow"); 
    food_color.set("Apple", "Green"); 
    food_color.set("Lemon", "Yellow"); 

    assert(food_color["Banana"] == std::string("Yellow")); 
    assert(food_color["Apple"] == std::string("Green")); 
    assert(food_color["Lemon"] == std::string("Yellow")); 

    auto print = [](std::string k, std::string v) { 
    std::cout << k << ' ' << v << std::endl; 
    }; 
    food_color.walk(print); 
    food_color.erase("Apple"); 
    std::cout << "-- without apple" << std::endl; 
    food_color.walk(print); 
    return 0; 
} 

std::map hatırı sayılır çaba gerektirir gibi tam teşekküllü kap için bir drop-in yerine bu kodu Geliştirme: Burada fikir gösteren bir örnektir.

+0

Ayrıntılı @ cevap için @ kullanıcı4815162342 teşekkürler. – packetie

-2

C++ bunun için standart konteyner vardır. Evet ve hayır

std::unordered_map <std::string, std::string> mymap = {{"Banana", "Yellow" }, {"Orange","orange" } } 
+3

Lütfen yanıtlamadan önce soruyu okuyun –