c++ - Perl 的 Tie::IxHash(索引关联数组)的 C++ 等价物？

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