Category Archives: Pointers and references in C ++

This category contains lessons about pointers and references in C ++

Pointers in containers. STL (part 16)




Indices in containers, STL, Programming for beginners

STL containers significantly reduce the complexity of writing code, working with dynamic data structures and, the most important thing, increase its inerrancy. But in some cases, when working with large data items in containers, This technique can produce the inevitable loss of productivity. This is because, that since the operation room a container element, and subsequent displacement elements may require a copy of elements.

Note: The severity of these effects depends on the type of container, and from the transactions. For example, interchange operation 2 elements in the sorting require 3 copyings type container vector and will not require additional copy for container list. But the operation of the initial space in the container (push_back(), insert() and etc.) always make a copy.

This can be a problem for an application, when operations on the containers is critical for runtime (or seem to you such). There are even more complicated cases, when a class container object is not picked up operation, or when the objects are referenced objects themselves, full backups for which you want to perform recursive procedures following all the links (then, in Python, and the other is called a deep copy).

Everything works well, as before - sort a set of records on arbitrary fields and in any order:

16-1

(Note, that completing this application you need for Ctrl + D - End Of File ... in the Widows, probably, по Ctrl + Z.)

But! ... Especially debugging "traces" positives were left constructors and destructors records, and recording constructed 8 times, and the destructor is only triggered 4, for local array at the exit point of the block. Local array generally not of interest to us. He was introduced to simplify the example, only as a set of initialization values. But for the record, placed in a container, records destruction does not occur, and we get a candid memory leak. But worse, after we remove the item from the container (without taking further action), we can not delete the record, calling for it delete. This is because, after call erase() We lost to a record only path through the iterator (the code shows a loop erase(), so graphically, that is equivalent to clear(), the effect of which, It is the same).

Conclusion, which can be made from Example, looks like that:

  • placing objects in containers not, and Indices on them, can significantly reduce the computational cost of the manipulation (but always principled whether these gains at the current computing power?).

  • replacement facilities pointers in containers makes the code is much more dangerous in the sense of hidden subtle bugs, And such a serious level, which can further lead to an application crash.

Here some help may have smart pointers of the latest C ++ standard (shared_ptr or weak_ptr, but not unique_ptr and not the good old and problematic auto_ptr), us for this in the previous code, just change 4 strings:

In Windows, shared_ptr needed #include <memory> , and in other systems, not necessarily.

And application behavior change significantly:

16-2

But we should not delude ourselves recklessly, so as smart pointers, removing some, generate other potential concerns (such as cyclic links etc.. about which much is written enough).

Newsletter of programming:

Binary trees (briefly about the main)




бинарное дерево с++, binary tree c ++, hierarchy, binary treeAt all, i must admit, that the theme of hierarchical structures is very wide. About it it is possible to argue long and hard, and did not come to a common denominator, clearly shows that such a hierarchy and how to work with it, for some canons in the sense of. I will not go into the jungle of mathematical horrible Tartarus. It is no one but academics are not interested, and in the foreseeable practical too thin.

So. As an example, take binary tree wood. What tree do? This is a set of data, which point to other data. Dynamic list. Incidentally lists this particular kind of tree. Moreover, the binary. The tree consists of branches (knots) and leaves (elements). Leaves – it hosts, which do not point at anyone, they do not have branches. binary tree – this is a tree, wherein at threads may be no more than two leaves or twigs. Hence its name – “binary” so “binary”, i.e.. or less than two elements. But not more than two.

Here is an example of such a binary tree (Yandex in Pictures found):

But ordinary tree:

An ordinary tree nodes in branches can be.

I will not go into the classification tree. This is also a large amount of information. This can be found in Wikipedia, what they are. You can type in a search word “Graph” and read. The main thing is not to stumble on this graph, which are the Countess. On Thursdays and Saturdays :)

The basic rule of the formation of a binary tree in C ++: If the node is greater than the added – added the right branch, otherwise a left branch.

The rule is simple, from him, and we will build. For this we need the structure of, described like a dynamic list: The data field and two pointers to the left and right branches. In dynamic lists two pointers are usually associated next and previous elements, in this case a tree with no need, because the, usually, pass on the tree is a root. Although of course can be and Feedback, if you really want.

