User Tools

Site Tools


notes:stl_allocation_example

This is an old revision of the document!


STL Allocation Example

These small pieces of C++ code illustrate how STL structures use copy-constructors and assignment to move items into place, and how the swap() method doesn't require any copies or assignments.

std::list

stl_copy_list.cpp
#include <list>
#include <stdio.h>
 
class MyClass
{
public:
  MyClass(int id);
  MyClass(const MyClass &other);
  ~MyClass();
  MyClass& operator=(const MyClass &other);
  int getID() const { return myID; }
private:
  MyClass() { };
  int myID;
};
 
MyClass::MyClass(int id) : myID(id)
{
  printf("%p: MyClass(%d)\n", this, myID);
}
 
MyClass::MyClass(const MyClass &other) : myID(other.myID)
{
  printf("%p: MyClass(MyClass(%d))\n", this, myID);
}
 
MyClass::~MyClass()
{
  printf("%p: ~MyClass(%d)\n", this, myID);
}
 
MyClass& MyClass::operator=(const MyClass &other)
{
  myID = other.myID;
  printf("%p: MyClass = MyClass(%d)\n", this, myID);
  return *this;
}
 
int main()
{
  std::list<MyClass> one;
  std::list<MyClass> two;
 
  printf("Adding 11 to one\n");
  one.push_back(MyClass(11));
  printf("Adding 12 to one\n");
  one.push_back(MyClass(12));
  printf("Adding 21 to two\n");
  two.push_back(MyClass(21));
  printf("Adding 22 to two\n");
  two.push_back(MyClass(22));
 
  printf("Contents of one:\n");
  for (std::list<MyClass>::iterator it = one.begin(); it != one.end(); ++it) {
    printf("  %d\n", it->getID());
  }
  printf("Contents of two:\n");
  for (std::list<MyClass>::iterator it = two.begin(); it != two.end(); ++it) {
    printf("  %d\n", it->getID());
  }
 
  printf("Calling one.swap(two)\n");
  one.swap(two);
 
  printf("Contents of one:\n");
  for (std::list<MyClass>::iterator it = one.begin(); it != one.end(); ++it) {
    printf("  %d\n", it->getID());
  }
  printf("Contents of two:\n");
  for (std::list<MyClass>::iterator it = two.begin(); it != two.end(); ++it) {
    printf("  %d\n", it->getID());
  }
 
  printf("Clearing two\n");
  two.clear();
 
  printf("Exiting now\n");
  return 0;
}

Typical output

