c++ - C++ は Perl の Tie::IxHash (インデックス付き連想配列) に相当しますか?

Question

Perl の IxHash は、要素が追加された順序を記憶する連想配列であり、キーまたはインデックスによって直接 (O(1)) アクセスできます。また、すべてのキーまたは値を、常に最初に挿入された順序で返すメソッドもあります。

C++ 用の同等のコンテナー クラスはありますか?

Answer 1

deque (または array ) と unordered_map の複合を考えてみましょう。削除する必要がある場合は、O(n) になります (ixhash と同様)。それらのキーを反復することは、汚いハックです。キーと値の実際の反復子が必要な場合は、boost iterator_facade を参照してください。

#include <unordered_map>
#include <deque>
#include <iterator>
#include <iostream>

using namespace std;

template <typename KeyType, typename ValueType>
class MapWithInsertionOrder {
    public:
        bool exists(const KeyType &kk)
        {
            return cache_.find(kk) != cache_.end();
        }

        bool store(const KeyType &kk, const ValueType &vv)
        {
            if (exists(kk))
            {
                return false;
            }
            keys_.push_back(kk);
            cache_.insert(make_pair(kk, vv));

        }

        typedef unordered_map<KeyType,ValueType> cache_type;
        typedef typename cache_type::value_type value_type;

        typedef deque<KeyType> order_type;
        typedef typename order_type::iterator order_iterator;

        value_type &fetch(const KeyType &kk)
        {
            return *cache_.find(kk);
        }

        value_type &at(size_t idx)
        {
            auto kk = keys_.at(idx);
            return fetch(kk);
        }

        size_t size()
        {
            return keys_.size();
        }

        order_iterator keys_begin()
        {
            return keys_.begin();
        }

        order_iterator keys_end()
        {
            return keys_.end();
        }

    private:

        order_type keys_;
        cache_type cache_;

};

int main()
{
    MapWithInsertionOrder<string, string> mm;

    mm.store( "cat", "tom" );
    mm.store( "mouse", "jerry" );
    mm.store( "bird", "tweety" );
    mm.store( "dog", "spike" );

    cout << mm.at(0).second << endl;
    cout << mm.at(1).second << endl;
    cout << mm.at(2).second << endl;

    cout << mm.exists("cat") << endl;
    cout << mm.exists("mouse") << endl;
    cout << mm.exists("dog") << endl;

    for( auto itr = mm.keys_begin();itr != mm.keys_end();itr++ )
    {
        cout << *itr << endl;
    }
    return 0;
}