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.

Loading...

來自 University of California, Santa Cruz 的課程

C++ For C Programmers, Part B

74 個評分

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.

從本節課中

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.

- Ira PohlProfessor

Computer Science

Finally, let's talk about the strongest of iterator classes.

And here, you want to think of an indexed array,

that's where you typically are seeing something that's random access.

We call it an indexed array.

If I have an indexed array of elements,

And say it had 37,000 elements, at any time,

I can get to any of these elements through a simple address calculation.

It's just how many ever bytes is needed for store.

Typically, that would be four bytes times the index.

So 4 x i whatever the index is,

gets me whatever the base pointer value is.

Base pointer + 4 x i, and

that gives me in bytes where I am.

And that's a simple calculation, that's a fixed time calculation.

So that means that I can do general address arithmetic.

So in order to be able to do things equivalent to the indexed array,

which I can do for vector or the special class array or

the special container class double ended queue.

I have to be able to do this calculation, and that requires random access.

A canonical random access iterator,

the one we have to have this behavior for, is a sort algorithm.

And again, we've used it already.

The sort algorithm that's found in STL is based on Hoare's Quicksort.

It's extremely fast, you should test it out.

Try it against your own handcoded version of Quicksort.

Remember Quicksort is also called partition exchange sort, so in Quicksort,

just to recall what you're doing, here might be a bunch of values,

sitting in a container, integer values in this case.

Quicksort, you would take one value, let's say you take the 3,

and you use it for your partition.

And after partitioning the set you are going to end,

what's less than 3 and what's greater or equal to 3, let's say.

So here is that element 3.

And we might say 2- 6- 2,

3 is on one side.

And on the other side is 6, 9 and 15.

So we know that this is in its right position and these two are now unordered.

And then we would recursively call and

effect partition these two sets recursively.

So partition exchange means that 6 got moved over there.

That's the exchange part.

9 got moved over there, -6 got moved over here.

And it's the exchange part, the exchange part that requires random access.

Here's a very simple random access element.

This is selecting at random from something in a range.

So we have normal range, first and last.

We compute a random number, which is an integer, we.

Modulo it by temp, and temp gives us last-first,

it gives us a range of values.

So if there's 100 values being stored there, temp's going to end up 100.

Rand is going to give us a number between 0 and 99 and

then we'll add that on to first.

And notice, we need general point arithmetic.

And that's a hallmark of a random access iterator.

So this is a scheme for picking an element at random.

Ptrdiff_t as a type or ready to find type, it's in the cstddef library.

It's basically an integer value which is the result of

an operation where you are given two pointers,

and you're allowing subtraction to get you an integer value for that pointer.

Remember, pointers need to know the underlying size

of it's not merely an int, it's not like one, two or three.

If you have two long doubles, they might be eight bytes so a pointer

diff between two long doubles might be intrinsically of a difference of eight.

So ptrdiff lets us factor in the size of the type.

And here would be a simple way to print a random element inside that range,

beginning to end, that's how we could use it.

Okay, so that's it for today.

Next time I'm going to go further into STL, give you more of STL,

more insight into how it's designed to be efficient and orthogonal and

I'm also going to give you some newer parts of STL

that are based on the C++ 11 standard.

Okay, see you then.