Does anybody has some code for associative ordered container
something like c++ map http://www.cplusplus.com/reference/stl/map/
Hash-table won't do as elements must stay ordered by order of entry.
Slobodan
On Jun 21, 1:50 pm, Slobodan Blazeski <·················@gmail.com>
wrote:
> Does anybody has some code for associative ordered container
> something like c++ maphttp://www.cplusplus.com/reference/stl/map/
> Hash-table won't do as elements must stay ordered by order of entry.
Well, if I understand you correctly, an STL map wouldn't work either;
it keeps the keys in some predetermined (albeit user-specified) order,
not the order of entry. The ordering is critical to the lookup
operation; it can't be arbitrary.
I think you'll just have to use some kind of sequence and some kind of
associative container together.
Of course I recommend FSet :)
-- Scott
On Jun 22, 7:17 am, Scott Burson <········@gmail.com> wrote:
> On Jun 21, 1:50 pm, Slobodan Blazeski <·················@gmail.com>
> wrote:
>
> > Does anybody has some code for associative ordered container
> > something like c++ maphttp://www.cplusplus.com/reference/stl/map/
> > Hash-table won't do as elements must stay ordered by order of entry.
>
> Well, if I understand you correctly, an STL map wouldn't work either;
> it keeps the keys in some predetermined (albeit user-specified) order,
> not the order of entry. The ordering is critical to the lookup
> operation; it can't be arbitrary.
>
> I think you'll just have to use some kind of sequence and some kind of
> associative container together.
Simple solution of hash-table + vector will do.
(defclass ordered-map ()
(hash-table adjustable-vector))
(defun insert-element (key element ordered-map)
(setf (gethash key (ordered-map hash-table)) element)
(vector-push-extend element (ordered-map vector)))
>
> Of course I recommend FSet :)
What are the advantages of fset to above approach?
>
> -- Scott
On Jun 22, 2:44 am, Slobodan Blazeski <·················@gmail.com>
wrote:
[...]
> > I think you'll just have to use some kind of sequence and some kind of
> > associative container together.
> Simple solution of hash-table + vector will do.
> (defclass ordered-map ()
> (hash-table adjustable-vector))
> (defun insert-element (key element ordered-map)
> (setf (gethash key (ordered-map hash-table)) element)
> (vector-push-extend element (ordered-map vector)))
If you're going to be deleting elements, you might want to use a list
with a tail pointer instead of an adjustable vector. For each key,
store a cons in the hash-table where the car is the value and the cdr
is the tail-pointer from when it was inserted. Then you just need a
GETHASH, a RPLACD and a REMHASH to get rid of an element.
Cheers,
Pillsy
Pillsy <·········@gmail.com> writes:
> On Jun 22, 2:44�am, Slobodan Blazeski <·················@gmail.com>
> wrote:
> [...]
>> > I think you'll just have to use some kind of sequence and some kind of
>> > associative container together.
>
>> Simple solution of hash-table + vector will do.
>> (defclass ordered-map ()
>> � (hash-table adjustable-vector))
>
>> (defun insert-element (key element ordered-map)
>> � �(setf (gethash key (ordered-map hash-table)) element)
>> � �(vector-push-extend �element (ordered-map vector)))
>
> If you're going to be deleting elements, you might want to use a list
> with a tail pointer instead of an adjustable vector. For each key,
> store a cons in the hash-table where the car is the value and the cdr
> is the tail-pointer from when it was inserted. Then you just need a
> GETHASH, a RPLACD and a REMHASH to get rid of an element.
You mean the cadr is the value. You must keep a reference to the
previous (or next depending on the order in which you keep the values
in the list) cons cell to remove it.
Also, it would be perfectly possible to delete elements from a vector
in O(1) amortized.
(defvar +deleted+ (cons nil nil))
(setf (aref (ordered-map-entries om) index) +deleted+)
(incf (ordered-map-deleted-count om))
So reading the vector in either order is still O(n), When
(< (* 2 (ordered-map-deleted-count om)) (ordered-map-size om))
you may reduce the size of the vector and pack it. (but if you're
still adding elements, then you will pack the vector when it has to be
extended).
--
__Pascal Bourguignon__
On Jun 23, 4:27 am, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> Pillsy <·········@gmail.com> writes:
[...]
> > If you're going to be deleting elements, you might want to use a list
> > with a tail pointer instead of an adjustable vector. For each key,
> > store a cons in the hash-table where the car is the value and the cdr
> > is the tail-pointer from when it was inserted. Then you just need a
> > GETHASH, a RPLACD and a REMHASH to get rid of an element.
> You mean the cadr is the value. You must keep a reference to the
> previous (or next depending on the order in which you keep the values
> in the list) cons cell to remove it.
That's why you keep the old tail-pointer in the CDR, though.
(defun add-to-omap (value key omap)
(with-slots (tail list table) omap
(if (null list)
(setf list (list key)
tail list
(gethash key table) (cons value tail))
(setf (gethash key table) (cons value tail)
(cdr tail) (list key)
tail (cdr tail))))
value)
(defun remove-from-omap (key omap)
(with-slots (table) omap
(let ((cell (cdr (gethash key table))))
(setf (cdr cell) (cddr cell))
(remhash key table))))
* (add-to-omap 3 'a *omap*)
3
* (add-to-omap 'foo 'bar *omap*)
FOO
* (add-to-omap "this" 'that *omap*)
"this"
* (slot-value *omap* 'list)
(A BAR THAT)
* (remove-from-omap 'bar *omap*)
T
* (slot-value *omap* 'list)
(A THAT)
> Also, it would be perfectly possible to delete elements from a vector
> in O(1) amortized.
That's a good point.
Cheers,
Pillsy
* Slobodan Blazeski
Wrote on Sun, 21 Jun 2009 23:44:00 -0700 (PDT):
|> I think you'll just have to use some kind of sequence and some kind of
|> associative container together.
| Simple solution of hash-table + vector will do.
An even simpler solution would be to use an Association lists
initialized to (NIL), with ASSOC to do lookups.
--
Madhu
* Slobodan Blazeski
Wrote on Sun, 21 Jun 2009 23:44:00 -0700 (PDT):
|> I think you'll just have to use some kind of sequence and some kind of
|> associative container together.
| Simple solution of hash-table + vector will do.
An even simpler solution would be to use Association lists
initialized to (NIL), with ASSOC to do lookups.
--
Madhu
On Jun 21, 11:44 pm, Slobodan Blazeski <·················@gmail.com>
wrote:
> On Jun 22, 7:17 am, Scott Burson <········@gmail.com> wrote:> On Jun 21, 1:50 pm, Slobodan Blazeski <·················@gmail.com>
>
> > Of course I recommend FSet :)
>
> What are the advantages of fset to above approach?
Probably none, in this case. FSet is most useful when you're passing
around collections as values; sounds like you just want a data
structure for an algorithm.
-- Scott
Scott Burson wrote:
> On Jun 21, 1:50 pm, Slobodan Blazeski <·················@gmail.com>
> wrote:
>> Does anybody has some code for associative ordered container
>> something like c++ maphttp://www.cplusplus.com/reference/stl/map/
>> Hash-table won't do as elements must stay ordered by order of entry.
>
> Well, if I understand you correctly, an STL map wouldn't work either;
> it keeps the keys in some predetermined (albeit user-specified) order,
> not the order of entry. The ordering is critical to the lookup
> operation; it can't be arbitrary.
>
> I think you'll just have to use some kind of sequence and some kind of
> associative container together.
I think he believes that iterating the pairs in a std::map will return
keys in the same order they were inserted. This is possibly true in
some implementations, but I don't see it specified anywhere.
Restated, I think Slobodan is asking for a CL hashtable where the
traversal of MAPHASH matches the insertion order.
- Daniel
On Jun 22, 8:09 am, D Herring <········@at.tentpost.dot.com> wrote:
> Scott Burson wrote:
> > On Jun 21, 1:50 pm, Slobodan Blazeski <·················@gmail.com>
> > wrote:
> >> Does anybody has some code for associative ordered container
> >> something like c++ maphttp://www.cplusplus.com/reference/stl/map/
> >> Hash-table won't do as elements must stay ordered by order of entry.
>
> > Well, if I understand you correctly, an STL map wouldn't work either;
> > it keeps the keys in some predetermined (albeit user-specified) order,
> > not the order of entry. The ordering is critical to the lookup
> > operation; it can't be arbitrary.
>
> > I think you'll just have to use some kind of sequence and some kind of
> > associative container together.
>
> I think he believes that iterating the pairs in a std::map will return
> keys in the same order they were inserted. This is possibly true in
> some implementations, but I don't see it specified anywhere.
My mistake, I knew that c++ map keeps element ordered but not under
order I want.
>
> Restated, I think Slobodan is asking for a CL hashtable where the
> traversal of MAPHASH matches the insertion order.
That's right.
Slobodan
>
> - Daniel
* Slobodan Blazeski
Wrote on Sun, 21 Jun 2009 13:50:09 -0700 (PDT):
| Does anybody has some code for associative ordered container
| something like c++ map http://www.cplusplus.com/reference/stl/map/
| Hash-table won't do as elements must stay ordered by order of entry.
The question is suspect. Your "Associative" requirement implies items
are accessed by some "key-value" API. The "Ordered" requirement means
the keys can be compared and ordered by some COMPARE operation. When
you talk of both in the same sentence you would be doing associative
lookups (via an assoc like API) while implementing the data structure
using the ordering information. BTREEs, PQUEUES (Priority queues,
heaps), TREAPS (randomized heaps), are all datastructures that implement
an "Associative Map" using underlying "Ordering" to provide certain
access characterstics.
Several implementations exist (even on my harddisk, implementations i've
gotten off the internet), I'm sure youve seen them.
What is your real question? (about ordering?)
--
Madhu