Geek Answers Handbook

Memory allocation when inserted into the card

#include <stdio.h> #include <stdlib.h> #include <memory.h> #include <vector> #include <string> #include <iostream> #include <map> #include <utility> #include <algorithm> void * GetMemory(size_t n) { void *ptr = malloc(n); printf("getMem n %d ptr 0x%x\n", n, reinterpret_cast<unsigned int> (ptr)); return ptr; } void FreeMemory(void *p) { free(p); } void* operator new (size_t n) { void *p = GetMemory(n); return p; } void* operator new [] (size_t n) { void *p = GetMemory(n); return p; } void operator delete (void *p) { FreeMemory(p); } void operator delete [] (void *p) { FreeMemory(p); } typedef std::vector<int> vec; int main(int argc, char *argv[]) { std::map<int, vec> z; vec x; z.insert(std::pair<int,vec>(1,x)); }

Compile g ++ -Wall -ansi test.cpp -o test

Run the test.

Why are there three GetMemory calls with n = 0?

+6
c ++ memory insert allocation map
source share
2 answers

Paste some trace into FreeMemory and replace main with this:

 int main(int argc, char *argv[]) { printf("map\n"); std::map<int, vec> z; printf("vec\n"); vec x; printf("pair\n"); std::pair<int,vec> y(1,x); printf("insert\n"); z.insert(y); printf("inserted 1\n"); y.first = 2; printf("insert\n"); z.insert(y); printf("inserted 2\n");

}

Output:

 $ make mapinsert CXXFLAGS=-O3 -B && ./mapinsert g++ -O3 mapinsert.cpp -o mapinsert map vec pair getMem n 0 ptr 0x6b0258 insert getMem n 0 ptr 0x6b0268 getMem n 32 ptr 0x6b0278 getMem n 0 ptr 0x6b02a0 FreeMemory ptr 0x6b0268 inserted 1 insert getMem n 0 ptr 0x6b0268 getMem n 32 ptr 0x6b02b0 getMem n 0 ptr 0x6b02d8 FreeMemory ptr 0x6b0268 inserted 2 FreeMemory ptr 0x6b0258 FreeMemory ptr 0x6b02d8 FreeMemory ptr 0x6b02b0 FreeMemory ptr 0x6b02a0 FreeMemory ptr 0x6b0278

So your 3-bit distributions:

  • One of them is copying an empty vector into a pair.
  • One of them is to save a copy of the empty vector on the map.

These two are clearly necessary. I am not sure about this:

  • One of them is to copy the vector somewhere in the call to insert , and this is also freed up in the call to insert.

As if insert (or something that it calls inside itself) takes its parameter by value instead of a link, or insert explicitly takes a copy into an automatic variable for a while before it assigns a new node map. Dismissing the debugger is an effort for me at the moment, I will leave it to someone else.

Edit: mystery solved. insert accepts a std::pair<const int, vec> , not a std::pair<int, vec> . An additional copy of the empty vector is that the pair you create must be converted to (previously) temporary, then a link to this temporary is passed to insert . std :: pair has a constructor template that lets you get away with just about anything. 20.2.2 / 4:

 template<class U, class V> pair(const pair<U,V> &p);

Effects: initializes members from the corresponding members of the argument, performing implicit conversions as needed.

I also noticed that in my implementation of vec x; does not call getMem , but vec x(0); does. So actually:

 z[1] = vec();

The code is reduced and forbids you to make an additional copy (although instead it calls operator= ). It still makes 2 0-dimensional distributions, at least for me.

The C ++ standard defines operator[] to return the result of a specified expression with an insert call. I'm not sure if this means that the effects of operator[] are called “as if” make_pair and insert were called (that is, the standard is also good as to what source should be for operator[] ), or just that the return value is the same value as the specified expression. If the latter, then perhaps the implementation can do this with a single 0-size distribution. But, of course, map does not have a guaranteed way to create a record without creating a pair containing the mapped type, so 2 distributions should be expected. Or more correctly, 2 copies of the desired mapped value: the fact that copying a vector of size 0 makes a selection of size 0 depends on the implementation.

So, if you had a case where the value was really expensive to copy, but really cheap to build by default (for example, a container with a lot of elements), then the following may be useful:

 std::map<int, vec> z; vec x(1000); z[1] = x; // ie (*(z.insert(std::pair<const int, vec>(1,vec())).first)).second = x;

makes 2 selections of size 4000 and 2 of size 0, whereas:

 std::map<int, vec> z; vec x(1000); z.insert(std::pair<const int, vec>(2, x));

makes 3 sizes 4000 and not a single size 0. In the end, the size is large enough that additional selection in the first code is cheaper than additional copying in the second code.

It is possible that the move constructors in C ++ 0x will help with this, I'm not sure.

+8
source share

All three cases associated with initializing an empty vector:

  • to initialize the root element of the tree (internal implementation of std :: map), which contains an empty vector.
  • your own initialization is 'vec x'.
  • copy constructor for std :: pair for the 'second' element, which causes the empty set of variables 'x' to be copied
+6
source share

More articles:


All Articles