-5

I'm using C++ to implement FP-growth algorithm, but I get some errors when using vector. Here is my code:

typedef struct Node
{
    FPData *fpData;
    int childCount;
    struct Node *parent;
    vector<Node*> childs;
}FPNode;

FPNode* FPTree::NewNode(string data, int support)
{
    FPNode *node = (FPNode*) malloc(sizeof(FPNode));
    FPData *fpData = (FPData*) malloc(sizeof(FPData));
    fpData -> data = data;
    fpData -> support = support;
    node -> fpData = fpData;
    node -> childCount = 0;
    node -> parent = NULL;
    return node;
}
void FPTree::InsertFPPath(FPNode* root, list<FPData*> fpDatas)
{
    if(fpDatas.size() <= 0)
    {
        return;
    }
    bool flag = true;
    for(int i = 0; i < root -> childCount; i++)
    {
        FPNode* child = root -> childs[i];
        if(child -> fpData -> data == fpDatas.front() -> data)
        {
           flag = false;
           child -> fpData -> support ++;
           fpDatas.pop_front();
           InsertFPPath(child, fpDatas);
           break;
        }
    }
    if(flag)
    {
        FPData* firstData = fpDatas.front();
        FPNode* newChild = NewNode(firstData -> data, firstData -> support);
        root -> childs.push_back(newChild);   // error at here
        root -> childCount ++;
        fpDatas.pop_front();
        for(int i = 0; i < fpDatas.size(); i++)
        {

            InsertFPPath(newChild, fpDatas);
        }
     }
}

The InsertFPPath() is a recursive method, I get error when second iterate:

root -> childs.push_back(newChild)

The error comes at:

 construct(_Up* __p, _Args&&... __args)  // here the __p is null, and __args is right
 {
      ::new((void*)__p) _Up(_VSTD::forward<_Args>(__args)...);
 }

And the thread Queue stop at:

#0  0x00000001000050cf in void std::__1::allocator::construct(Node**, Node* const&&&) [inlined] at /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/memory:1673

the backtrace is :

#0  0x00000001000050cf in void std::__1::allocator::construct(Node**, Node* const&&&) [inlined] at /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/memory:1673
#1  0x00000001000050bc in void std::__1::allocator_traits >::__construct(std::__1::integral_constant, std::__1::allocator&, Node**, Node* const&&&) [inlined] at /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/memory:1600
#2  0x000000010000509c in void std::__1::allocator_traits >::construct(std::__1::allocator&, Node**, Node* const&&&) [inlined] at /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/memory:1453
#3  0x0000000100005079 in std::__1::vector >::push_back(Node* const&) [inlined] at /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/vector:1590
#4  0x0000000100004fa9 in FPTree::InsertFPPath(Node*, std::__1::list >) at /Users/dorothy/ME/USTC/作业/数据挖掘/experiment/FPTree/FPTree/FPTree.cpp:129
#5  0x00000001000051b4 in FPTree::InsertFPPath(Node*, std::__1::list >) at /Users/dorothy/ME/USTC/作业/数据挖掘/experiment/FPTree/FPTree/FPTree.cpp:135**
17
  • 6
    What error? Please be specific.
    – ajshort
    Dec 15, 2015 at 7:15
  • 2
    Why do you keep track of childCount while you can get the size() of childs? Also, when iterating over an std::vector you should use iterators, instead of indexed access.
    – tillaert
    Dec 15, 2015 at 7:18
  • 1
    If you're programming C++, why are you using typedef for a structure? A structure is basically the same as a class, so the structure name can be used as a type. Dec 15, 2015 at 7:25
  • 1
    Also, the line you say give you the error doesn't exist in the code you show, and it doesn't match the structure you show either. And please show us the actual error! Copy the complete build-log and paste it in the question as text, then tell us where in your code the errors is, for example by adding a comment in the code you show. Dec 15, 2015 at 7:27
  • 1
    Now to the big question: What is the value of root and where does it point when the crash happens? Dec 15, 2015 at 9:10

1 Answer 1

0

When you allocate memory for structures (struct or class) containing constructors, or for structures containing objects that have constructors, then you can't allocate the memory using malloc. The malloc function only allocates memory, but it doesn't call the constructors, and in your case that means that the childs member object will not be constructed and using the vector will lead to undefined behavior.

When allocating memory dynamically in C++ you need to use the new operator:

FPNode *node = new FPNode;
FPData *fpData = new FPData;
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.