Geek Answers Handbook

Is there such a thing as an associative queue?

I need a clojure data structure that:

  • appears from the front
  • pushing back
  • allows me to associate indices with values ​​(i.e. (assoc q 0 1) sets the value before 1)

Is there something similar in clojure (unfortunately PersistentQueue does not match Nr.3), or did I have to create it on top of the vector?

+6
source share
4 answers

The Clojure standard does not have a data structure that will effectively meet these requirements.

The Clojure -Dev mailing list talked about how to use RRB trees for vectors, which would be a good data structure for this:

I don’t know how far this has developed, but if you are interested in the structure of this type of data, then it is certainly worth a look at this.

+1
source

If you do not require a persistent data structure, you can use java.util.LinkedList in your Clojure programs.

Example:

 ;;; Creation user> (import 'java.util.LinkedList) java.util.LinkedList user> (def linked-list (LinkedList. [:a :b :c :d :e])) #'user/linked-list ;;; Pop from the front user> (.pop ^LinkedList linked-list) :a user> linked-list #<LinkedList [:b, :c, :d, :e]> ;;; Push to the rear, but costly user> (.addLast ^LinkedList linked-list :x) nil user> linked-list #<LinkedList [:b, :c, :d, :e, :x]> ;;; Assoc (cf. (assoc linked-list 0 :y) user> (.add ^LinkedList linked-list 0 :y) nil user> linked-list #<LinkedList [:y, :b, :c, :d, :x]>
+1
source

You can use sorted-map , but you will have to implement part of the index yourself.

For example, to press v, you can associate it with a key created by increasing the last key on the map. To pop, you can break the first key on the map.

0
source

It looks like you need a deck like python deque , except that you may prefer indexed access performance characteristics for C ++ std::deque<T> , the documentation is somewhat dumb.

Java comes with java.util.Deque implementations that you could use, just like the @tnoda java.util.LinkedList clause.

If you rode on your own, the implementation is quite simple for a fickle collection and seems to me intuitive enough, at least for the implementation against the "hashed arrays" underlying clojure hashmap and vector, or directly against the vector initially, if the details annoy you.

0
source

More articles:


All Articles