Есть класс

Код

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'ов двух найденных эл-в.
- Новый элемент добавляется в список.
- Следующие наименьшие один или два элемента могут быть эти новые добавленные.
- Так повторяется пока список не иссякнится.

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

Цитата

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

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

Цитата(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 его вообще не удаляет.

Это сообщение отредактировал(а) Dray - 7.4.2005, 16:09

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

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

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

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

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

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

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

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

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

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

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

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

Код

while (!m_List.empty ())

а

Код

while(m_List.size() >=1)

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

Цитата(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++; }

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

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

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

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

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

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

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