Constant time search in list.

[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 however 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 Set is
not exactly what I am looking for.

Thanks,
Amit.

 

[Alf P. Steinbach]

* 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 however 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 Set 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.

 

[Amit Bhatia]

* Amit Bhatia:

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)?

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 ?

Thanks,
Amit.

 

[=?iso-8859-1?q?Erik_Wikstr=F6m?=]

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.

 

[Amit Bhatia]

* Amit Bhatia:

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.

I am using a vector since I am organizing objects of class B according to
certain criteria in different lists. So the index of the vector has nothing
to do with the pair of integers that uniquely identify objects of class B.


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 constant
time? does the hash_map also has the ability to return iterator in case one
instance of the object is found (in constant time)?

Thanks,
Amit.

 

[=?iso-8859-1?q?Erik_Wikstr=F6m?=]

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 constant
time? does the hash_map also has the ability to return iterator in case one
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.

 

[peter koch]

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 constant
time?

Remember that insert/delete of a hashed container is only O(1) in the
normal case. worst case is O(n).
For the other questions, you should refer to your compilers
documentation since hashed containers are only now being accepted into
the standard. I would recommend that you upgrade the compiler as g++
should now have implemented the hash-containers that will be the part
of the next standard. As soon as you ask question about standard
containers, you are much better of in this newsgroup.

/Peter