Re: Constant time search in list.
On Feb 21, 10:23 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 integers=
(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: meaning=
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 howev=
er if
its possible to do it in constant time, and use list the the same time=
.. I
read something about using lookup function on a hash, but I don't want=
to go
away from using a list.
Arranging the elements of the list is not important to me, hence a Se=
t is
not exactly what I am looking for.
You can use a hash in addition to the list; package both in some wrapper
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 you
are using. Also, it won't buy you constant time, but logarithmic time,
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).
As of now, I am using the following:
Class A{
//;
Vector<List<Class B> > tree;
//;;
};
If class B is not an STL pair, but each object can still be uniquely
identified by 2 integers, then I don't think that changes much ?
Sorry, but I can't see the reason to use such a construct, what is the
vector good for if you store the pair in the list? Do you use the
first integer to index into the vector and then store the pair in the
list? If you do you only have to store the second integer in the list,
since the first was used to index.
--
Erik Wikstr=F6m