Field Data It presents data, on the basis of which the constructed tree. More precisely one of these elements. Fields Branch describe the left and right branches of a tree, and are pointers to the same structure.

Tree items can be any value. Arrays, strings (the string is an array of characters if anything), other trees… Data fields can be many. In each field, you can build your tree. This example is from an array of characters – string.

Just show the main code tree construction, so you can understand what kind of data source is taken as an example:

String. Common string C, which will raise the branches. Units and sheets will contain characters, on codes of characters will also determine the right or to the left to construct tree. Although I took into digital characters string, it does not matter. With the same success it is possible to write a string “They killed Kenny”.

How should the work program? Take symbols “12384” from a string. First, the program sees , a tree without roots. He is not here yet. It is necessary to sow the seed, so it grew. The first character will become the root, respectively. The second character – “2” It will be compared with the root. According to the code of its value is greater than. So at the root to grow to the right branch (RightBranch) in our case. Next comes the triple. We already have two branches. The program should work through them, check: 3 more 1? – Yes. Go right. there couple. 3 more 2? Yes sir. After deuces no branches, It means it is necessary to create a branch to the right to assembly “2”.

Next comes eight. What to do with him? Same. From unit to go through a deuce to triples and just grow right branch.

After eight is 4. This value will take root. Since it is more, program should look, Do you have the right root branch. There are – go for it. Pass the “2” and “3”, for 4 More meaningfully. Further to the right to meet the number of 8. it is less than. so “4” already go from eight not right, and left.

The simplest code tree construction (with a hierarchical structure) It will look like:

Note: The functions of the three basic conditions:

  1. If a branch node is not created – create it, fill the data and specify NULL (0) for its branches;
  2. If the transmitted data is greater than the current node data – try to build it right branch, or if it is already there just to pass through it;
  3. The same is true for the left branch, if the data value less.

Hierarchy is very friendly with recursion. Recursive call functions, to pass through the column, tree or other type of hierarchical structure – It is the easiest way. Used by the way in artificial intelligence. The above code carries a kind of search, but not for result, and to find a place for the element.

It is all! What do you think? Tree ready. Yggdrasil famous could well be established here so that's 14 th strings in C ++. Or is there some divine-cosmic language used? If you think, it is difficult to plant a tree – here's the obvious unbelievable. No. Nothing complicated there. Well, maybe N-dimensional tree will be slightly more difficult to implement…

In this case, in order to understand the principle of its construction does not need a ton of code. It is not necessary to consider the insertion between the nodes, for example to organize a tree or develop code for balancing the tree. Naked principle in its essence is very simple. And if in the writing of a spider to surf the sites on the Internet or various 3D design programs, such as those, that develop Autodesk, knowledge trees and graphs need crazy, in the case of a simple core framework is enough and something simpler.

It remains perhaps for compliance “Feng” write traversal code and display

and the release of a tree:

Here probably seen another principle of working with trees. At print() recursively called consecutive jump from branch to branch. And between calls, data is inserted into the output node, from which branches grow, To properly display on the screen, or simply to work for example when searching for data.

The release comes as a recursive call to release branches. First, the entire left, then all right with their used and worksheets, and then freed himself calling node. It is important, because if you put delete at the beginning of the function we will get either an error (that likely) or all the branches growing from the site simply can not free, hovering in the memory garbage.

In any case, I will explain one more trick in the output:

Before the conclusion of the current node data derive a certain amount of indentation. This is done for beauty, so that the screen looks like a real tree, and not just the data set. To be able to see the structure of their own eyes.

To do this, we define a global variable int tabs=0; that will count the number of indents, and upon (by the way!) be the bearer of values node level, i.e.. number of its nesting. How many parents of this node branches until the root. This concept can also be found in the literature about the trees. So it's there (code meaning) not only for guidance on the screen beauty.

Here is the complete code (when the tree is started “increases” not downward, as in figures, and from left to right. I do not want to complicate the code):

On the screen:

бинарное дерево с++, binary tree c ++, hierarchy, binary tree

