Is there a set type that preserves insertion order?

Question

Is there a type that preserves insertion order (think Vec) but only tracks unique values (think HashSet)? I want to avoid using Vec because I would first need to check if the value exists in it before insertion.

Answer 1

linked_hash_set crate is now available. It's based on the linked-hash-map crate mirroring the std HashSet API as closely as possible.

extern crate linked_hash_set;
use linked_hash_set::LinkedHashSet;

let mut set = LinkedHashSet::new();
set.insert(234);
set.insert(123);
set.insert(345);
set.insert(123);

assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![234, 345, 123]);

Answer 2

The linked-hash-map crate provides a hash map that holds key-value insertion order. We can create a set wrapper for this hash map using () as values (std::collections::HashSet is implemented this way):

extern crate linked_hash_map;

use linked_hash_map::*;
use std::collections::hash_map::RandomState;
use std::hash::{BuildHasher, Hash};
use std::borrow::Borrow;

fn main() {
    let mut s = LinkedHashSet::new();
    s.insert(5);
    s.insert(3);
    s.insert(7);
    s.insert(1);
    assert_eq!(vec![5, 3, 7, 1], s.iter().cloned().collect::<Vec<_>>());
    s.remove(&7);
    assert_eq!(vec![5, 3, 1], s.iter().cloned().collect::<Vec<_>>());
    s.remove(&5);
    assert_eq!(vec![3, 1], s.iter().cloned().collect::<Vec<_>>());
}

pub struct LinkedHashSet<K, S = RandomState>(LinkedHashMap<K, (), S>);

impl<K: Hash + Eq> LinkedHashSet<K> {
    pub fn new() -> Self {
        LinkedHashSet(LinkedHashMap::new())
    }
}

impl<K: Hash + Eq, S: BuildHasher> LinkedHashSet<K, S> {
    pub fn insert(&mut self, k: K) -> Option<()> {
        self.0.insert(k, ())
    }

    pub fn contains<Q: ?Sized>(&self, k: &Q) -> bool
        where K: Borrow<Q>,
              Q: Eq + Hash
    {
        self.0.contains_key(k)
    }

    pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<()>
        where K: Borrow<Q>,
              Q: Eq + Hash
    {
        self.0.remove(k)
    }

    pub fn iter(&self) -> Keys<K, ()> {
        self.0.keys()
    }
}

You can implement other methods. See LinkedHashMap docs.