1.11 Non-mutating Algorithm

Loading...

Do curso por University of California, Santa Cruz

C++ For C Programmers, Part B

83 classificações

University of California, Santa Cruz

C++ For C Programmers, Part B

83 classificações

This course is for experienced C programmers who want to program in C++. The examples and exercises require a basic understanding of algorithms and object-oriented software.

Na lição

STL and the game of Hex

This module looks at the architecture of the Standard Template Library. It is especially important to understand how iterators are used to access container to produce highly efficient generic algorithms. The module also includes the important new style of function object—the lambda expression.

1.8 STL: Overview of Containers10:30

1.9 Associative Containers11:35

1.10 STL: Algorithms Library6:31

1.11 Non-mutating Algorithm7:50

Conheça os instrutores

Ira Pohl
Professor
Computer Science

Non-mutating sequence algorithms.

They do not modify the contents of the class they work on.

Their typical operation is a searching operation for

a particular element and returning its position.

So you can imagine that you have a whole bunch of stuff, on your desk,

you could have a whole bunch of friends with their telephone numbers and

you want to search it to find a particular telephone number.

So that's what searching is going to mean,

typically a linear operation and here are some of the non-mutating algorithm.

You don't change any values but you need to find something.

And again if you look at the prototype, here's an iterator

range that's a very frequent part of a signature.

This tells you that it requires a very weak

iterater type, weakest in this case.

And then this is the value being searched for.

You're looking for a t in the range b to e.

That's going to be typically a linear time algorithm,

typically only needs to be done in one direction, so it's one pace algorithm, and

that's why something like input iterator is sufficient.

Here's a second signature for find, that's an overloaded version of find.

And notice in the overloaded version of find.

Okay, for those of you who were wondering about syntax,

there's an extra parenthesis here.

In the overloaded version of find, Instead of a value, we look for a predicate.

Recall what a predicate is.

Predicate is something that leads to true or false.

So let's say in our pile of stuff we want to

find the first value that's greater than a thousand.

That's a predicate, we are not looking for a thousand.

We are looking for the first value that is greater than a thousand.

So that means that somehow we can put it in here

something that a logician would call a front door.

It's a functor that yields true or false.

And we are going to see how to do that as well.

So that vastly increases the power.

You could actually, but this is so common that you would want to have,

this could be arranged to be a predicate, right?

Or you have the predicate would be a value matching T.

So it's a subcase, so this is way more general and more powerful.

But this is standard, so you might as well have it specialized.

We're going to see this kind of signature a lot in STL, where we're allowed to,

instead of just a value, we're allowed to use a function.

A function will vastly increase, remember orthogonality.

And the design of the library, it let's us use the library in many

more instances than the simple idea of just testing for a value.

Here's another non-mutating algorithm.

Again, it uses the idea of a function.

We're going to see this in use in an example shortly.

Again, there's an iterator range.

Again, for some reason, I have an extra paren.

And here's a function, and

we want to apply the function to every element found in range.

Let's say we want the function to do output, so

every element in this range of a for each would be outputted.

And this function lets us sort of basically do anything.

And for each you can see is a very, very powerful,

in effect it's a control structure.

Now, here's our example.

We have a string, we have words,

we have an initialization of the words to my,

hop, mop, hope and cope.

So word sub zero is my, right?

This is the sub 01, and this is the sub 41.

Here we have the equivalent of an iterator.

It's a pointer.

So, this is what we get back from find.

We get back the position that finds the position.

And we're looking for, this is your begin and your and.

We're looking for the position of hop.

Now a hop is sitting there.

And then we're auto incrementing it, we're moving one past where we would be and

that means we jump over here and we get mop.

Here's a sort.

So now we're going to sort.

Again, this is quick sort, we sort the whole range.

We could sort a sub range as well,

shows you how using iterator ranges is quite powerful.

So we could have a whole big sequence and only sort a sub-sequence.

In this case, we're sorting from the beginning to the end of the array.

And we're using lexigraphic sort, so cope is going to is end up first, right?

Cope is going to end up first.

If I'm getting my dictionary order right,

I think my is going to end up last.

And then what's in the middle?

We have cope, hop, hope, mop, my.

So hop is second, and then hope is third.

And then mop and

finally my.

So what comes after hop after sorting is hope.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play