data structures – Supercharged Computing

This post explains sizes of different data types, structures and classes under various circumstances.

#include <iostream>
#include <atomic>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <forward_list>
#include <memory>
// An empty class without any data members
class EmptyClass{};

// class with member variable int
class X{
  int a;
};

// class with member variable int and double
class Y{
  int a;
  double b;
};

// class with static variable int
class StaticMember{
  static int a;
};

// packed structure
class __attribute__((packed)) YPacked{
int a;
double b;
};

// packed large structure
class __attribute__((packed)) LargeStruct {
int a;
double b;
float c;
char d;
double l;
double m;
int n;
int o;
double p;
double q;
double t;
double u;
double v;
double w;
char s;
double x;
float y;
int z;
};

// class with a single virtual function
class VFunClass{
  public:
    virtual void fun(){std::cout << "class with virtual function\n";};
};

// class with a virtual destructor.
class VDesttructorClass{
  public:
    virtual ~VDesttructorClass(){
      std::cout << "in the virtual destructor\n";
    }
};

// Multi level class hierarchy
class Base{};

class Derived: public Base{

};

class Derived1: public Base{
};

class Derived2: public Base{
};

class MostDerived: public Derived, public Derived1, public Derived2{};

class VBase{};

class VDerieved: public virtual VBase{

};

class VDerieved1: public virtual VBase{
};


class VMostDerieved: public VDerieved, public VDerieved1{

};

int main(){
  std::string s = "test string";
  std::cout << "sizeof(s) "<< sizeof(s) << '\n'; // 24
  std::cout << "s.size() " << s.size() << '\n'; // 11


  std::vector<int> v{1,2,3,4,5};
  std::cout << "sizeof(v) "<< sizeof(v) << '\n'; // 24
  std::cout << "v.size() " << v.size() << '\n'; // 5

  std::set<int> set{1,2,3,4,5};
  std::cout << "sizeof(set) "<< sizeof(set) << '\n'; // 24
  std::cout << "set.size() " << set.size() << '\n'; // 5

  std::queue<int> queue;
  for(int i = 0; i < 5; ++i) queue.push(i);
  std::cout << "sizeof(queue) "<< sizeof(queue) << '\n'; // 48
  std::cout << "queue.size() " << queue.size() << '\n'; // 5

  std::forward_list<int> fl;
  auto it = fl.before_begin();
  it = fl.emplace_after ( it, 100 );
  it = fl.emplace_after ( it, 200 );
  it = fl.emplace_after ( it, 300 );
  std::cout << "sizeof(fl) "<< sizeof(fl) << '\n'; // 8

// Size of X is 4 because there is a single data member in the class/struct
  std::cout << "sizeof(X) "<< sizeof(X) << '\n'; // 4

// Size of Y should be 12 i.e. addition of int (4) + double (8)= 12
// but its size if 16 because the compiler aligns the class/struct
// by multiples of its max member.
  std::cout << "sizeof(Y) "<< sizeof(Y) << '\n'; // 16

// Size of a packed structure = sum of sizes of member variables
  std::cout << "sizeof(YPacked) "<< sizeof(YPacked) << '\n'; // 12

  std::unique_ptr<int> uniq_ptr = std::make_unique<int>(10);
  std::cout << "sizeof(uniq_ptr) " << sizeof(uniq_ptr) << '\n'; // 8

  std::shared_ptr<int> sh_ptr = std::make_shared<int>(10);
  std::cout << "sizeof(sh_ptr) " << sizeof(sh_ptr) << '\n'; // 16

  std::weak_ptr<int> w_ptr = std::make_shared<int>(10);
  std::cout << "sizeof(w_ptr) " << sizeof(w_ptr) << '\n'; // 16

  std::cout << "sizeof(EmptyClass) "<< sizeof(EmptyClass) << '\n'; // 1 
  std::cout << "sizeof(VFunClass) " << sizeof(VFunClass) << '\n'; // 8
  std::cout << "sizeof(VDesttructorClass) " << sizeof(VDesttructorClass) << '\n'; // 8

// Size of most Derived class in the hierarchy with 3 NON virtual 
// Base classes has 2 * 1 bype per class Hence the size if 3
  std::cout << "sizeof(MostDerived) " << sizeof(MostDerived) << '\n'; // 3

// Size of most Derived class in the hierarchy with 2 virtual Base classes
// has 2 * 8 bype (v_ptr). Hence the size if 16.
std::cout << "sizeof(VMostDerived) " << sizeof(VMostDerived) << '\n'; // 16

// Size of class with only static variable is 1 i.e.
// it does not include size of static in the size of class.
  std::cout << "sizeof(StaticMember) " << sizeof(StaticMember) << '\n'; // 1

  std::atomic<int> i = 10;
  std::cout << "sizeof(std::atomic<int>) " << sizeof(i) << '\n'; // 4

//size of packed atomic structure is 16
  std::atomic<double> d;
  std::cout << "sizeof(std::atomic<double>) " << sizeof(std::atomic<double>) << '\n'; // 16

//size of packed atomic structure is 16
  std::atomic<YPacked> yp;
  std::cout << "sizeof(std::atomic<YPacked>) " << sizeof(std::atomic<YPacked>) << '\n'; // 16
}

CRTP a.k.a. Static Polymorphism

The size of CRTP class is 1 compared to 8 in virtual function/class.

template <typename T>
class Logger{
  public:
    void log(){
      static_cast<T*>(this)->log();
    }
};

class FileLogger: public Logger<FileLogger>{
  public:
    void log(){
      std::cout << "In the class FileLogger\n";
    }
};

int main(){
  std::cout << sizeof(FileLogger) << '\n'; // Size is 1
  FileLogger fl;
  r43fl.log();
}

Iteration:

Iteration is very basic and important operation of any container type like std::vector, std::deque or std::list.

std::queue<int> q;
for(int i = 0; i <= 10; i++){
  q.push(i);
}
for(int i = 0; i <= 10; i++){
  std::cout << q.pop() << '\n';
}

Shuffle Queue:

Shuffling with extra space (using another deque)can be done as follows:

#include <iostream>
#include <queue>
#include <algorithm>
#include <random>
#include <deque>

int main(){
  std::queue<int> q;
  for(int i = 0; i <= 10; i++){
    q.push(i);
  }
 
 std::deque<int> d;
 for(int i = 0; i <= 10; i++){
  d.push_back(q.pop());
 }

  unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
  std::shuffle (d.begin(), d.end(), std::default_random_engine(seed));


  std::queue<int> empty;
  std::swap(q, empty);

  std::for_each(d.begin(), d.end(), [&q](const auto & i){q.push(i);});
  std::for_each(d.begin(), d.end(), [&q](const auto & i){std::cout << i << '\n';});
  
  for((int i = 0; i <= 10; i++){
   std::cout << q.pop() << '\n';
  }
  
}

Category: data structures

Sizes of data types in c++

std::queue operations

Iteration:

Shuffle Queue: