Solved

# Best way of doing it.

Posted on 1999-07-21
Medium Priority
199 Views
If i have a list of integers that are not sequenced but arranged from the smaller number to the biggest one ( up to 250 number ) and i want to find a number to see if it is in the list.
What is the better container to use here ( vecotr ,array , hashtable , map etc.. ) and why ?
0
Question by:sector
• 5
• 3
• 3
• +3

LVL 3

Expert Comment

ID: 1200694
hashtable since all 250 numbers not present and
gives fast access
0

LVL 22

Accepted Solution

nietod earned 100 total points
ID: 1200695
A hashtable would be best if you don't need to iterate the elements in a sorted order.  However STL does not include a hast table, so that isn't even an option unless you want to write one.  The best option if you want to use STL is the set<> container.   it stores the elements in sorted order and allows them to be iterated in that order.  It is like the map<> container but does not associate a value with the sort key, the sort key itself (your numbers) are the only value stored.  There are no other STL containers that are even slightly appropriate.  For example the vector container you mention, does not sort the data, thus you would have to do so and this is very inneficient, vector isn't designed in a way to make sorting efficient.

Let me know if you have any questions.
0

Author Comment

ID: 1200696
Why is a hashtable faster than just putting the numbers into an array like this :
int[] local = { 1,250,450,22 };

0

Author Comment

ID: 1200697
but i get the data already sorted.
Does that change the picture ?
0

LVL 22

Expert Comment

ID: 1200698
>> Why is a hashtable faster than just putting
>> the numbers into an array like this
When hashtables perform well, they are extremely fast at finding data.  Often much faster than a binary search.  In many cases, the data can be found in a single operation.  However, if you also need to access the data sequentualy, that is nearly impossible to do with a hash table, in that case a set would be better.   If you just need to search the data a hashtable is probably the best option, except there is not one included in STL, you would have to write it yourself.

>> i get the data already sorted.
>> Does that change the picture ?
Not really.   vector<> cannot be searched quickly.  (If the data is sorted, it would be possible to write a binary search for a vector<>, but there is no built in search for this, so you have to write your own or use the standard linear search, which is slow.)  The same is true of the list<> container.  Only map<> and set<> can be searched quickly and map<> needs that "extra value" so set<> is the right choice.
0

LVL 9

Expert Comment

ID: 1200699
there is a binary_search algorithm in the STL, which can be used with the standard vector as long as it is sorted.  Access to the vector is fast, it has random access iterators, so it can use the indexing operator in O(1) time.

The following code works fine:

#include <algorithm>
#include <vector>

using namespace std;

void main()
{
vector<int> vi;
vi.push_back(7);
vi.push_back(4);
vi.push_back(5);
vi.push_back(9);
vi.push_back(2);
std::stable_sort(vi.begin(), vi.end());

bool found = std::binary_search(vi.begin(), vi.end(), 5);
}
0

LVL 22

Expert Comment

ID: 1200700
I didn't realize that STL has a binary search (of sorts--its not guaranteed to be binary).  However that still is more work than the set container.
0

LVL 9

Expert Comment

ID: 1200701
A set is better as long as the data contains no duplicates (or it doesn't matter if the duplicates are removed), but you can use a multiset if that is not the case.

The binary_search will be binary on a sorted vector since random access iterators are used.
0

LVL 7

Expert Comment

ID: 1200702
It uses forward iterators:

template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value);

template<class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

0

LVL 7

Expert Comment

ID: 1200703
Although the code shows that lower_bound() is used, which has a random access iterator version....
0

LVL 9

Expert Comment

ID: 1200704
The docs I have say that binary_search performs in O(logn) time if you have random access iterators and O(n) otherwise.  As you say, the algorithm can make use of the fact that there are random access iterators.
0

LVL 7

Expert Comment

ID: 1200705
My docs only say it uses at most log(n) + 2 *comparisions* Seems there are some differences?
SGI docs also say log(n) + 2 compares, a logaritmic number of steps for random access iterators and lineair number of steps otherwise.
Anyway, with integers that would qualify for a O(N) time when using non-random access iterators.

SGI docs also metion the existence of a 'Hash Associative Container'
0

LVL 9

Expert Comment

ID: 1200706
I think you are correct in what you say about excecution times, what I said was a simplification.

The dinkumware version of STL (which is what you get with VC++, although I don't think the version with the compiler is up to date) also contains hash implementations of sets and maps.
0

LVL 9

Expert Comment

ID: 1200707
The trouble with hash table versions is of course that you have to define a suitable hashing algorithm that will ensure that items in the table are evenly distributed, which usually requires knowledge of the number of hash buckets in the table etc.

A bad hashing algorithm can make the hash table very inefficient.

The worst hashing algorithm I have seen is:

return 1;

:)
0

LVL 1

Expert Comment

ID: 1200708
SGI do have hash_[multi]map and hash_[multi]set containers, but these are not defined in the C++ standard. They're included with the GNU C++ compiler libs, and I guess you can get them from SGI and integrate them for use with any compiler you fancy.

For what you want, the hash_set would be the best choice, offering faster access than a plain set.

As for the hashing algorithm, it is possible to override the default one if your needs be. Look at
http://www.sgi.com/Technology/STL/HashFunction.html
to see what SGi say about the whole thing. Go to the index of that directory for loads of good STL resources.

Leon

0

## Featured Post

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
###### Suggested Courses
Course of the Month13 days, 15 hours left to enroll