Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > STL vector

Автор: Dray 3.4.2005, 20:21

Есть класс

Код


class CNode
{
public:
    CNode *m_pLeft, *m_pRight;
    
    unsigned int m_Char;
    unsigned int m_CharCount;
    
    CNode()                                        //!
    {
        m_pLeft = NULL;
        m_pRight = NULL;
        m_Char = 0;
        m_CharCount = 0;
    };

    CNode (unsigned int newChar)
    {
        m_pLeft = NULL;
        m_pRight = NULL;
        m_Char = newChar;
        m_CharCount = 0;
    };

    CNode (const CNode &node)
    {
        m_pLeft     = node.m_pLeft;
        m_pRight    = node.m_pRight;
        m_Char      = node.m_Char;
        m_CharCount = node.m_CharCount;
    };

    CNode (CNode *node)
    {
        m_pLeft     = node->m_pLeft;
        m_pRight    = node->m_pRight;
        m_Char      = node->m_Char;
        m_CharCount = node->m_CharCount;
    };

    CNode (CNode *pLeft, CNode *pRight)
    {
        m_pLeft  = pLeft;
        m_pRight = pRight;
        m_Char = 256;
        m_CharCount = pLeft->m_CharCount + pRight->m_CharCount;
    };

    bool operator < (const CNode &node)
    {
        return (m_CharCount < node.m_CharCount);
    };

    bool operator == (const CNode &node)
    {
        return (m_Char == node.m_Char);
    };

    const CNode& operator = (const CNode &node)
    {
        if (&node == this)return *this;
        m_pLeft  = node.m_pLeft;
        m_pRight = node.m_pRight;
        m_Char = node.m_Char;
        m_CharCount = node.m_CharCount;
        return *this;
    };
    
};

Контейнер:

Код


class CHufTree2  
{
private:
    CNode *m_Root;
    int   m_Count;
    
    bool  m_IsTree, m_IsInit;
    vector <CNode> m_List;
.........

};

Нужно из вектора построить дерево по след. алгоритму.
- Из списка находится два элемента с наименьшим m_CharCount.
- Удаляются из списка.
- Создается новый элемент типа CNode, где m_pLeft и m_pRight эти найденные элементы.
- m_CharCount нового эл-та - сумма m_CharCount'ов двух найденных эл-в.
- Новый элемент добавляется в список.
- Следующие наименьшие один или два элемента могут быть эти новые добавленные.
- Так повторяется пока список не иссякнится.

Помогите пожалуйста. Просто проблемы возникли из-за использования вектора.

Автор: bel_nikita 3.4.2005, 23:45

Цитата

Помогите пожалуйста. Просто проблемы возникли из-за использования вектора.

А какие именно проблемы? Вектор - тот же самый массив CNode m_List[n];

Автор: Dray 4.4.2005, 21:27

Цитата(bel_nikita @ 3.4.2005, 23:45)

А какие именно проблемы?

Ну я делал так:

Код


int CHufTree2::CreateTree()
{
    if(!m_IsInit)return 1;
    CNode *buf1 = NULL;
    CNode *buf2 = NULL;
    vector <CNode>::iterator itr_min;
    while (!m_List.empty ())
    {
        itr_min = min_element(m_List.begin (), m_List.end ());
        buf1 = new CNode (itr_min);
        m_List.erase (itr_min);

        itr_min = min_element(m_List.begin (), m_List.end ());
        buf2 = new CNode (itr_min);
        m_List.erase (itr_min);

        m_Root = new CNode (buf1, buf2);
        m_List.push_back (*m_Root);
    };
    m_IsTree = true;
    return 0;
};

Однако стандартный min_element находит постоянно один и тот же элемент. Т. е. похоже, что erase его вообще не удаляет. smile

Автор: yaja 5.4.2005, 23:29

Конечно не мое дело, но по-видимому тебе надо написать сжатие Хафмана(или хотя бы его построение). С использованием спиаска ты сделаещь ето за O(n^2), а можно за O(n*log(n)). Да плюс stl, то сильно он у тебя тормозить будет...
Лучше использовать приоритетную очередь smile

Автор: DENNN 6.4.2005, 09:12

Цитата(yaja @ 5.4.2005, 23:29)

Да плюс stl, то сильно он у тебя тормозить будет...

Что-то сомневаюсь я smile

Автор: yaja 6.4.2005, 11:52

Честно говоря стоит проверить. smile

stl предоставляет большие возможности, которые вданном случае просто ни к чему smile

Проетому уже при построении дерева для unicode (2^16 символов) ужедолжна быть разница, нежели написать самому простой список, позволяющий дделать элементарные операции с ним.

Автор: Dray 6.4.2005, 16:01

Цитата(yaja @ 5.4.2005, 23:29)

по-видимому тебе надо написать сжатие Хафмана

Именно так. Это такое задание там где я учусь.

Цитата(yaja @ 6.4.2005, 11:52)

stl предоставляет большие возможности, которые вданном случае просто ни к чему

STL использовать надо. Т. к. это условие задания.

Автор: Dray 7.4.2005, 16:27

Почти разобрался. Если не

Код

while (!m_List.empty ())

Код

while(m_List.size() >=1)

То все вроде работает. И элементы разные находятся.
Но есть еще вопрос. Как сдесь правильно сделать конструктор копирования, а то, вроде два объекта не должны ссылаться на один другой. Из-за этого могут быть серьезные проблемы.
И еще, я прочитал, что в векторе, если использовать erase, то все ссылки после удаленного элемента становятся недействительнами. Если это так, то как тогда удалять из середины вектора?

Автор: Fire-Plug 13.4.2005, 20:21

Цитата(Dray @ 7.4.2005, 16:27)

что в векторе, если использовать erase, то все ссылки после удаленного элемента становятся недействительнами. Если это так, то как тогда удалять из середины вектора?

Oбрати внимание на возвращаемое значение метода vector::erase(). Это - итератор, указыв. на элемент, следующий за удаленным или же на конец вектора.
Все ссылки, полученные на основе этого итератора - корректны.
К примеру, след. фрагмент вполне работоспособен.

Код


vector <CNode>::iterator it= m_List.begin();
while(it != m_List.end ())
{
// что-то делаем юзая 'it'
   if(Some_erase_condition)
        it = m_List.erase (it); //  возвращаемый it указыв. на след. эл-т
   else
        it++;
}

Автор: Fantasist 13.4.2005, 23:16

Цитата(Dray @ 6.4.2005, 13:01)

STL использовать надо. Т. к. это условие задания.

Каким образом это сформулированно? Вообще, вектор и дерево просто разные структуры, и использовать одно для реализации другого выглядит слегка не логично.

Автор: Dray 16.4.2005, 17:03

Спасибо, Fire-Plug за ответ.

Цитата(Fantasist @ 13.4.2005, 23:16)

Каким образом это сформулированно?

Вообще, как бы, в задании это не оговорено. Просто преподаватель дал условие - чтобы был STL. Типа показать что я умею с ним работать. smile