vala - 如何在 Vala 的 HashMap 中保留插入顺序

Question

我正在使用 HashMap。当我遍历 map 时，数据以(通常是相同的)随机顺序返回。但是数据是按特定顺序插入的，我需要保留插入顺序。我怎样才能在 Vala 中做到这一点？在 Java 中有 LinkedHashMap，但我没有看到 Gee.Map 的任何等效项。

Answer 1

据我所知，Vala 中没有 LinkedHashMap 的等价物。使用 TreeMap 并将比较函数设置为始终为其他 Map 条目返回 1(如果您想要相反的顺序，则为 -1)将保留顺序并允许您按照添加项目的顺序遍历 Map 但 get 将无法按预期运行。

不幸的是，在彻底检查 Gee 源之后，除了自己动手，似乎别无他法。最直接的方法是继承 HashMap 并使用 ArrayList 来跟踪键插入时的顺序。您也可以使用 LinkedList，只需将内部 ArrayList _keys 字段更改为 LinkedList。选择取决于您的用例。来自文档-

This implementation (ArrayList) is pretty good for rarely modified data. Because they are stored in an array this structure does not fit for highly mutable data.

下面是一个基本的实现，在 Vala (arrayhashmap.vala) 中:

using Gee;

public class ArrayHashMap<K,V> : HashMap<K,V> {

    private weak Set<K> _keyset;
    private weak Collection<V> _values;
    private weak Set<Entry<K,V>> _entries;
    internal ArrayList<K> _keys = new ArrayList<K>();

    private class KeySet<K> : AbstractSet<K> {

        private weak ArrayList<K> _keys;

        public KeySet (ArrayList<K> keys) {
            _keys = keys;
        }

        public override Iterator<K> iterator () {
            return _keys.iterator();
        }

        public override int size {
            get { return _keys.size; }
        }

        public override bool read_only {
            get { return true; }
        }

        public override bool add (K key) {
            assert_not_reached ();
        }

        public override void clear () {
            assert_not_reached ();
        }

        public override bool remove (K key) {
            assert_not_reached ();
        }

        public override bool contains (K key) {
            return _keys.contains (key);
        }
    }

    private class ValueCollection<K,V> : AbstractCollection<V> {
        private weak ArrayHashMap<K,V> _map;

        public ValueCollection (ArrayHashMap map) {
            _map = map;
        }

        public override Iterator<V> iterator () {
            return new ValueIterator<K,V> (_map);
        }

        public override int size {
            get { return _map.size; }
        }

        public override bool read_only {
            get { return true; }
        }

        public override bool add (V value) {
            assert_not_reached ();
        }

        public override void clear () {
            assert_not_reached ();
        }

        public override bool remove (V value) {
            assert_not_reached ();
        }

        public override bool contains (V value) {
            Iterator<V> it = iterator ();
            while (it.next ()) {
                if (_map.value_equal_func (it.get (), value)) {
                    return true;
                }
            }
            return false;
        }
    }

    private class ValueIterator<K,V> : Object, Traversable<V>, Iterator<V> {
        protected weak ArrayHashMap<K,V> _map;
        protected Iterator<K> _keys;

        public ValueIterator (ArrayHashMap<K,V> map) {
            _map = map;
            _keys = map._keys.iterator();
        }

        public bool next () {
            return _keys.next();
        }

        public bool has_next () {
            return _keys.has_next();
        }

        public virtual bool read_only {
            get {
                return true;
            }
        }

        public bool valid {
            get {
                return _keys.valid;
            }
        }

        public new V get () {
            return _map.get(_keys.get());
        }

        public void remove () {
            assert_not_reached ();
        }

        public bool foreach(ForallFunc<V> f) {
            foreach (K key in _map._keys)
                if (!f(_map.get(key)))
                    return false;
            return true;
        }
    }

    private class EntrySet<K,V> : AbstractSet<Entry<K, V>> {
        private weak ArrayHashMap<K,V> _map;

        public EntrySet (ArrayHashMap<K,V> map) {
            _map = map;
        }

        public override Iterator<Entry<K, V>> iterator () {
            return new EntryIterator<K,V> (_map);
        }

        public override int size {
            get { return _map.size; }
        }

        public override bool read_only {
            get { return true; }
        }

