Re: Constant time search in list.
On Feb 22, 3:57 pm, Amit Bhatia <amit.bhatia.nos...@nospam.com> wrote:
* Amit Bhatia:
Hi,
I am not sure if this belongs to this group. Anyway, my question is=
as
follows: I have a list (STL list) whose elements are pairs of intege=
rs (STL
pairs, say objects of class T). When I create a new object of class =
T, I
would like to check if this object already exists in the list: meani=
ng one
having same integers. This can be done in linear time in a list, and
probably faster if I use STL Set instead of list. I am wondering how=
ever if
its possible to do it in constant time, and use list the the same ti=
me. I
read something about using lookup function on a hash, but I don't wa=
nt to
go
away from using a list.
Arranging the elements of the list is not important to me, hence a =
Set is
not exactly what I am looking for.
You can use a hash in addition to the list; package both in some wrap=
per
object that enforces the policy of updating the hash when adding or
removing an element. You can also use a std::map, if as you indicate
they keys are unique, but it depends on what functionality of lists y=
ou
are using. Also, it won't buy you constant time, but logarithmic tim=
e,
which is often in practice good enough.
Thanks. I am using constant time removal and insertion of elements in
between mainly. Could you please explain in a slightly more detail how=
to go
about using the hash in addition to a list (I have never used a hash
before)?
I think Alf meant that you could create a class that contains both a
hashmap and a list, and when you insert an element in your class you
insert it both in your list and the hashmap. This gives you constant
insertion time when the element is not already stored, but linear time
if it is or when deleting (since you then have to search the list).
A hashmap is a datastructure on its own, just like a list or map, in C+
+ you need to have a fairly new standard library which is updated to
TR1 or use a third party implementation. The one in TR1 is called
unordered_map and works just like a map, you can insert items using
the []operator. The difference from a map is that inserting and
finding elements in general is faster (though I think worst case is
linear).
I think I am using g++ version 3.3 or so. So from what I understand,
hash_map still does not invalidate iterators pointing to objects upon
deletion and insertion, but does not allow insertion or deletion in const=
ant
time? does the hash_map also has the ability to return iterator in case o=
ne
instance of the object is found (in constant time)?
Well, hash_map is not part of the standard library so I don't know the
specifics of that implementation. However it would be a poor
implementation of a hashmap is you could not perform insertions/
deletions in constant time (best case). I don't know about
invalidation of iterators but it's possible to make an implementation
where only iterators to the element removed are invalidated.
I would suspect that the interface of a hashmap is much the same as
that of map, with the exception that finding, inserting and deleting
elements are constant time operations, so finding an element and
getting an iterator to it in constant time should be possible.
--
Erik Wikstr=F6m