Well… Perhaps this about binary trees in C ++ all. How else to describe the principles of short, I do not know, but absolutely sure, that get into the wilds of academic spaces (read: prostration) not necessary. The simpler explanation is as, so it is closer to the truth.

Video. Author – “mycodeschool”:

Newsletter of programming:

References in C++





C ++ references, ++ reference variables

In our previous articles, we have already mentioned that, that parameters can be passed to the function by value or the pointer. It worked when writing programs in C. In C ++, it is possible to pass parameters to the link function. Consider the example of this lesson, you will notice, links that use more convenient than pointers.

Reference – is an alternative name of the variable (her nickname, in other words). When the function takes a parameter by reference, the name of the parameter becomes the nickname variable, that we pass to the function. This data transfer method allows the function to work with variables, which are transmitted to it, rather than copies of these variables.

Defining a function, to point, that the parameter is a reference, it is necessary to add the name of an ampersand &.

Collect the following example, and everything should be clear:

Let's start with the function change(). Calling it in string 17 source, we pass it in the variables by value. Function safely create copies of these variables, writes the data in them and, completing his “hard” work, destroy those copies. As a result, any changes to the transferred variables will not happen.

Now look at the function definition changeRef(), in which the parameters are passed by reference – strings 45 – 49. As mentioned above, We used & , to tell the compiler that, that accepts parameters – It references. Inside the function we refer to references, as ordinary variables. That is, we do not need to apply the dereference operation, if you need to change the value of a variable:

C ++ references, ++ reference variables

And calling this function from the main (string 21), we do not need, transmission variables, apply the operation of taking the address (same & , but with a different connotation), as necessary to make the transfer by the pointer. The result of the work function see, display the values ​​of variables on the screen. The values ​​of variables successfully changed.

Finally, – transmission pointer. Directly to the definition of changePtr() – strings 51 – 55. There is something, which we did not use at the reference transmission – dereference pointers to change values of variables:

C ++ references, ++ reference variables

Since the function is to take the pointer variables, and the pointer holds the address, when calling (string 25) pass the addresses of variables in it:

C ++ references, ++ reference variables

The result of the program work:

C ++ references, ++ reference variables

I do not really want to burden you any more information about references. They are most often used is to pass parameters to a function. In the role of the parameters can act variables, arrays (it is familiar to us). But what is more important – the reference to the function objects are passed structures and classes. The time will come and we'll talk about it.

Only, It is regarding syntax, if you need to declare a reference to the program, it must be immediately initialize (to show how variable it is created). For example:

C ++ references, ++ reference variablesSo the program we can use the reference name for further access to your data, that stores aaa. This example if someone is up to you to write the code and gave the name of the variable aaa. This programmer knows, it stores the number of boxes. And you, for your convenience, gave this variable an nickname amountOfBoxes and use this new name, appending some new code in a program.

I propose to see the video of the function parameters, including where and talked about references.




Newsletter of programming:

C++ Pointers. Part 2





C ++ pointers, c ++ pointers

At the first part of the We have reviewed the, as using a pointer operator new You can allocate a piece of memory size required directly during the program operation. Just learned, as this memory can be freed, using delete. Saw how parameters are passed to a function pointer. And then, that it gives the opportunity to make changes in the value of variables, which are passed to the function.

We now look at an example where we pass to the function a pointer to a string (pointers of type char). This function returns a pointer to itself. Next task: there are two pointers to strings, under which they are allocated the necessary memory areas. It is necessary to combine these two strings. That is, it is necessary to allocate a new chunk of memory for the first string, to make it possible to add to it a second string.

Before, how to type code, that you are not “buried” errors – install the latest version of Microsoft Visual Studio environment. For example Microsoft Visual Studio 2013 Express. If you are using an earlier version, instead of functions strcat_s() apply strcat() and strcpy() instead strcpy_s().

Let's go in order. In string 4 It is a function prototype. Her task – allocate a new chunk of memory for the string, at the end of which it will write another string. This will be discussed below, when we come to the definition of this function,. Go to strings 11 – 12. They identify the variables, that will store the values ​​of the lengths of strings "string 1 " and "+ string 2". The length is calculated with the help of built-in functions strlen(). It will return the string length, excluding the symbol \0 . Therefore, when the initialization of variables strSize1 and strSize2 we add to that the return strlen(…) unit.

