Valgrind error(invalid read) operator delete(void*) when freeing objects from map

Unfortunately I'm facing this problem inside one of my classes

==4442== Invalid read of size 4
==4442==    at 0x806EC34: std::_Rb_tree_increment(std::_Rb_tree_node_base*) (in /home/blabla/projects/test proj)
==4442==    by 0x804C634: std::_Rb_tree_iterator<std::pair<std::string const, Order*> >::operator++(int) (stl_tree.h:197)
==4442==    by 0x804B98C: Play::~Play() (Play.cpp:46)
==4442==    by 0x80501AF: main (main.cpp:121)
==4442==  Address 0x421c5c4 is 12 bytes inside a block of size 24 free'd
==4442==    at 0x402B3D8: free (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==4442==    by 0x8050D4E: operator delete(void*) (in /home/blabla/projects/test proj)
==4442==    by 0x804E1E6: __gnu_cxx::new_allocator<std::_Rb_tree_node<std::pair<std::string const, Order*> > >::deallocate(std::_Rb_tree_node<std::pair<std::string const, Order*> >*, unsigned int) (new_allocator.h:110)
==4442==    by 0x804DC59: std::_Rb_tree<std::string, std::pair<std::string const, Order*>, std::_Select1st<std::pair<std::string const, Order*> >, std::less<std::string>, std::allocator<std::pair<std::string const, Order*> > >::_M_put_node(std::_Rb_tree_node<std::pair<std::string const, Order*> >*) (stl_tree.h:374)
==4442==    by 0x804D2D7: std::_Rb_tree<std::string, std::pair<std::string const, Order*>, std::_Select1st<std::pair<std::string const, Order*> >, std::less<std::string>, std::allocator<std::pair<std::string const, Order*> > >::_M_destroy_node(std::_Rb_tree_node<std::pair<std::string const, Order*> >*) (stl_tree.h:422)
==4442==    by 0x804D3BB: std::_Rb_tree<std::string, std::pair<std::string const, Order*>, std::_Select1st<std::pair<std::string const, Order*> >, std::less<std::string>, std::allocator<std::pair<std::string const, Order*> > >::_M_erase_aux(std::_Rb_tree_const_iterator<std::pair<std::string const, Order*> >) (stl_tree.h:1746)
==4442==    by 0x804CB9A: std::_Rb_tree<std::string, std::pair<std::string const, Order*>, std::_Select1st<std::pair<std::string const, Order*> >, std::less<std::string>, std::allocator<std::pair<std::string const, Order*> > >::erase[abi:cxx11](std::_Rb_tree_iterator<std::pair<std::string const, Order*> >) (stl_tree.h:820)
==4442==    by 0x804C678: std::map<std::string, Order*, std::less<std::string>, std::allocator<std::pair<std::string const, Order*> > >::erase[abi:cxx11](std::_Rb_tree_iterator<std::pair<std::string const, Order*> >) (stl_map.h:697)
==4442==    by 0x804B96F: Play::~Play() (Play.cpp:50)
==4442==    by 0x80501AF: main (main.cpp:121)
==4442== 
==4442== Invalid read of size 4
==4442==    at 0x806EC4B: std::_Rb_tree_increment(std::_Rb_tree_node_base*) (in /home/blabla/projects/test proj)
==4442==    by 0x804C634: std::_Rb_tree_iterator<std::pair<std::string const, Order*> >::operator++(int) (stl_tree.h:197)
==4442==    by 0x804B98C: Play::~Play() (Play.cpp:46)
==4442==    by 0x80501AF: main (main.cpp:121)
==4442==  Address 0x421c5bc is 4 bytes inside a block of size 24 free'd
==4442==    at 0x402B3D8: free (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==4442==    by 0x8050D4E: operator delete(void*) (in /home/blabla/projects/test proj)
==4442==    by 0x804E1E6: __gnu_cxx::new_allocator<std::_Rb_tree_node<std::pair<std::string const, Order*> > >::deallocate(std::_Rb_tree_node<std::pair<std::string const, Order*> >*, unsigned int) (new_allocator.h:110)
==4442==    by 0x804DC59: std::_Rb_tree<std::string, std::pair<std::string const, Order*>, std::_Select1st<std::pair<std::string const, Order*> >, std::less<std::string>, std::allocator<std::pair<std::string const, Order*> > >::_M_put_node(std::_Rb_tree_node<std::pair<std::string const, Order*> >*) (stl_tree.h:374)
==4442==    by 0x804D2D7: std::_Rb_tree<std::string, std::pair<std::string const, Order*>, std::_Select1st<std::pair<std::string const, Order*> >, std::less<std::string>, std::allocator<std::pair<std::string const, Order*> > >::_M_destroy_node(std::_Rb_tree_node<std::pair<std::string const, Order*> >*) (stl_tree.h:422)
==4442==    by 0x804D3BB: std::_Rb_tree<std::string, std::pair<std::string const, Order*>, std::_Select1st<std::pair<std::string const, Order*> >, std::less<std::string>, std::allocator<std::pair<std::string const, Order*> > >::_M_erase_aux(std::_Rb_tree_const_iterator<std::pair<std::string const, Order*> >) (stl_tree.h:1746)
==4442==    by 0x804CB9A: std::_Rb_tree<std::string, std::pair<std::string const, Order*>, std::_Select1st<std::pair<std::string const, Order*> >, std::less<std::string>, std::allocator<std::pair<std::string const, Order*> > >::erase[abi:cxx11](std::_Rb_tree_iterator<std::pair<std::string const, Order*> >) (stl_tree.h:820)
==4442==    by 0x804C678: std::map<std::string, Order*, std::less<std::string>, std::allocator<std::pair<std::string const, Order*> > >::erase[abi:cxx11](std::_Rb_tree_iterator<std::pair<std::string const, Order*> >) (stl_map.h:697)
==4442==    by 0x804B96F: Play::~Play() (Play.cpp:50)
==4442==    by 0x80501AF: main (main.cpp:121)
==4442== 
==4442== 
==4442== HEAP SUMMARY:
==4442==     in use at exit: 0 bytes in 0 blocks
==4442==   total heap usage: 34 allocs, 34 frees, 580 bytes allocated
==4442== 
==4442== All heap blocks were freed -- no leaks are possible
==4442== 
==4442== For counts of detected and suppressed errors, rerun with: -v
==4442== ERROR SUMMARY: 11 errors from 2 contexts (suppressed: 0 from 0)

And the place where I'm facing this problem is when freeing the allocated memory in Destructor

std::map<std::string, Order*>::iterator order_itr;
for(ord_itr = order_.begin(); ord_itr != order_.end(); ord_itr++)
{
  //if(ord_itr->second != nullptr)
    delete ord_itr->second;
  order_.erase(ord_itr);
}

From the above iterator you can see with what kind of std::map I'm dealing with. As you can see I even tried to check if it's a null pointer not to free it(what makes no sense, because all of them should get allocated)

And for the end, this is my Constructor where I allocate the memory

order_["test1"] = new Test1Order();
order_["test2"] = new Test2Order();
order_["test3"] = new Test3Order();
order_["test4"] = new Test4Order();
order_["test5"] = new Test5Order();
order_["test6"] = new Test6Order();
order_["test7"] = new Test7Order();

Thanks