Menu
I happen to run into the source of std::find and find it confusing to me. Basically it divides the count of items by 4 and do the compare 4 in each round:
template<typename _RandomAccessIterator, typename _Tp>
_RandomAccessIterator
__find(_RandomAccessIterator __first, _RandomAccessIterator __last,
const _Tp& __val, random_access_iterator_tag)
{
typename iterator_traits<_RandomAccessIterator>::difference_type
__trip_count = (__last - __first) >> 2;
for (; __trip_count > 0; --__trip_count)
{
if (*__first == __val)
return __first;
++__first;
if (*__first == __val)
return __first;
++__first;
if (*__first == __val)
return __first;
++__first;
if (*__first == __val)
return __first;
++__first;
}
switch (__last - __first)
{
case 3:
if (*__first == __val)
return __first;
++__first;
case 2:
if (*__first == __val)
return __first;
++__first;
case 1:
if (*__first == __val)
return __first;
++__first;
case 0:
default:
return __last;
}
}
I have no idea why it's done this way. Looks like some optimization. But I don't think this will take advantage of multi-core that easy. This is in a single thread anyway.
Any ideas?
704
The algorithm to use is std::binary_search , that directly returns a bool representing whether the searched value has equivalent elements in the collection.
It's implemented by using an underlying array. It's not possible to implement a std::vector<T> with a linked list because the standard guarantees the elements in the list will be held in contiguous memory. Also, lookup time is important.
std::find on average runs in O(n/2) time whereas std::count is O(n) always.
But std::find is not really made for sorted collections because it uses equality and not equivalence, and it operates in linear time and not logarithmic time.
Today we are going to talk about C++ basic std::pair class in a way how and why it is broken. std::pair first appeared in C++98 as a pretty basic class with a very simple semantics — you have two types T1 and T2, you can write std::pair<T1, T2> and access .first and .second members with all intuitive copy, assignment, comparison operators, etc.
This is a minor and debatable thing but std::pair with trivial and non default zero initialized scalars is zero initialized: In contrast, std::array does not initialize their elements with the default construction (if the underlying type is trivial) and leaves this for the user.
Looks like loop unwinding, also known as loop unrolling.
99
It's loop unrolling. The result is the same, but it's friendlier for the processor.
The asymptotic complexity is the same though.
28
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