In string 14 defined pointer pStr1 on the first string. To write a string, you must first select it by memory: char* pStr1 = new char[strSize1]; The following copy a string in the allocated memory: strcpy_s(pStr1, strSize1, "string 1 "); . The first parameter, which receives function strcpy_s() – a pointer to the address where you want to copy a string; second – string size; the third – the string itself. The second pointer pStr2 We define exactly.

In str.. 20 – 21, Please show on screen the recorded strings. For this purpose it is enough to refer to them by name pointers. Pointer stores the address null cell. When we ask to show it on the screen – will be alternately displayed an array of characters (memory area, which was previously isolated), until it encounters an end-of-string character – \0 .

Str.. 23-24 – look how many bytes of memory takes each string. String 26 deleted a comment. It tried to add a second string to the first. Try to remove // and compile the program. Implementation of the program will abort error. You will see the following screen:

указатели на строки с++, pointers to the line c ++, new, deleteOf course – because the allocated memory area under the first string is too small, to append additional data. In string 28 write variable requiredSize really necessary memory size to record two strings: int requiredSize = (strSize1 + strSize2) - 1; Unit subtract because, variables that strSize1 and strSize2 already included two \0 , and we need only one.

Navigate to the definition of giveNewMem() – str.. 42 – 51. It will take the first string (a pointer to it) and integer (adequate memory size). Look – we need to allocate a new chunk of memory in this function for writing characters in it. So the function should return a pointer to the new memory location. So we can write in a pointer pStr1 new address, on which is located the memory to write two strings. Therefore, in the function header write so char* giveNewMem(char *pstr1, int reqSize)

So how will the new chunk of memory, then the memory, which occupies the first string should be released. If we do this right at the beginning of the function – data (characters string) disappear, because we lose the address at which they are located. Therefore, we should be in a function to request a new chunk of memory, in which we copy the characters of the first string, before you release the memory allocated for this component.

Create a new directory and immediately allocate memory for it, enough to accommodate two strings of symbols (str.. 44). Then copy the selected memory in the first string of characters: strcpy_s(strInFunc, reqSize, pstr1); The string is copied – you need to free up memory, that she was, lest there be a memory leak (str.. 48). We return from a function pointer to the new memory location: return strInFunc;

It turns out, when we call this function from main() (str.. 31) pStr1 = giveNewMem(pStr1, requiredSize); – in a pointer pStr1 written address of the new memory section, that can accommodate two strings. The only thing left to add this second string memory (str.. 33) and show it on the screen. Before exiting the program frees the memory. The first that has been allocated in the function, and then that is where the second string.

Compile program:

указатели на строки с++, pointers to the line c ++, new, delete

This example showed, as we, using pointers, can dispose of RAM with precision to the byte.

Summarize at the end and let the main, it is necessary to remember about pointers.

Why use pointers in C++?

  • using pointers, possible allocation of dynamic memory. Because memory for data is released in the course of the work program, and not at compile time. This is very beneficial, when we do not know in advance of the program will be used as actual data (variables). To allocate memory and free it, used by operators new and delete.
  • Indices are often used to access portions of the data volume of the functions. Character data and numerical arrays such as, which are defined outside the function. This approach came from the programming language C. In C ++, relative numeric variables and arrays easier to use link transmission. Soon we consider this topic. With strings in C style works best transfer by pointer.
  • using pointers – we work with the memory at the addresses directly. It's faster, than going by the name of variables.

Declaring pointers, taking addresses, dereferencing

Consider the example in detail:

In string 8 defined regular integer variable. In string 9 commented out declare and initialize the pointer. Try to remove the comment signs // and compile. We will report an error. All right. It should be a pointer to store the address (hexadecimal number), not the value (decimal number or symbol). In order for the, to get the address of a variable used by the capture operation addresses & (ampersand: Shift + 7). In string 10 create a pointer and write it the address of a variable:

инициализация указателя

To define a pointer, It is necessary to declare its type, for type an asterisk * and give it a name. Initialize the pointer can only address. If you do not assign an address pointer in its declaration, Initialize it to zero. Then this pointer will not be able to lead to complex errors, which is hard to find. He just anything will not indicate.