        public override bool add (Entry<K, V> entry) {
            assert_not_reached ();
        }

        public override void clear () {
            assert_not_reached ();
        }

        public override bool remove (Entry<K, V> entry) {
            assert_not_reached ();
        }

        public override bool contains (Entry<K, V> entry) {
            return _map.has (entry.key, entry.value);
        }
    }

    private class EntryIterator<K,V> : Object, Traversable<Entry<K,V>>, Iterator<Entry<K,V>> {
        protected weak ArrayHashMap<K,V> _map;
        protected Iterator<K> _keys;

        public EntryIterator (ArrayHashMap<K,V> map) {
            _map = map;
            _keys = map._keys.iterator();
        }

        public bool next () {
            return _keys.next();
        }

        public bool has_next () {
            return _keys.has_next();
        }

        public virtual bool read_only {
            get {
                return true;
            }
        }

        public bool valid {
            get {
                return _keys.valid;
            }
        }

        public new Entry<K,V> get () {
            K* k = _keys.get();
            var ent = new Entry<K,V>(k, _map.get(k));
            return ent;
        }

        public void remove () {
            assert_not_reached ();
        }

        public bool foreach(ForallFunc<Entry<K,V>> f) {
            foreach (K key in _map._keys)
                if (!f(new Entry<K,V>(key, _map.get(key))))
                    return false;
            return true;
        }
    }

    public class Entry<K,V> : Map.Entry<K,V> {
        weak K _key;
        weak V _value;

        public override K key {
            get {
                return _key;
            }
        }

        public override V value {
            get {
                return _value;
            } set {
                _value = value;
            }
        }

        public override bool read_only {get { return true; }}

        public Entry (K key, V value) {
            this._key = key;
            this._value = value;
        }
    }

    public new void @set(K key, V value) {
        if (!_keys.contains(key))
        _keys.add(key);
        base.set(key, value);
    }

    public new void unset(K key, out V? value = null) {
        _keys.remove(key);
        base.unset(key, out value);
    }

    public new void clear() {
        base.clear();
        _keys.clear();
    }

    public new Set<unowned K> keys {
        owned get {
            Set<K> keys = _keyset;
            if (_keyset == null) {
                keys = new KeySet<K> (_keys);
                _keyset = keys;
                keys.add_weak_pointer ((void**) (&_keyset));
            }
            return keys;
        }
    }

    public new Collection<unowned V> values {
        owned get {
            Collection<K> values = _values;
            if (_values == null) {
                values = new ValueCollection<K,V> (this);
                _values = values;
                values.add_weak_pointer ((void**) (&_values));
            }
            return values;
        }
    }

    public override Set<Entry<K,V>> entries {
        owned get {
            Set<Entry<K,V>> entries = _entries;
            if (_entries == null) {
                entries = new EntrySet<K,V> (this);
                _entries = entries;
                entries.add_weak_pointer ((void**) (&_entries));
            }
            return entries;
        }
    }

}

你可以用这个糟糕的测试用例 (tests.vala) 来测试它:

public static void doTest() {
    const string[] strings = { "test", "another", "one-more", "how-about-this-one", "even-more" };

    var entries3 = new ArrayHashMap<string, int>();

    for (int i = 0; i < strings.length; i++)
        entries3.set(strings[i], i);

    entries3.unset("one-more");

    foreach (var entry in entries3.keys)
        message ("%s:%d", entry, entries3.get(entry));

    entries3.set ("for-your-viewing-pleasure", 3);

    foreach (var entry in entries3.keys)
        message ("%s:%d", entry, entries3.get(entry));

    entries3.set ("for-your-viewing-pleasure", 7);

    foreach (var entry in entries3.entries)
        message ("%s:%d", entry.key, entries3.get(entry.key));

}

public static int main (string[] args) {
    Test.init(ref args);
    Test.add_func ("/ArrayHashMap", doTest);
    Test.run();
    return 0;
}

一起运行整个包:

valac --pkg gee-0.8 -g tests.vala arrayhashmap.vala

这是一个非常粗略的实现，基于 HashMap 的内部工作方式。您可能想要重构它以获得更好的可维护性并编写更多单元测试。如果您发现任何问题，请告诉我，我们可以解决这些问题。

希望对您有所帮助。