vector issue

[TheIdeasMan]

I am using the vector container for a binary searches.

If sorting and searching are a priority, then I would recommend a different container - one that is already sorted, or items are sorted upon insertion. std::set is almost the same as a sorted vector with a binary search in terms of a find operation, except that the set is sorted upon insertion - it is usually implemented as a Binary Sort Tree (BST). So the cost of sorting the vector is avoided if std::set is used.

But it would be a good idea to compare some containers, and see how you get along. For example compare the time taken to std::find using std::clock with std::unordered_set , std::set , and the sorted vector with std::sort.

[jlb]

std::set is almost the same as a sorted vector

The std::set has a couple of items that could be problematic. First std::set isn't random access and it doesn't allow duplicate key values. Also remember that elements of a set are const.

So the cost of sorting the vector is avoided if std::set is used.

Inserting a large number of elements in a set can be much slower than inserting elements into a vector and then sorting the vector.

However since a set is much faster searching for the key, if the set remains fairly constant and you're doing a lot of searching, the set may be the better choice.

[doug4]

I'm not sure the OP would get much better improvement on searches with a set vs. an ordered vector. It sounds like he is already doing a O(log(n)) search.

I am using the vector container for a binary searches. I get around 20 recursive passes to find a number in an ordered vector of a million elements.

I assume this means that he is not using the the provided find() function, but instead is starting in the middle and playing the high/low game (depending on the fact that the array is sorted). That is essentially the same search algorithm that is used in a binary tree.

[TheIdeasMan]

doug4 wrote:

I'm not sure the OP would get much better improvement on searches with a set vs. an ordered vector. It sounds like he is already doing a O(log(n)) search.

That's what I was was thinking when I said "std::set is almost the same as a sorted vector with a binary search in terms of a find operation", but as jlb pointed out inserting into the set would be slower in the first place as opposed to sorting a vector. Also, it might depend on whether the set's tree became unbalanced, and what cost of re-balancing?

I am trying to write some code to test unordered_set, but for some reason it is creating more buckets than elements !! Will start new topic on that.

[TheIdeasMan]

@technologist

Check out these two results htiwirn and JLBorges:

http://www.cplusplus.com/forum/general/193311/#msg930363

Note that one can use the binary_search algorithm on sorted containers:+)