Usually we are not particularly interested, which stores an address pointer. We are interested in the data, located at this address. To view this data (or amend them) pointer to the name should apply the dereferencing operation. This is the same star *, as well as the declaration.

pointer dereference

Cout stream only is treated differently – not as much as in the pointer declaration. It helps to access data, stored at the address. This is shown in string 15 source.

In string 18 defined integral array five elements. Below specified pointer. Note – to initialize a pointer to the address array, operation & not applicable. This is because, that the name of the array refers to the address of the zero cell. It turns out that the record

pointer initialization

quite normally compiled. In the pointer variable pFirstArr address will be recorded zero array cell firstArr. This entry is similar to the following

pointer initialization

In string 25 shows an example of accessing data elements in the array through a pointer. Use array notation. That is, we do not need to apply the dereference operation, to access data in the array:

cout << "pfirstArr[0] = " << pFirstArr[0] << endl << endl;

Can, of course access the data array, using the notation of pointers, but it is inconvenient. Look, It looked as though assigning values to array elements and display values on screen:

Strings 27 – 28 source – definition C-strings and determination on this string pointer. Pointers are very good at working with strings. When we are in the stream cout call by name to a pointer to a character array, He will show us the entire string. As in the case of arrays, the compiler will display the characters on the screen, until it finds the end of the string in the array symbol \0

Look at the outcome of the program and the source code again. Try to understand how it works.

pointer initialization, pointer dereference, & taking addresses

Another digression, to encourage those, who is given difficult topic pointers :) You are not alone. Everything comes with practice! And it comes to you! Do not panic, if it looks too confusing for you. Solve as many as possible programming tasks. Even if you do something you do not in the process of writing code, our wonderful development environment will know about it.

Must see video about pointers (with the 12-th minute), if you haven't watched it in the first part of article:

Pointers, as parameters (arguments) function:




Newsletter of programming:

C++ Pointers. Part 1





указатели с++, указатели c++, new delete c++

Collecting information for this article, I remembered my first encounter with pointers – sadness-sadness was… Therefore, after reading a few chapters on the topic from different books about programming in C ++, it was decided to go another way and present the topic C ++ pointers in the sequence, which I consider it necessary. Immediately give you a short definition and will consider pointers in work – on examples. In the next article (C++ Pointers. Part 2) will set out the nuances of, with the use of pointers C-style strings (character arrays) and basic, what you should remember.

Pointer in C ++ – variable, that in itself stores the address data (the value of the) in memory, and not the data itself.

Having considered the following examples, you'll see the main – Why do we need programming pointers, how to declare and use.

Let's, in the program we need to create an integer array, the exact size of which is not known to us before the start of the program. That is, we do not know how many numbers the user will need to make in this array. Of course, we can insure and declare an array of several thousand items (for example on 5 000). This (in our subjective opinion) it should be enough for the user to work. Yes – really – This may be sufficient. But let's not forget, that the array will take up much space in RAM (5 000 * 4 (type int) = 20 000 bytes). We then secured themselves, and the user will fill only 10 elements of our array. It turns out, what is real 40 bytes in the work, and 19 960 byte needlessly take up memory.

The standard library function sizeof() send an announcement to the array arrWithDigits string 10. She will return to the place of call size in bytes, which takes the array in memory. On the question “How many numbers you enter into an array?” answer – 10. In string 15, expression amount * sizeof(int) would be equivalent to 10 * 4, since the function sizeof(int) return 4 (the size, in bytes, of type int). Next, enter the number from the keyboard and the program will show them on the screen. It turns out, that the remaining 4990 elements will keep the zeros. So it makes no sense to them to show.

C ++ pointers, c ++ pointers, new, delete

Home information on the screen: an array of finished 20 000 bytes, but really it is necessary to 40 bytes. How to get out of this situation? Perhaps, someone wants to rewrite the program so, the user with the keyboard input of the array, and after entering a value to declare an array with the required number of elements. But it is impossible to implement without pointers. As you remember – size of the array must be a constant. That is, an integer constant must be initialized to an array of ads and we can not ask for her input from the keyboard. Experiment – check.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

