- 2 days ago
The C++ Standard Library provides provides classes and functions which can be used in a program. Stream I/O, strings, and STL are explained. https://www.softprayog.in/programming/cpp-standard-library1-streamio-strings-stl
Category
🤖
TechTranscript
00:00:00The C++ standard library comprises of Stream.io, Strings, the Standard Template Library or
00:00:09the STL, Threads and Utilities.
00:00:13Of these, we will examine the first three i.e. Stream.io, Strings and the STL in this video.
00:00:23The next video would cover Threads and Utilities.
00:00:26So, let's get started with these topics for the C++ standard library.
00:00:33How to use the standard library?
00:00:36The standard library is available under the std namespace.
00:00:41So to access a class or an object from the standard library, we need to use the scope resolution
00:00:48prefix std double colon like std double colon cout or std double colon stream.
00:00:56The next thing is to include the relevant standard library header files in the program.
00:01:02The header files are like iostream for standard input, output and error streams.
00:01:08iostream is easily the most commonly used header file.
00:01:14String for using the std string class.
00:01:17Vector for the std vector container.
00:01:19Similarly map for the std map container.
00:01:23Unordered map for std unordered map container.
00:01:27And algorithm for using the std algorithms like std copy, std find, std sort etc.
00:01:36There are many new header files and we will find them as we see the example programs.
00:01:41The standard library provides streams for IEO.
00:01:46A stream is like a pipeline in which data flows.
00:01:51A program writes to a stream and the data might end up on the video display or a file or
00:01:58network.
00:02:00Similarly a program reads a stream and the data might be coming from the keyboard or a
00:02:06file or the network.
00:02:08The data flowing in the stream can be of characters or it can be binary data.
00:02:15Let's look at the two cases separately.
00:02:18And first the character based stream IEO and characters here follow a format.
00:02:25It's like we have a format character string followed by an integer and the double precision
00:02:31floating point number.
00:02:33Now we say integer, double etc.
00:02:36But these are characters not the binary representation.
00:02:41Say an integer like 123 which we write as characters 1, 2 and 3.
00:02:47So kind of we had an integer like int i which had a value 123 and we printed as character
00:02:541,
00:02:552, 3 or we read it as characters 1, 2 and 3.
00:02:593.
00:03:014.
00:03:02StdOS stream.
00:03:02StdOS stream is a class for output streams.
00:03:05And there are two important global objects of this class.
00:03:09And these are stdCout for standard output which by default is connected to the video monitor
00:03:16screen.
00:03:28In Linux environments these streams correspond to file descriptors 1 and 2.
00:03:37Then we have the put2 operator which writes the second argument on the first.
00:03:42So if we say stdCout less than less than hello world it writes hello world on the standard
00:03:51output stream and you can see it on the video monitor screen.
00:03:56Similarly you can write stdCout less than less than i or stdCout less than less than d or stdCout less
00:04:07than less than c and all these values appear on the screen.
00:04:11Now put2 operator is left associative.
00:04:15So if you write stdCout less than less than a less than less than b it is first stdCout less
00:04:24than less than a and the result less than less than b.
00:04:28The expression in parenthesis evaluates to stdCout while the value of a is written on the standard output and then
00:04:38we have stdCout less than less than b.
00:04:42So in effect we get the values of a and b written on the screen.
00:04:47It is not necessary to write two statements you can simply put them together as stdCout less than less than
00:04:55less than a less than less than b.
00:04:57So we can replace the last three statements in the above program with a single statement like this and the
00:05:05values of i, d and c are printed.
00:05:08For the input we have the stdI stream class and it has global object stdCin which reads data from the
00:05:19standard input which by default is the keyboard.
00:05:23Here is an example stdCin greater than greater than i.
00:05:29We have this greater than greater than operator which is the get from operator and it gets input from the
00:05:37object cin.
00:05:38It gets the input from the first argument to the second argument which is the integer variable i here.
00:05:45Here is an example stdCin greater than greater than i.
00:05:52This reads the character from the standard input to integer variable i and next we read stdCin greater than greater
00:06:02than str and we print the values we have read.
00:06:06We compile and run this program.
00:06:08We have an integer 23 and the string we type is hello world.
00:06:15We print the values the integer is 23 that's correct but the string only has one word hello.
00:06:22The rest of the string is missing.
00:06:24We type the string as hello space world.
00:06:28Now space is a delimiter and the system thinks that the string is just hello because there is a delimiter
00:06:36between hello and world.
00:06:38We can correct this by using the get line function which reads a line that is correct us up to
00:06:45the new line.
00:06:47So we say get line stdCin comma str which should read a line from the stdCin into the string str
00:06:57and we command the earlier stdCin greater than greater than str and we compile and run.
00:07:05Now there is another problem.
00:07:07I type in integer 23 and the program runs through.
00:07:11We don't get a chance to type in the string.
00:07:15The problem is that when I type 23 I also press enter and integer i becomes 23 and there is
00:07:23a new line character in the buffer which comes to the get line function.
00:07:28Get line sees the new line thinks that it has got a string and immediately returns.
00:07:36So there is no string nor a chance to enter one.
00:07:40This is not what we wanted.
00:07:42So what we should do.
00:07:44We need to skip the delimiter character new line after rating the integer i.
00:07:50So we say stdCin dot ignore 1000 comma new line character.
00:07:57This function discards characters till either 1000 characters are discarded or end of file is reached or the delimiter character
00:08:07which is new line here is found and discarded.
00:08:11With this we discard the new line before the get line function and now the program works fine.
00:08:18In the previous examples we have used put to and get from operators for built in types like int and
00:08:27also strings.
00:08:29But we can use these operators for user defined types also.
00:08:33So suppose we have a user defined type struct student int role number std string name and we are going
00:08:43to use the put to and get from operators with standard output and input like this.
00:08:50Int main student s while std cin greater than greater than s std co less than less than s less
00:09:03than less than std endl.
00:09:06That is read a student from standard input and write a student on standard output.
00:09:13And our format for student is like this open brace row number comma student name in quotes closing brace.
00:09:23And these are the operator overload functions for put to and get from operators.
00:09:29For these operators we need a stream and a student structure.
00:09:34So there are references to these in the input parameters.
00:09:38Most important is that these overload functions return a reference to the relevant stream.
00:09:46This is how chaining becomes possible.
00:09:49Because a reference to a stream is returned which is used for the next argument if any.
00:09:57The output operator overload function simply writes the two data elements row number and the name on the stream.
00:10:04And enclosing the output embraces and putting a comma in between.
00:10:10The input operator overload function is somewhat involved.
00:10:14Because we need to do validation of input whether it is as per the format or not.
00:10:21If validation fails, std ios base fail bit is set and the stream returns in a failed state.
00:10:29And the main function loop terminates.
00:10:33Binary stream IO is important.
00:10:36In fact, very important because there are lots of times you create or modify binary files.
00:10:44These files are mostly for use by the computers.
00:10:47For example, a binary data file recording student data.
00:10:53Image files like png, jpeg, document files like pdf, etc.
00:10:59So let's look at binary file IO in C++.
00:11:03And here we need to use the fstream header file for library classes for file handling.
00:11:11There are three core filestream classes.
00:11:15Ifstream for input filestream.
00:11:18This is for input operations and is for reading data from files.
00:11:23Ofstream for output filestream.
00:11:26This is for output operations that is for creating and writing data to files.
00:11:32And then there is fstream that is filestream.
00:11:36This is for input output operations.
00:11:39You can create, read and write data to files.
00:11:43Here is an example program to copy a source file to destination.
00:11:49We include the header files IO stream, fstream and string.
00:11:55Here we will copy source file to destination.
00:11:58So we need the source and destination filenames.
00:12:02We get the source and destination filenames from the standard input stream CIN with string variables
00:12:10source and dest.
00:12:13Next we open the two streams.
00:12:15The first input stream, ifstream, is is for the input stream and os for the output stream.
00:12:22The flag stdios binary specifies that it is a binary stream.
00:12:30Data would be written or read exactly as it is with absolutely no translations like lf to crlf.
00:12:39If both is and os are valid streams, then let's look at the important line os less than less than
00:12:48is rd buff.
00:12:50Each stream is associated with a stream buffer.
00:12:53The data in a stream flows through a buffer.
00:12:56It is like file to stream buffer to the program.
00:13:00A stream buffer is a low level implementation detail.
00:13:04Is rd buff gives the pointer to the stream buffer.
00:13:08The put to operator transfers the data to the os stream.
00:13:12A string is a sequence of characters.
00:13:16For example, hello world is a string.
00:13:19In C programming, a string is implemented as an array of characters terminated with a null character.
00:13:28So that you know where the string is terminated.
00:13:31As all C programs are also C++ programs, the C style strings are available in C++ also.
00:13:41But in C style strings, you need to worry about the memory, whether you are overshooting the space available and
00:13:48also whether the terminating null character is in place or not.
00:13:53The good news is that the standard library in C++ provides strings where you need not worry about the memory
00:14:03management for strings or whether there is a null character there or not.
00:14:09In C++ strings, all this is taken care of automatically.
00:14:14You need to include the string header file to use C++ strings.
00:14:20For example, here we have the string abcd1234 which we can print on the standard output.
00:14:29A string of std string class can grow or shrink during the runtime.
00:14:35The underlying memory management for creation of a string and increase in its size at runtime is automatic.
00:14:43operators.
00:14:45The subscript operator which is the square brackets gives the character at that index.
00:14:52We can treat the string as a character array.
00:14:56A string starts at 0 index and the last character is at string length minus 1.
00:15:03Equal to is the assignment operator for assigning a string value to a string object.
00:15:09Plus is for concatenation of two strings.
00:15:12Plus equal to is add to string or append string at the end.
00:15:18Here is an example of operators for strings.
00:15:22First we create three string objects str, str1 and str2 with initialization and then we have
00:15:31cstyle string comma which contains a comma and a space.
00:15:36So str has value high to start with.
00:15:39str is assigned str1.
00:15:42So str is now hello.
00:15:45We append comma to it and it becomes hello comma space.
00:15:49So we can use c++ std string along with cstyle strings in expressions and then we append str2 to str.
00:16:02It becomes hello world and finally we append exclamation mark to str and it is the final string hello comma
00:16:11space world exclamation mark.
00:16:15If there are string literals adjacent to one another these are concatenated into a single string by the compiler.
00:16:25For example if we have three string literals hello comma and world the compiler makes it a single string hello
00:16:33world and here in this case it is printed.
00:16:37Since std string is a class it has got member functions and we look at some of them.
00:16:45The length function gives the length of the string.
00:16:48For example std string str initialized to shanks pony and we can print its length which is std cout less
00:16:59than less than str dot length less than less than std endl.
00:17:05And this prints 12.
00:17:07Now accessing the individual characters of the string we can treat the string as an array.
00:17:13Suppose we have a string std string str initialized to silver bullet and then char a equal to str 0
00:17:23char b equal to str str dot length minus 1.
00:17:28And if we say std cout less than less than less than a less than less than less than comma
00:17:34space less than less than less than b less than less than std endl.
00:17:39And this prints the first and the last characters of the string which are s and t.
00:17:45The substring function substr returns a copy of the substring inside the given string.
00:17:54The parameters are the index of the start of substring and the length of the substring.
00:17:59For example we have the string str initialized to good, bad and ugly.
00:18:06So substring at 63 that is start index is 6 and length is 3 is bad.
00:18:14And with the replace function we can replace substring.
00:18:17Suppose you want to replace substring bad and str with excellent.
00:18:22We can say str dot replace 6 3 excellent.
00:18:28So 3 character substring bad are replaced with excellent.
00:18:33And replacement is in situ.
00:18:35That is replacement string can be smaller, equal to or larger than the original substring.
00:18:42The relational operators are equal to, not equal to, greater than, less than, greater than equal to and less than
00:18:53equal to.
00:18:54And these relational operators can be used in expressions involving strings.
00:19:01For example std string s1 initialized to effect and std string s2 initialized to effect.
00:19:11So the expression s1 greater than s2 evaluates to false and the expression s2 greater than s1 evaluates to true.
00:19:20And if we have expression s2 equal to effect, which indeed it is, the result is true.
00:19:30The standard template library stl was developed separately in the 1980s.
00:19:38It was the work of many people, most notably Alexander Stipanov, David Musser and Wang Li.
00:19:47The work of STL was considered highly and in the 1990s efforts were put in to include it in the
00:19:56C++ standard.
00:19:58Consequently the STL became a part of C++ in the C++ 98 standard.
00:20:06The classes of STL are available under the STD namespace.
00:20:11The important part of STL is its unified design and the parts of STL work in a similar way and
00:20:19they work well together.
00:20:21There are three major concepts in STL and these are containers, iterators and algorithms.
00:20:29Together these three are called the STL triad.
00:20:34Containers provide storage for elements.
00:20:37Algorithms provide the logic for getting the work done using the elements in the containers.
00:20:44Iterators provide the algorithms a standardized interface to the elements of the containers.
00:20:50And the main thing is that they all work together.
00:20:53We will look at containers, algorithms and iterators in this video.
00:21:00A container is a class template.
00:21:02Its main objective is to hold objects of a type.
00:21:07The objects are called the elements of the container.
00:21:10A container manages memory for its elements and provides interface to access, add, modify, remove and iterate over the elements.
00:21:21The standard template library provides a host of containers.
00:21:26So we can use them straight away in our programs as they are highly optimized.
00:21:32And some of the important containers provided by the STL are
00:21:36Vector t, it's a variable size vector.
00:21:40List t, a doubly linked list.
00:21:43Forward list t, a singly linked list.
00:21:46Deck t, a double ended queue.
00:21:50Set t, a collection of unique keys ordered by their values.
00:21:55Multi set t, a set allowing duplicate keys.
00:22:00Map kv, an associative array mapping a key into value.
00:22:06So it has two type parameters, k for key and v for value.
00:22:11Multi map kv, similar to map but allowing duplicate keys.
00:22:17Unordered map kv, it's a map using a hashed lookup table.
00:22:22Unordered multi map kv, a multi map using a hashed lookup table.
00:22:28Unordered set t, a set using a hashed lookup table.
00:22:37Of these, we'll look at vector, list, map and unordered map containers in a little detail.
00:22:49Vector is a container class template.
00:22:52It contains objects of a type.
00:22:55These objects are the elements of the vector.
00:22:59A vector is like an array.
00:23:01Its elements occupy contiguous successive memory locations.
00:23:07We can do random access of elements using the subscript starting with 0.
00:23:13And the last element has the subscript vector size minus 1.
00:23:18The number of elements in a vector is its size.
00:23:22The number of elements can increase or decrease at run time.
00:23:28So a vector appears like a dynamic array.
00:23:31Its size can increase or decrease at run time.
00:23:36And this is how it looks like.
00:23:38Elements and sc are kind of private data members.
00:23:42The vector appears like a dynamic array with subscript operator and also member functions.
00:23:49Here is an example program for vector.
00:23:53Student is a struct having role number and name.
00:23:57And these are the operator overload functions for put to, output operator and also get from input operator.
00:24:05In the main function we have the vector student register.
00:24:10Which is a vector of a student.
00:24:13And this vector has three student elements.
00:24:15John Doe, Joe Blocks and Fred Nerk.
00:24:19We have the print register function.
00:24:21Where we pass a reference to the student register vector.
00:24:25And print register function iterates over the elements of the vector.
00:24:31And prints each student.
00:24:33We can compile and run this program.
00:24:37And it works fine.
00:24:40And now the member functions.
00:24:42The size function gives the number of elements in the vector.
00:24:46In the previous vector example.
00:24:49We can print the size of student register vector.
00:24:53And it prints three.
00:24:55The pushback member function adds an element at the end of the vector.
00:25:00And the size of vector increases by one.
00:25:04For example.
00:25:05We can say.
00:25:06Student register dot.
00:25:09Pushback.
00:25:09One, two, three, five, nine.
00:25:12John Smith.
00:25:13And John Smith is added to the student register vector at the end.
00:25:18And its size becomes four.
00:25:21The pushback function illustrates the expandability of the vector at runtime.
00:25:26The capacity of a vector is the number of elements it can hold in the currently allocated buffer.
00:25:35So essentially size is less than or equal to capacity for a vector.
00:25:41We can print the capacity of vector with the capacity member function.
00:25:45Like here.
00:25:47We first print the size and the capacity.
00:25:50It prints the size of student register vector as four.
00:25:55Whereas the capacity of student register is six.
00:25:59So if we add two elements to the vector.
00:26:01The size and capacity both become six.
00:26:04And what happens when we try to add the seventh element.
00:26:08We can try that.
00:26:10And when we add the seventh element.
00:26:12The vector size becomes seven.
00:26:14And its capacity becomes twelve.
00:26:18The capacity is implementation dependent.
00:26:21All we are interested here is.
00:26:23When the size and capacity become equal.
00:26:26And we add an element.
00:26:28The capacity increases.
00:26:29When the size of a vector is equal to its capacity.
00:26:33And a new element is to be added.
00:26:36A new buffer for the vector is allocated dynamically.
00:26:40The existing elements of the vector are copied or moved.
00:26:44If possible to the newly acquired buffer.
00:26:47And it becomes the memory buffer for the vector.
00:26:50The old buffer is deleted.
00:26:53And all this is done automatically under the hood.
00:26:56And to the user.
00:26:57The vector appears to be growing.
00:26:59As new elements are added.
00:27:01Most of the time.
00:27:03We have some idea.
00:27:04About the size of the vector.
00:27:06So we make a sort of.
00:27:08Guestimate.
00:27:09And say.
00:27:10We might need.
00:27:11That many elements.
00:27:13At runtime.
00:27:14And we can avoid the overhead.
00:27:16Of repeated.
00:27:17Dynamic memory allocations.
00:27:19As a vector grows.
00:27:21We can reserve.
00:27:22Memory for that many elements.
00:27:24Right up front.
00:27:26For example.
00:27:27We might think.
00:27:28That the student register.
00:27:30Might have a.
00:27:31Maximum.
00:27:32Of.
00:27:33Hundred students.
00:27:34So we.
00:27:35Reserve space.
00:27:36For hundred elements.
00:27:37Right at the beginning.
00:27:39And we can.
00:27:39Keep on adding.
00:27:40Elements.
00:27:41To the student register.
00:27:42Vector.
00:27:43The vector size.
00:27:44Increases.
00:27:45But the capacity.
00:27:46At the beginning.
00:27:47Was hundred.
00:27:48And it stays.
00:27:49That way.
00:27:49Till.
00:27:50Hundred students.
00:27:51Are added.
00:27:52If you want to add.
00:27:54The hundred first.
00:27:55Student.
00:27:56There would be.
00:27:57Dynamic memory.
00:27:58Allocation.
00:27:59For larger.
00:28:00Buffer.
00:28:00And behind the scene.
00:28:02Housekeeping.
00:28:03Would be done.
00:28:04So that the.
00:28:05Student register.
00:28:06Vector.
00:28:06Can have.
00:28:08One hundred.
00:28:08One students.
00:28:10The subscript.
00:28:10Operator.
00:28:11Is used.
00:28:12For accessing.
00:28:13The elements.
00:28:14Using an index.
00:28:15In the range.
00:28:16Zero.
00:28:17To size.
00:28:17Minus one.
00:28:18But by default.
00:28:19There is no.
00:28:20Range checking.
00:28:21Of the index.
00:28:22So if the index.
00:28:23Is outside.
00:28:23The valid range.
00:28:24The program.
00:28:25May give.
00:28:26Erroneous output.
00:28:27Or it might.
00:28:28Crash.
00:28:29The act.
00:28:30Member function.
00:28:30Checks.
00:28:31Whether the index.
00:28:32Is within the.
00:28:33Valid range.
00:28:34Or not.
00:28:35If it is in the.
00:28:37Valid range.
00:28:38It returns.
00:28:39A reference.
00:28:40To the element.
00:28:41At the specified.
00:28:42Position.
00:28:43You can read.
00:28:44And modify it.
00:28:45But if the index.
00:28:47Is out of range.
00:28:47It throws.
00:28:49STD.
00:28:49Out of range.
00:28:50Exception.
00:28:51Which can be.
00:28:52Caught.
00:28:52By the program.
00:28:54So here.
00:28:55In this example.
00:28:57Let's look.
00:28:57At the.
00:28:57For loop.
00:28:58The size.
00:28:59Of student.
00:29:00Vector.
00:29:01Is four.
00:29:02So I.
00:29:03Would vary.
00:29:03From zero.
00:29:04To four.
00:29:04Inclusive.
00:29:05But I.
00:29:06Equal to four.
00:29:07Is.
00:29:08Index.
00:29:09Out of range.
00:29:09Situation.
00:29:11So.
00:29:11STD.
00:29:12Out of range.
00:29:13Exception.
00:29:14Generated.
00:29:14Which is.
00:29:15Caught.
00:29:15By the.
00:29:16In the.
00:29:17Plot.
00:29:18And we.
00:29:18Get this.
00:29:19Output.
00:29:20The first.
00:29:20Four.
00:29:21Lines.
00:29:21Okay.
00:29:22But when.
00:29:22The index.
00:29:23Value is.
00:29:23Four.
00:29:24It says.
00:29:25This is.
00:29:26Than.
00:29:26Or.
00:29:26Equal to.
00:29:27Size of.
00:29:27The.
00:29:27Vector.
00:29:28Which is.
00:29:29Four.
00:29:29And.
00:29:30This is.
00:29:30Out of range.
00:29:31So.
00:29:32Using.
00:29:32The.
00:29:32Add.
00:29:33Member.
00:29:33Function.
00:29:34Instead.
00:29:34Of.
00:29:34The.
00:29:35Subscript.
00:29:35Operator.
00:29:36We are.
00:29:37Able.
00:29:37To.
00:29:37Catch.
00:29:38This.
00:29:39Exception.
00:29:40And.
00:29:40Program.
00:29:40Works.
00:29:41Properly.
00:29:42It.
00:29:42Does.
00:29:42Not.
00:29:42Show.
00:29:43Junk.
00:29:44Or.
00:29:44It.
00:29:45Does.
00:29:45Not.
00:29:45Crash.
00:29:46If.
00:29:46You.
00:29:46Wish.
00:29:47To.
00:29:47Use.
00:29:47The.
00:29:48Subscript.
00:29:48Operator.
00:29:49And.
00:29:57Overload.
00:29:58The.
00:29:58Subscript.
00:29:59Operator.
00:30:02For.
00:30:03Accessing.
00:30:04Vector.
00:30:04Elements.
00:30:05For.
00:30:05Example.
00:30:06Here.
00:30:07Template.
00:30:07Type.
00:30:08Name.
00:30:08T.
00:30:10Vec.
00:30:11Derives.
00:30:11From.
00:30:12Std.
00:30:12Vector.
00:30:12T.
00:30:17Vector.
00:30:18This.
00:30:18Is.
00:30:19The.
00:30:19Constructor.
00:30:20Inheritance.
00:30:21And.
00:30:21What.
00:30:22It.
00:30:22Means.
00:30:22Is.
00:30:22That.
00:30:23All.
00:30:23Constructors.
00:30:24Of.
00:30:24Std.
00:30:25Vector.
00:30:25T.
00:30:26Become.
00:30:27Available.
00:30:28In.
00:30:29Derived.
00:30:29Class.
00:30:30Vec.
00:30:30T.
00:30:31T.
00:30:32Reference.
00:30:32Operator.
00:30:33Subscript.
00:30:34Int.
00:30:35And.
00:30:36Here.
00:30:36We.
00:30:36Use.
00:30:36The.
00:30:37At.
00:30:37Function.
00:30:38For.
00:30:38Returning.
00:30:39A.
00:30:39Reference.
00:30:39To.
00:30:39Element.
00:30:40At.
00:30:41Index.
00:30:41I.
00:30:42So.
00:30:42Says.
00:30:43Return.
00:30:44Std.
00:30:45Vector.
00:30:45T.
00:30:46At.
00:30:47I.
00:30:48And.
00:30:48The.
00:30:48Same.
00:30:48For.
00:30:49Constant.
00:30:50T.
00:30:51Reference.
00:30:51Operator.
00:30:52Subscript.
00:30:53Inti.
00:30:54Constant.
00:30:55Return.
00:30:56Std.
00:30:57Vector.
00:30:57T.
00:30:58At.
00:30:58I.
00:30:59That's it.
00:31:00We can use the Vec.
00:31:02Class.
00:31:02Template.
00:31:04And.
00:31:04We define Vec.
00:31:05Student.
00:31:05Student.
00:31:07Vector.
00:31:07Container.
00:31:08And.
00:31:09We.
00:31:09Add.
00:31:09Four.
00:31:10Elements.
00:31:11Using.
00:31:11The.
00:31:11Pushback.
00:31:12Member.
00:31:12Function.
00:31:14And.
00:31:14Then.
00:31:14We.
00:31:14The.
00:31:14Student.
00:31:15Register.
00:31:15Where.
00:31:16We.
00:31:16Access.
00:31:17Using.
00:31:18Subscript.
00:31:18Operator.
00:31:19And.
00:31:19Here.
00:31:20Deliberately.
00:31:21We.
00:31:21Are.
00:31:21Trying.
00:31:21To.
00:31:22Past.
00:31:22The.
00:31:22Last.
00:31:23Element.
00:31:23Vector.
00:31:24Just.
00:31:25To.
00:31:25See.
00:31:25Whether.
00:31:25The.
00:31:26Exception.
00:31:26Index.
00:31:27Of.
00:31:27Range.
00:31:28Generated.
00:31:29And.
00:31:30Whether.
00:31:30It.
00:31:30Caught.
00:31:31And.
00:31:31It.
00:31:32As.
00:31:33Expected.
00:31:34Using.
00:31:34The.
00:31:34Vect.
00:31:35Class.
00:31:36Template.
00:31:37Which.
00:31:37Derived.
00:31:38From.
00:31:38Std.
00:31:38Vector.
00:31:40We.
00:31:40Can.
00:31:40Use.
00:31:41The.
00:31:41Subscript.
00:31:41Operator.
00:31:42For.
00:31:43Accessing.
00:31:43Vector.
00:31:51The.
00:31:54Commonly.
00:31:54Used.
00:31:55Container.
00:31:56C++.
00:31:57It.
00:31:57Provides.
00:31:58Constant.
00:32:00Random.
00:32:01Access.
00:32:01To.
00:32:02Its.
00:32:02Elements.
00:32:03This.
00:32:03Is.
00:32:04Important.
00:32:04Part.
00:32:05The.
00:32:05Time.
00:32:05Required.
00:32:06To.
00:32:06Access.
00:32:06An.
00:32:07Element.
00:32:08Is.
00:32:08Independent.
00:32:09Of.
00:32:09The.
00:32:10Elements.
00:32:25Occupy.
00:32:26Success.
00:32:26In.
00:32:26Memory.
00:32:27Locations.
00:32:28This.
00:32:28Leads.
00:32:28To.
00:32:28Good.
00:32:29Cache.
00:32:29Performance.
00:32:30By.
00:32:30The.
00:32:30CPU.
00:32:31Vector.
00:32:32Is.
00:32:32Slightly.
00:32:32Slow.
00:32:33In.
00:32:33Adding.
00:32:34Deleting.
00:32:34Deleting.
00:32:35Elements.
00:32:36In.
00:32:36The.
00:32:37Where.
00:32:37It.
00:32:38On.
00:32:38Time.
00:32:39Complexity.
00:32:40Vector.
00:32:41Preferred.
00:32:42Container.
00:32:43C++.
00:32:44Study.
00:32:46The.
00:32:46Container.
00:32:46Class.
00:32:47Template.
00:32:47It keeps a sequence of elements or nodes in a doubly linked list.
00:32:52Each node has the forward and backward links or in common parlance the next and the previous
00:32:59links apart from the data members.
00:33:02Most implementations keep a sentinel node after the last element.
00:33:08The sentinel node has the next and previous links but it does not have any data members.
00:33:14There is a link from the last element to sentinel and vice versa.
00:33:19Similarly there is a link from the sentinel to the first element and vice versa.
00:33:25This makes it a circular doubly linked list.
00:33:28In most implementations the sentinel node is embedded in the list object.
00:33:34So the links to the first and the last element of the list are available in the list object itself.
00:33:41Now the sentinel and the links are implementation details which help us in understanding the list.
00:33:48But these details are not specified in the C++ standard.
00:33:53The standard is silent on the implementation and the details are left to the C++ standard library implementers.
00:34:02We need to use the standard library as per the public library interface.
00:34:09So to a user or programmer the list appears to be a sequence of elements which can be accessed sequentially,
00:34:17no random access and if you have an iterator at a position in the list elements can be added
00:34:24or deleted with O1 time complexity at the place pointed by the iterator.
00:34:31This operation is very fast because there is no shuffling of elements before or after the insertion or deletion.
00:34:41Not like the vector where the rest of the elements need to be moved up or down.
00:34:45It is not like that.
00:34:47Here in this example we traverse a list.
00:34:51Struct student has two data members intro number and std string name.
00:34:58The operator overlook functions for output put to operator and input get from operator.
00:35:05and the std list container has elements of type student.
00:35:10It has three elements and we have function print register for printing the contents of the student register list.
00:35:18It uses a range for loop to iterate over the contents of student register and then printing on the basis
00:35:27of student name.
00:35:29That is given a student name we search for that student in the list and print the details.
00:35:37So it is a loop, read a student name and execute the function print student details.
00:35:45And in the print student details we traverse the list from the beginning to the end using a range for
00:35:52loop.
00:35:52For each element we check the name, if it matches we print that element and return.
00:36:00And there is an error message if no student is found.
00:36:04Similarly we have a loop where the user can enter row number and we have print student details 1.
00:36:12And this function goes through the list sequentially as before and if there is a match the element is printed.
00:36:20Earlier in the print student details we had used the elements in the for loop.
00:36:26But here in print student detail 1 we are using an iterator S.
00:36:32S is an iterator with initial value student register dot begin which points to the first element and we stop
00:36:41when the iterator is at student register dot end which points one past the last element.
00:36:48And here we print pointer S that is the element pointed by S.
00:36:55Next we try to insert elements in the list.
00:36:59Say initially the list has three elements.
00:37:03We define three students S1, S2 and S3 and we will try to insert these records in the list.
00:37:11There is push front member function for adding an element at the start of list.
00:37:17And there is push back for adding at the end of list.
00:37:22So we say student register push front S1.
00:37:27Student S1 is now added to the front of the list.
00:37:30And we say student register dot push back S3 for adding S3 at the end of the list.
00:37:38Now list is five elements and we wish to add student S2 at element number 3.
00:37:45That is we wish to make S2 the third element in the list.
00:37:51So first we go to the beginning of the list by defining an iterator it and the assignment it equal
00:37:59to student register dot begin.
00:38:02Now it points to the first element.
00:38:04Next we say std advance IT 2.
00:38:09This advances it by two elements and now IT points to the third element.
00:38:15Now it is at the proper place and we say student register dot insert IT S2.
00:38:23Which means insert S2 at the location pointed by IT.
00:38:29And S2 becomes the third element.
00:38:31And if we print the student register list now.
00:38:35It is like this.
00:38:37We have added Jack Dawkins at number 1.
00:38:40Jane Doe at number 3.
00:38:42And Alfred Dolittle at the end.
00:38:45The splice member function in std list is for transferring a part of one list to another.
00:38:53Or we can transfer one part of a list to another position in the same list.
00:38:58And here we use iterators for pointing the elements for transfer.
00:39:04Or for the distinction location of the transferred elements.
00:39:09The main point is the splice operation is very fast.
00:39:13Over time complexity.
00:39:15There is no copying of elements.
00:39:18Only the pointer links are adjusted.
00:39:20As an example.
00:39:22Here we have two lists.
00:39:24Student register with six students.
00:39:27And new students with five students.
00:39:30We wish to transfer three students.
00:39:33Second, third and fourth.
00:39:35In the new students list.
00:39:37To the student register at the third place.
00:39:41First, we set an iterator in the target list.
00:39:46It is the iterator which is equal to student register dot begin.
00:39:51It points to the first element in the student register.
00:39:54We advance it by two.
00:39:57That is std advance it two.
00:40:01So now it points to the third student.
00:40:03Now we go to the source list.
00:40:06Here we did two iterators.
00:40:08Start and end iterators.
00:40:12It1 is the start iterator.
00:40:14It1 equal to new students dot begin.
00:40:17It1 points to the first element in the new students.
00:40:22std advance it1 1.
00:40:26Advance it1 by 1.
00:40:28So it points at the second location.
00:40:32Next, auto, it2, std next, it1 3.
00:40:38Since it1 points to the location number 2.
00:40:41It2 points to location 5.
00:40:45Next, student register dot splice, it, new student, it1, it2.
00:40:53Transfer new students IT1 to IT2 but not including IT2 to location pointed by IT.
00:41:03And we run it.
00:41:04The three students are not there in the new students list and they are there in the student
00:41:10register at location 3.
00:41:13The next job is to transfer students 678 in student register to position 2.
00:41:20Also in the student register.
00:41:23That means Jane Doe, Joblox and Fednerk should go up just behind Jack Dawkins.
00:41:33And we use three iterators.
00:41:36First, IT points to position 2.
00:41:38The target position.
00:41:40IT1 points to 6th location.
00:41:42Jane Doe and IT2 points to 3 locations away from IT1.
00:41:47That is the ninth position.
00:41:49One after Frednerk.
00:41:52And we say student register dot splice IT student register IT1, IT2.
00:41:59We can run the program and Jane Doe, Joblox and Frednerk are transferred starting at the
00:42:07second position.
00:42:07And finally, we can transfer what is left in the new student list to the end of the student
00:42:14register.
00:42:15And we need to say studentregister dot splice studentregister dot end new students.
00:42:24And Max Musterman and Harvard Pocket have been transferred to student register and new
00:42:30students is now empty.
00:42:32So what is our take on list?
00:42:35In list, we have the splice operation which is very efficient.
00:42:40There is the merge operation where two sorted lists are merged into a single sorted list.
00:42:48And merge is also very efficient.
00:42:50The efficiency comes from the fact that the elements are not copied during these operations.
00:42:56only the links are updated.
00:42:59Splice is useful in implementation of caches and task schedulers.
00:43:06The list is useful when there are going to be a lot of additions or deletions of elements
00:43:12in the middle.
00:43:14What goes against list is that its elements are not contiguous.
00:43:18The elements are scattered in memory and there is pointer chasing coming into play at runtime.
00:43:25So cache performance may not be good.
00:43:28So vector continues to be the preferred container.
00:43:32The next container is map.
00:43:34Map is an associative container.
00:43:36Associative containers retrieve elements using lookup keys rather than sequential indices.
00:43:43Each element in a map is a key-value pair.
00:43:47That is, a value corresponds to a key.
00:43:51The key is unique for each element in a map.
00:43:54Maps are implemented in C++ using red-black trees which are self-balancing binary search trees.
00:44:04The time complexity for search, insert and delete operations is O log N.
00:44:11A map stores key-value pairs.
00:44:15Since map is a class template, it has at least two template parameters.
00:44:21Something like std double colon map key comma t.
00:44:26So here we have two template parameters.
00:44:29Key is the type of the key and t is the type for the mapped value.
00:44:34Internally, map stores elements as key-value pairs.
00:44:38That is, std double colon pair, constant key comma t.
00:44:44The constant keyword signifies that the key is constant.
00:44:49It cannot be changed after insertion.
00:44:52Only the value corresponding to the key can be changed.
00:44:56A constant key is required to maintain the internal integrity of the map's data structure.
00:45:03For example, here we have the map student register.
00:45:08The template parameters are int and std string.
00:45:12That is, the key is of type int which maps to a value which is student's name and is of
00:45:20type std string.
00:45:22The print register function prints all the elements of the map.
00:45:27In a map, all elements are arranged in the increasing order of the key.
00:45:33Map elements are stored as std pair which has two public data members, first and second.
00:45:41So we use a range for loop in which x iterates over the elements of the map and prints the
00:45:48first and second data members of each element.
00:45:53Next, since map is an associative array, we can index it using a key to get to the corresponding value.
00:46:01So we can say student register subscript 123457 and it prints job logs.
00:46:11What happens if we use the subscript operator for a non-existent key?
00:46:17Suppose we say student register 123459 and there is no student in the map with this key.
00:46:26It turns out, if the subscript operator is used with a non-existent key, map creates a new element for
00:46:33that key and fills the value fields with defaults.
00:46:37So here, an element with the key 123459 is created with name as null and str is printed with nothing
00:46:48for the null value.
00:46:50This might be okay in some cases but it is a kind of spurious record in lot of other cases
00:46:56and we might not want this.
00:46:59So in those cases, we don't use the subscript operator for accessing the element's value.
00:47:05We use mapsFindMember function with a key value and it returns an iterator pointing to the relevant element.
00:47:15If there is no element for the given key, the iterator points to the end which is the last element
00:47:23plus 1 and then we can conclude the element does not exist.
00:47:27There are many ways to insert elements in a map. We will look at two of them.
00:47:33The first is the insertMember function in maps. If the key of the given element does not exist in map,
00:47:40the insertMember function inserts the element in the map.
00:47:43But if the key exists, nothing is done. There is no overwriting of data existing in the map.
00:47:50The second way is to use the assignment operator. We can index a map with a key and assign a
00:47:56value. After that, this element is part of the map. If it did not exist earlier, a new element is
00:48:04created. If it existed, the existing value is overwritten.
00:48:09For example, there is an existing element 123456 John Doe. Now if we say studentregister.insert 123456 Alice Wonderland, nothing
00:48:23happens because there is an existing element 123456 John Doe.
00:48:30But if we index the map using the key and make the assignment, but if we index the map using
00:48:44the key and make the assignment, studentregister.insert 123456
00:48:58and value Herbert pocket. Similarly using the assignment, if we say studentregister.insert 123456
00:49:070 equal to Sarah pocket, the element 123456 Sarah pocket is created. We can erase elements from a map and
00:49:19the simplest way to do that is to erase using the key. If there is no element for the given
00:49:25key, nothing happens.
00:49:27Alternately, we can erase elements. Alternately, we can erase an element using an iterator. However, it must be a valid
00:49:35iterator and it must not be the end iterator.
00:49:39You can erase multiple elements and iterator range it1 to it2 and here also it1 and it2 must be valid
00:49:49iterators for the map and it2 must be greater than or equal to it1.
00:49:56And to erase all elements in a map, we can use the clear member function. For example, when we say
00:50:05studentregister.erase 123456 then the element 123456 is erased. Now erasing using an iterator, we initialize the iterator with find
00:50:19function for the key 123458 and check that iterator is valid.
00:50:35So the clear difference. In case of erasing by key, it is not necessary to check whether the key exists
00:50:43or not. But for the iterator, we need to check its validity. In fact, when we say studentregister.erase 1
00:50:53and there is no element in the
00:50:55key 1, nothing happens. Now we can erase elements for iterator range. So for that, we add 2 elements in
00:51:04our map making a total of 5 elements and now we wish to erase elements 2 to 4. And for
00:51:13that, the map must have at least 4 elements.
00:51:16We set it1. We set it1 iterator to begin and then we advance it by 1. So it1 points to
00:51:23the second element. Since we wish to erase 3 elements, we make it2 point to 3 elements after it1. And
00:51:33then we say studentregister.erase it1, it2.
00:51:38Now using the iterator range, both it1 and it2 must be valued iterators and it2 must be greater than or
00:51:47equal to it1. These are the requirements for using iterator range in the erase function.
00:51:53And we wish to erase the entire map. We say studentregister.clear and all elements in the map are erased.
00:52:05To summarize on maps, we can say map is an associative container. It contains key value pairs as elements.
00:52:14The elements. The elements are ordered in the ascending order of the key by default. It provides ologn time complexity
00:52:23for lookup, insertion, renewal of elements.
00:52:28Regarding the cons, the memory used by maps is not contiguous. So there is poor cache locality, the memory overhead
00:52:38is high and it involves pointer chasing.
00:52:41Maps are fast. Maps are fast but unordered maps which we will see next are faster.
00:52:48Now we look at unordered maps which like maps is an associative container and stores key value pairs as elements.
00:52:58The implementation is quite different from maps. Unordered maps are implemented using hash tables.
00:53:05Now hash table is an all-encompassing concept. It comprises of data structures and algorithms. For data structures part, we
00:53:17have a bucket table which is an array of buckets and each bucket holds 0 or more elements.
00:53:25At the implementation level, a bucket can be linked list of elements.
00:53:30Regarding algorithms, we have a hash function which transforms a key value into a hash value.
00:53:37HV equal to F key. F is the hash function which converts the key to an integer hash value.
00:53:45We can map the hash value HV into an index into the bucket table by say index equal to HV
00:53:55modulus n.
00:53:57This gives an index value in the range 0 to n-1.
00:54:03Now the problem is multiple key values can ultimately convert into the same index in the bucket table.
00:54:10This is called a collision where multiple key values convert to the same index.
00:54:16A bucket can have multiple elements in a linked list.
00:54:20This is a simplified way of putting things. The actual implementation might be more involved.
00:54:25A well-tuned unordered map that is a bucket table of adequate size, a good hash function and also a
00:54:35good mapping function which maps the hash value to a bucket table index.
00:54:40If these are well-tuned, we can get O1 time complexity.
00:54:45However, the worst case scenario is O n time complexity.
00:54:50The member functions for operations in unordered maps are the same as that of maps and we can easily convert
00:54:58the map program to the one that uses unordered maps.
00:55:03First the header file. It should be unordered map. Then the type should be changed from map to unordered map
00:55:10and we are good to go.
00:55:12We can compile and run the program. It produces the same results.
00:55:16The standard template library STL provides a triad of three fundamental interrelated concepts and these are containers, iterators and algorithms.
00:55:32Containers provide storage for their elements.
00:55:35Algorithms provide the logic for doing work on the elements of container and iterators provide a standard interface to the
00:55:45elements of containers.
00:55:46Iterators are the link between algorithm and containers.
00:55:51Algorithms work on a sequence of elements. Sequence is represented as the elements between two iterators.
00:55:59Algorithms work on half-open sequences. A half-open sequence between a and b is specified as left square bracket
00:56:09a comma b right parenthesis.
00:56:12This means range between a and b where a is included and all elements upto b are included but b
00:56:23is not included.
00:56:26Algorithms do work like copy, sort, unicopy etc on the elements of the sequence. Algorithms are part of std namespace
00:56:37and the header file algorithm needs to be included.
00:56:40Some of the algorithms available in the standard library are std find first last value. This is for searching value
00:56:52in the container. It returns iterator to the first occurrence of value in the range first last.
00:57:00std find if first last f where f is a predicate and this returns an iterator to the first element
00:57:10for which the predicate f is true.
00:57:14std count if first last f is true. std count if first last f returns the number of elements in
00:57:31the range first last meeting the criteria indicated by the predicate f.
00:57:37std count if first last f. std count if first last f. std count if first last f. std count
00:57:41if f. std count if first last f. std count if f. std count if f. std count if f.
00:57:44std count if f. std count if f. std count if f. std count if f. std count if f.
00:57:55std count if f. std count if f. std count if f. std count if f. std count if f.
00:57:55std count if f. std count if f. std count if f. std count if f. std count if f.
00:57:56std count if f. std count if f. std count if f. std count if f. std count if f.
00:57:57std count if f. std count if f. std count if f. std count if f. std count if f.
00:58:01std count if f. std count if f. std count
00:58:06range first last to the range starting at iterator out. There must be adequate
00:58:13number of existing elements at the destination range so that the source
00:58:19element can be copied. STD copy if first last out p, copy the elements from the
00:58:28source range to the destination out if the predicate p is true. You need copy
00:58:35first last out unit copy copies the elements in the range first last to the
00:58:42range starting at iterator out and most importantly removing consecutive
00:58:50duplicates it copies the first element the next element only if it is different
00:58:56from the previous and so on. STD sort first last sorts element between the first and
00:59:04last iterator in ascending order and STD sort first last f this sorts elements
00:59:12between the first and last iterators using f as the sort criteria. f is a custom
00:59:19comparison function we can define f suitably to sort in a certain way say
00:59:26descending order. STD equal range first last value for this function the range
00:59:33between the iterators first and last must be sorted. It returns results which is a
00:59:41pair of values result dot first is not less than the value and result dot second is
00:59:49greater than the value and we have STD merge first one last one first two last two
00:59:56result here first one last one and first last two are input sorted sequences and the result is the
01:00:06merged sequence. An iterator is a pointer like object used for accessing elements of a
01:00:14container. We can dereference it just like a pointer and access the pointed element. There are two
01:00:22important iterators begin and end. The iterator begin points to the first element in the container. The
01:00:30iterator end points to one past the last element of a container. The end iterator
01:00:37cannot be dereferenced. It is there just to tell that there are no more elements to be accessed. For
01:00:44example here we have vector v with four elements and we can access the elements using the
01:00:51iterator p. The type of iterator p is std double colon vector int double colon iterator.
01:01:01Normally we do not write all that we can just say auto p and it works fine. So we start
01:01:08with p equal to v dot begin and that is the first element and the loop ends
01:01:14when p is equal to v dot end. Note that we never access p when it is equal to the
01:01:21end iterator. We just stop there and the loop terminates.
01:01:26There are library functions that return iterators based on certain criteria. For example let's say we have a vector int
01:01:35v and we wish to find elements with the minimum and maximum values.
01:01:41So there is a library function std min max element which gives iterators that point to the minimum and maximum
01:01:51values. And we can receive these iterators in an object of type std pair.
01:01:58Std pair is a structure with two members. Here we have std pair where each member is an iterator to
01:02:07a vector of int. Or we can just say auto p and it works.
01:02:11It works fine. But we can do better. Instead of say auto p we can say auto square brackets minute
01:02:19maxit which is structured bindings.
01:02:23So because of assignment minute becomes equal to the first element of pair and maxit becomes equal to the second
01:02:31element of std pair.
01:02:33Now minute and maxit are iterators and not values. What happens if the vector is empty? If the vector is
01:02:42empty it has no elements. V dot begin is equal to V dot end which is the last.
01:02:49And both minute and maxit would be equal to the last. And the dereference operator is not defined for the
01:02:56last. So if we do that we get a run time error like segmentation fault.
01:03:02We can put a small check if minute not equal to V dot end before the print statement and it
01:03:10works fine for empty vectors as well.
01:03:14The stream iterators are iterators for input and output streams. Stream iterators help in using the STL algorithms with streams.
01:03:27C++ has the STL triad of containers, iterators and algorithms which work together to provide efficient and reusable code.
01:03:41The containers are sequences of elements. We can use iterators for the elements which can be connected to algorithms.
01:03:50Now if we look closely the data passing through a stream it is also a sequence of some object like
01:03:57character, int, string, a user defined type etc.
01:04:03So if we have iterators that can get hold of the data sequence we can connect that to STL algorithms
01:04:12and get the full benefit of STL algorithms for the data flowing through the streams.
01:04:17Thus we have stream iterators and these are std istream iterator T for formatted input of type T, std istream
01:04:30iterator T for formatted output of type T, std istream buff iterator char for raw corrector input and std istream
01:04:41buff iterator char for raw corrector output.
01:04:44Since we are dealing with objects and not raw characters we will confine our attention to the first two here
01:04:52in this video.
01:04:53std istream iterator std istream iterator std istream iterator T is for formatted objects of type T in the stream.
01:05:01For example std istream iterator int ii std cin.
01:05:08This is an input stream iterator ii this is an input stream iterator ii handling objects of type int and
01:05:15connected to the standard input std cin.
01:05:19We need a special sentinel input stream iterator for signaling the end of input and it is std istream iterator
01:05:29int eos braces.
01:05:32This indicates the end of input there are no more objects of type int in the input stream.
01:05:39Similarly we have output stream iterator std istream iterator int oo std cout comma backslash m the new line character
01:05:52which means oo is an output stream iterator connected to std cout and it has a delimiter backslash m the
01:06:03new line character.
01:06:04So this iterator so this iterator adds a new line character after each integer object.
01:06:11Here we have a small example of using stream iterator.
01:06:15The vector v has three string elements a, b and c and we have output stream iterator os connected to
01:06:24std cout and it puts a space delimiter after each string.
01:06:30So there is the standard library copy algorithm to which we pass the iterator vbegin and vend and the output
01:06:39stream iterator os.
01:06:41It copies the elements of vector v from vbegin to vend to stream iterator os and we can see the
01:06:50results.
01:06:50Another example ii is the input stream iterator eos is for signaling end of input stream and oi is the
01:07:00output stream iterator.
01:07:01We create a vector v of std string for the range input iterator ii and end of stream eos.
01:07:11We sort the vector v and vector v might have duplicates.
01:07:15Since it is sorted the duplicates are arranged as consecutive elements and we do a unique copy of vector from
01:07:24vbegin to vend to output stream iterator.
01:07:27And this is the result the elements are sorted and duplicates removed.
01:07:34A predicate is a function that returns a boolean value false or true.
01:07:40Predicates test conditions like whether a given value is odd and return false or true.
01:07:47Or another example check whether a given value is greater than a base value and return false or true.
01:07:56For example we might wish to find the first odd number element in a vector of integers and we can
01:08:04use the algorithm std find if vbegin, vend isOrd.
01:08:11IsOrd is the predicate, it checks whether the element is odd or not and this is the program where isOrd
01:08:18is a function object or functor.
01:08:21We can use a lambda expression instead of functor and the code is like this.
01:08:26You can find the code for all the examples in this video at soft priyok website.
01:08:32Here is the QR code and the link is there in the description.
01:08:36If you like this video please share it and subscribe to our channel.
Comments