Hi,
Let's say I have an array. Every time I want to input an element, I want to make sure there is no duplicate entry in the array/list.
I think the simplest method is doing a linear search against the array everytime I input the value. However, if the list grows longer, this method will not be efficient.
How to avoid duplicate entry to a list/array in an effective manner?
If you keep the array sorted, you can really cut down on the time it takes to search the array.
On the plus side, stdlib.h contains both qsort() and bsearch() to make this pretty easy.
Or you could implement a hash function.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
to implement hash table, if i m not mistaken, it will allows quick matching to data.
However, when inserting a new entry, the hash value of the new entry has to be calculated. If the collision occurs, the insertion will takes quite sometime, correct?
Yes u are right, So to avoid collision too many time, there are many way to find the key value which will end up in good hashing function which reduces clusters. For your Reference
ssharish2005
Last edited by ssharish2005; 12-16-2006 at 02:36 PM.
You want a "set", which is an associative container. there are two implementations for associative containers.Originally Posted by janetsmith
One is the self-balancing binary search tree, which is sorted and gives a O(log n) to most operations; requires you to be able to compare elements. This is implemented with the "set" class in C++.
The other is a hash table, which is not sorted and gives an average O(1) and worst-cast O(n) to most operations; requires you to have a hash function for the type. This is implemented with the "hash_set" class in C++.
thanks, i will take a look on it