указатели с++, указатели c++, new, delete
Here we highlight red operator >> because you can not change the constant value.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

указатели с++, указатели c++, new, delete
Here we warn, that the size of the array can not be a normal variable value. Must be a constant value!

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

In the next example we will use a pointer and new operators for you new (allocate memory) and delete (frees memory).

The user enters a value from the keyboard – string 12. Below defined pointer: int* arrWithDigits This entry means, what arrWithDigits – this pointer. It is designed to store cell addresses, which will be an integer. In our case arrWithDigits will point to an array of cell index 0. Sign * – the same that is used for multiplication. In the context of the compiler “understand”, what is the declaration of a pointer, instead of multiplication. This is followed by the sign = and operator new, which allocates memory section. We remember, that our memory should be allocated for the array, and not a single number. Record new int [sizeOfArray] so you can decipher: new (Mark memory) int (to store integers) [sizeOfArray] (in an amount sizeOfArray).

Thus, in string 16 was determined dynamic array. It means, that memory is allocated for it (or does not stand out) during the program, and not at compile time, as is the case with conventional arrays. That is, memory allocation depends on the development of programs and solutions, which are taken directly to her work. In our case – depends on, that will introduce the user to the variable sizeOfArray

In string 25 apply statement delete. He frees the allocated operator new memory. So as new it allocates memory for an array of accommodation, even if its release is necessary to make it clear to the compiler, it is necessary to release the array memory, and not just the zero cell, which indicates arrWithDigits. Therefore, between delete and the name of the pointer are square brackets [] – delete [] arrWithDigits; You should remember, that every time, When memory is allocated by a new, you must release the memory using delete. Of course, at the end of program memory, occupied it, will be automatically freed. But even for you will become a good habit to use statements new and delete in pair. Because the programme can be 5-6 arrays for example. And if you will free the memory, everytime, when it is no longer required in the future in the running program – the memory will be spent more wisely.

Let's say in our program we filled the array with ten values. Next, find them, and the amount recorded in some variable. And all – the more we work with the array will no longer be. The program also continues to work, and new dynamic arrays are created in it for some purposes. In this case it is advisable to release memory, which occupies the first array. Then, when the memory allocation for the rest of this memory arrays can be used to re-program.

Consider the use of pointers, as a parameter function. For the beginning, enter and compile the following code. It receives two function variables and proposes changes in their values.

Run the program and enter the new values ​​of the variables. You will see in the end, that at the end of the function, variables have not changed and are 0.

C ++ pointers, c ++ pointers, new, delete

As you remember, function does not work directly with variables, and create their replicas. These copies are destroyed after leaving the function. That is the function received as a parameter some variable, has created its copy, has worked with it and destroyed. The very variable remains unchanged in this case.

Using pointers, we can pass variables into the function address. Then the function will be able to work directly with these variables at. Make any changes to the previous program.

In the header (string 27) and the function prototype (string 5), add operation * before the parameter names. This suggests that the, the function will receive the address of, rather than the values of the variables. When calling a function of the main() add to the names of variables transmitted operation & (ampersand – Shift + 7). & means taking the address. You remember, pointer stores the address. Therefore, we cannot pass the ordinary meaning, if the header specified, that the function takes a pointer. Using & before the variable names, function get their addresses.

The body of the function, when entering values in variables, you must use the pointer dereference. This is done using all the same operation * : cin >> *varForCh1; So we will make changes in the values ​​of the variables, and not in the address. Check the operation of the program:

C ++ pointers, c ++ pointers, new, delete

Everything worked out – variables were changed in the function.

This way of (passing parameters to the function through a pointer) widely used in programming C. In C ++, are increasingly using the transmission parameters in the link function. There is no need to use the dereference * and taking the address & variables. Therefore, use the convenient link to pass parameters. The method we'll look at in the following lessons.

Do not worry, if something is not clear. You got a lot of new information in this lesson – and it is quite normal, not all at once perceive. Understanding pointers will come with practice. We still talk about pointers in the second part of this article and we will solve the tasks. So everything will be fine.

If possible, watch the video about pointers (with the 12-th minute):

Options (arguments) function:




Newsletter of programming: