std::bad_alloc error - why?

Question

Programming

Again the same program and the same classes tree:

class tree{
private:
  vector<node> nodes;
  vector<wstring> codedString;
  int fmax;
  int inode1;
  int inode2;
public:
  void extractString(wstring& str); //Разделяем строку на первичные узлы
  void construct();
  void codeString (wstring& str);
  void printCodedString();
  int getCodedStringSize();
  void printFreqTable();
  void printCodeTable();
  void codeNodes();
  void code(node& n, int level);
  void selectNode (wstring& str);
  wstring decodeString ();
  void findCode (wstring& str);
  node findNode (wstring& code);
  bool inNodes (wstring& str);
  bool inNodes (int freq);
  void getMinNode1();
  void getMinNode2();
};

and node:

class node{
private:
  int freq, child1, child2;
  wstring sym;
  wstring code;
  bool flag;
public:
  node(int fr, int ch1, int ch2, wstring s, wstring c):freq(fr),child1(ch1),child2(ch2),sym(s),code(c),flag(false){};
  int getFreq();
  int getChild1();
  int getChild2();
  wstring getCode();
  //bool getFlag();
  wstring getSym();
  void incFreq();
  void incCode(int val);
  void setCode(wstring &str);
  void toggle();
  //bool operator> (node& n);
  bool operator<= (node& n);
};

True, now the question is already devoted to other functions - functions that assign to each node a certain code consisting of 0 and 1:

void tree::codeNodes()
{
  //wcout << L"кодируются вершины" << endl;
  code(nodes[nodes.size()-1], 0);
  //wcout << L"вершины закодированы" << endl;
}

void tree::code(node& n, int level)
{
  int ch1 = n.getChild1();
  int ch2 = n.getChild2();
  wstring tmp=n.getCode();
  //wcout<<tmp<<endl;
  nodes[ch1].setCode(tmp);
  nodes[ch1].incCode(0);
  nodes[ch2].setCode(tmp);
  nodes[ch2].incCode(1);
  if (ch1!=-1&&ch2!=-1) {
    //wcout<<L"глубина "<<level<<endl;
    code (nodes[ch1], level+1);
    code (nodes[ch2], level+1);
  }
}

void node::incCode (int val)
{
  //wcout << L"добавляем к коду символ" << endl;
  wstringstream s;
  s << val;
  code += s.str();
}

void node::setCode (wstring &str){
  code += str;
}

So, small strings are successfully encoded. But on lines of greater length, the program behaves like this:

Введите строку
Говорил командир про полковника и про полковницу,про подполковника и про подполковницу, про поручика и про поручицу, про подпоручика и про подпорутчицу, про прапорщика и про прапорщицу, про подпрапорщика, а про подпрапорщицу молчал.
//...
//...
Размер строки:7424
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Where does it come from? Memory seems to be consumed not so much ...
Debugger backtrace:

#0  0x00007ffff74ab267 in __GI_raise ([email protected]=6)
    at ../sysdeps/unix/sysv/linux/raise.c:55
#1  0x00007ffff74aceca in __GI_abort () at abort.c:89
#2  0x00007ffff7ae6b7d in __gnu_cxx::__verbose_terminate_handler() ()
   from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#3  0x00007ffff7ae49c6 in ?? () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#4  0x00007ffff7ae4a11 in std::terminate() ()
   from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#5  0x00007ffff7ae4c29 in __cxa_throw ()
   from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#6  0x00007ffff7ae51cc in operator new(unsigned long) ()
   from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#7  0x00007ffff7b8a869 in std::__cxx11::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_M_mutate(unsigned long, unsigned long, wchar_t const*, unsigned long) () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#8  0x00007ffff7b8bcdb in std::__cxx11::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_M_append(wchar_t const*, unsigned long) ()
   from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#9  0x0000000000402501 in node::setCode(std::__cxx11::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >) ()
#10 0x0000000000403577 in tree::code(node&, int) ()
#11 0x000000000040366c in tree::code(node&, int) ()
#12 0x00000000004036a7 in tree::code(node&, int) ()

Answer 1

Well, I'll repeat my original answer : without the full source text, all that can be said is that the bug is most likely somewhere else. And replacing the objects with references just masked the problem for the time being.
Although I have one guess: perhaps you are building the tree incorrectly and some of its nodes are their own children.

Answer 2

If small objects are selected, but large ones are not. And while the memory is definitely not over - the most likely reason is heap fragmentation.
The easiest way to solve this problem is to always compile to x64.

Answer 3

Make sure that there is no eternal recursion that eats up all the memory. Learn the tree:code function. It can set a recursion counter, look at the value when it crashes, or simply prohibit too deep recursion.