The output below demonstrates that an instance is first constructed in-place on the stack (the expression MyClass(11) does this, for example). Then, the std::list code uses placement new to copy the item into place, which results in the copy constructor being invoked (assuming that placement new itself isn't overridden). Finally, the destructor of the in-place instance on the stack is invoked.

Adding 11 to one
0x7fff02969ea0: MyClass(11)
0xed8020: MyClass(MyClass(11))
0x7fff02969ea0: ~MyClass(11)
Adding 12 to one
0x7fff02969eb0: MyClass(12)
0xed8040: MyClass(MyClass(12))
0x7fff02969eb0: ~MyClass(12)
Adding 21 to two
0x7fff02969ec0: MyClass(21)
0xed8060: MyClass(MyClass(21))
0x7fff02969ec0: ~MyClass(21)
Adding 22 to two
0x7fff02969ed0: MyClass(22)
0xed8080: MyClass(MyClass(22))
0x7fff02969ed0: ~MyClass(22)
Contents of one:
  11
  12
Contents of two:
  21
  22
Calling one.swap(two)
Contents of one:
  21
  22
Contents of two:
  11
  12
Clearing two
0xed8020: ~MyClass(11)
0xed8040: ~MyClass(12)
Exiting now
0xed8060: ~MyClass(21)
0xed8080: ~MyClass(22)

std::map

stl_copy_map.cpp
#include <map>
#include <stdio.h>
 
class MyClass
{
public:
  MyClass();
  MyClass(int id);
  MyClass(const MyClass &other);
  ~MyClass();
  MyClass& operator=(const MyClass &other);
  int getID() const { return myID; }
private:
  int myID;
};
 
MyClass::MyClass() : myID(-1)
{
  printf("%p: MyClass()\n", this);
}
 
MyClass::MyClass(int id) : myID(id)
{
  printf("%p: MyClass(%d)\n", this, myID);
}
 
MyClass::MyClass(const MyClass &other) : myID(other.myID)
{
  printf("%p: MyClass(%p: MyClass(%d))\n", this, &other, myID);
}
 
MyClass::~MyClass()
{
  printf("%p: ~MyClass(%d)\n", this, myID);
}
 
MyClass& MyClass::operator=(const MyClass &other)
{
  myID = other.myID;
  printf("%p: MyClass = %p: MyClass(%d)\n", this, &other, myID);
 
  return *this;
}
 
 
int main()
{
  std::map<int, MyClass> one;
  std::map<int, MyClass> two;
 
  printf("Adding 11 to one\n");
  one[11] = MyClass(11);
  printf("Adding 12 to one\n");
  one[12] = MyClass(12);
  printf("Adding 21 to two\n");
  two[21] = MyClass(21);
  printf("Adding 22 to two\n");
  two[22] = MyClass(22);
 
  printf("Contents of one:\n");
  for (std::map<int, MyClass>::iterator it = one.begin();
       it != one.end(); ++it) {
    printf("  %d: %d\n", it->first, it->second.getID());
  }
  printf("Contents of two:\n");
  for (std::map<int, MyClass>::iterator it = two.begin();
       it != two.end(); ++it) {
    printf("  %d: %d\n", it->first, it->second.getID());
  }
 
  printf("Calling one.swap(two)\n");
  one.swap(two);
 
  printf("Contents of one:\n");
  for (std::map<int, MyClass>::iterator it = one.begin();
       it != one.end(); ++it) {
    printf("  %d: %d\n", it->first, it->second.getID());
  }
  printf("Contents of two:\n");
  for (std::map<int, MyClass>::iterator it = two.begin();
       it != two.end(); ++it) {
    printf("  %d: %d\n", it->first, it->second.getID());
  }
 
  printf("Clearing two\n");
  two.clear();
 
  printf("Exiting now\n");
  return 0;
}

Typical Output

In contrast with the std::list example above, std::map invokes a substantial number of copy operations in the process of adding an element via assignment, as is done above.

First, an in-place instance is constructed on the stack in response to the expression MyClass(11) as was done for std::list. Next, the default constructor is called to instantiate the instance in the map on the left-hand side of the assignment, and placement new is used to copy this into the map — I'm currently not sure why there appears to be yet another additional temporary value used in the process. At this point the destructors of both temporary instances are invoked. Then the assignment operator is used to overwrite the value in the map with the in-place instance created earlier. Finally, the destructor for the in-place instance is called, as with std::list.

Adding 11 to one
0x7fff67f4ef30: MyClass(11)
0x7fff67f4ee50: MyClass()
0x7fff67f4ee44: MyClass(0x7fff67f4ee50: MyClass(-1))
0x1edb034: MyClass(0x7fff67f4ee44: MyClass(-1))
0x7fff67f4ee44: ~MyClass(-1)
0x7fff67f4ee50: ~MyClass(-1)
0x1edb034: MyClass = 0x7fff67f4ef30: MyClass(11)
0x7fff67f4ef30: ~MyClass(11)
Adding 12 to one
0x7fff67f4ef40: MyClass(12)
0x7fff67f4ee50: MyClass()
0x7fff67f4ee44: MyClass(0x7fff67f4ee50: MyClass(-1))
0x1edb064: MyClass(0x7fff67f4ee44: MyClass(-1))
0x7fff67f4ee44: ~MyClass(-1)
0x7fff67f4ee50: ~MyClass(-1)
0x1edb064: MyClass = 0x7fff67f4ef40: MyClass(12)
0x7fff67f4ef40: ~MyClass(12)
Adding 21 to two
0x7fff67f4ef50: MyClass(21)
0x7fff67f4ee50: MyClass()
0x7fff67f4ee44: MyClass(0x7fff67f4ee50: MyClass(-1))
0x1edb094: MyClass(0x7fff67f4ee44: MyClass(-1))
0x7fff67f4ee44: ~MyClass(-1)
0x7fff67f4ee50: ~MyClass(-1)
0x1edb094: MyClass = 0x7fff67f4ef50: MyClass(21)
0x7fff67f4ef50: ~MyClass(21)
Adding 22 to two
0x7fff67f4ef60: MyClass(22)
0x7fff67f4ee50: MyClass()
0x7fff67f4ee44: MyClass(0x7fff67f4ee50: MyClass(-1))
0x1edb0c4: MyClass(0x7fff67f4ee44: MyClass(-1))
0x7fff67f4ee44: ~MyClass(-1)
0x7fff67f4ee50: ~MyClass(-1)
0x1edb0c4: MyClass = 0x7fff67f4ef60: MyClass(22)
0x7fff67f4ef60: ~MyClass(22)
Contents of one:
  11: 11
  12: 12
Contents of two:
  21: 21
  22: 22
Calling one.swap(two)
Contents of one:
  21: 21
  22: 22
Contents of two:
  11: 11
  12: 12
Clearing two
0x1edb064: ~MyClass(12)
0x1edb034: ~MyClass(11)
Exiting now
0x1edb0c4: ~MyClass(22)
0x1edb094: ~MyClass(21)
notes/stl_allocation_example.1361811987.txt.gz · Last modified: 2013/02/25 17:06 by andy