Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Best way of doing it.

Posted on 1999-07-21
15
Medium Priority
?
193 Views
Last Modified: 2010-04-02
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
Comment
Question by:sector
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 3
  • 3
  • +3
15 Comments
 
LVL 3

Expert Comment

by:Iexpert
ID: 1200694
hashtable since all 250 numbers not present and
gives fast access
0
 
LVL 22

Accepted Solution

by:
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

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

0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 

Author Comment

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

Expert Comment

by:nietod
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

by:jasonclarke
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

by:nietod
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

by:jasonclarke
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

by:KangaRoo
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

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

Expert Comment

by:jasonclarke
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

by:KangaRoo
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

by:jasonclarke
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

by:jasonclarke
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

by:Astroman
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

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

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…
What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
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 member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

688 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question