C9 Lectures: Stephan T. Lavavej - Standard Template Library (STL), 7 of n

Why does the MinMax function have that complexity?

FUNCTION: MinMax( seq, comparer_lessthan) --> pair(,)
_min = seq.begin
_max = seq.begin
for each element in seq
if comparer_lessthan(element, _min) then _min=element
if comparer_lessthan(_max,element) then _max=element
next
return new pair(_min,_max)

O(n)

or if the STL would let you do

FUNCTION: MinMax( seq, comparer_lessthan) --> pair(,)
_min = LB(seq.begin,seq.end)
_max = _min + UB(_min.begin, seq.end)
return new pair(_min,_max)

Best Case: O(log n)  ' both are the last element.

Worst Case: O(2 log n) ' first and last elements.

Average Case: 0( (2 log n) / 3)

If I've missed something in the algorithms implementation, could you point be to a source (as I would be interesting in look at it.) 

Because binary search only works on sorted ranges? 

Stephan, at 6:39 you write *it++ = elem. I wonder if this code is indeed well-defined for output iterators and opened a question on stack overflow. Could you comment on this issue? Thanks!

I made slight booboo in the algorithm I forgot to add the element you are looking for.

Can't get link to work, Timestamp 33m00

The section where you are on about the lower and upper bounds of a group of elements (equal to the value you're looking for) in a sorted sequence y.

Not the lowest and highest values.

FUNCTION: MinMax( seq, comparer_lessthan, value) --> pair(,)
_min = LB(seq.begin,seq.end,value)
_max = _min + UB(_min.begin, seq.end,value)
return new pair(_min,_max)

Ah! I see where the _min iterator would be affected, so let's say a copy is passed to UB.

Let see if I've got this right minmax_element returns the smallest and largest element from an underordered sequece? 

I found out hows it is implemented,

Just thank you, STL

Same here :)
 
Stephan, are you going to tell us everything about functors in a next episode?

@STL:

Good interesting stuff as always  

> Is there anything else that people want to see?

1. perhaps a how to and how not to write ex a base64 encoder/decoder that interacts with the stl streams 

2. (perhaps this is more of a question) when to use lambdas and when to use bind, bind2nd, mem_fn.

i've read that lambdas can replace these functions but when should you use functions like bind, bind2nd,mem_fn. instead of lambdas ?

3. Talk more about common mistakes / gotchas

4. How to optimize the usage of STL, ex making sure you use the right container/algorithm for the right job, etc..

5. How not to use the STL, guess this is the same as 3.

6. How to add new features / functionality to complement the STL.. ( connected with 1. )

How about that ?   

At least the need for manual loops has almost been completely eliminated .

int main (int argc, char *argv[])
{    
    unsigned int fact = 0;
    cout << endl << "What factorial do you want to calculate?  ";
    cin >> fact;    
    vector <unsigned int> vec(fact);
    iota (vec.begin(), vec.end(), 1);
    cout << endl;
    cout << "Factorial is: " << accumulate (vec.begin(), vec.end(), 1, multiplies<unsigned int>() );
    cout << endl;
    return 0;
}

I've been spraining my brain recently with how to implement Shear-sort, its absolutely cool,entertaining and fast.  Shell & Radix soort used to be my favs, but now its shearsort.  Have a look at it, you also may find it fairly entertaining.

@STL: I/O handle, Socket, file Processing in the STL(Standard Template Library)..

But I'd like to close and learn to the "vector, string" and Lambda expression for char* processing.

As well, furthermore , Stephan tries to emphasize that "C++(STL) is more effective and efficient than other languages." just my hope or wish..

Thank you for your lectures.

@STL: Template metaprogramming, as mentioned in the previous Video comments (you answered that it might be in part 8 )

@STL: Thanks for another great lecture.

> Is there anything else that people want to see?

Aside from what you've just mentioned, I'd like clarification on using r-value reference.  MSDN help doesn't really show how to use it effectively, just syntactically.

@STL:
"Is there anything else that people want to see?"
Wide character support, e.g. wstring, wofstream etc.
Locales

For general purpose, I believe the complexity of shearsort is something like O(n^{^1/2 (}log n)) or equivalent to: Im glad my tablet functionality comes in handy every once in a while

But I AM quite pleased to have heard you mention that your STL implements an IntroSort its pretty awesome since SGI's STL implementation has IntroSort as the default too.

This URL is awesome since you can customize, this is how I compare sorts haha, when their bad implementation doesn't bug out of course

http://home.westman.wave.ca/~rhenry/sort/duel.php?width=600&height=1000&alg1=ShearSort&alg2=IntroSort

I made it be around screen width(each 600 wide), both sorts using 1000 entries to sort, Comparing side-by-side my new fav Shearsort with the also impressive IntroSort. The bigger N, the better Shearsort can do, since its complexity stays way down,  and is excellently-parallel n-way per "shear".

Recursive lambdas don't actually look so bad:
std::function<int(int)> factorial = [&factorial](int n) -> int {      return n <= 1 ? 1 : n * factorial(n-1);};
std::cout << factorial(4);
They do not work with "auto" however... And you couldn't just slap this inside an algorithm as you need to define a variable, and if you're doing that anyway you may as well just be making a named functor for it.
Source: http://cottonvibes.blogspot.com/2010/07/c0x-autos-lambdas-and-lambda-recursion.html
 

I would've much rather seen the standard library draft text on the monitor rather than your wm7 advertisement.

Didn't even realize that it was a mistake nor did I realize that your right eye is blind.

...impatiently waiting for your next video! Keep up these awesome videos!

...impatiently waiting for your next video! Keep up these awesome videos!

Seconded!

@STL: Cool, that's great!

@STL: > Is there anything else that people want to see?How about making a simple yet extensible calculator using STLi think a lot the STL will come in handy.
What do you think about that suggestion ?
Keep the videos coming, please :)

Starting to feel the effects of withdrawal and it ain't pretty!

8 hours ago, Garp wrote

Starting to feel the effects of withdrawal and it ain't pretty!

 

Agreed, I need my STL fix now!

10 days later, still no video

8 hours ago, Deraynger wrote

10 days later, still no video

Oh well, the joy of anticipation...

11 hours ago, NotFredSafe wrote

*snip*

Oh well, the joy of anticipation...

Yes, except that the joy could be in anticipation for the 9th Video, after having watched the 8th video

Oh Stephan, where art thou?