Re[3]: Выделение памяти под структуру - C/C++

Здравствуйте, Pils, Вы писали:

P>Здравствуйте, night beast, Вы писали:
NB>>минимальный компилируемый код. который можно отдать компилятору.
NB>>может ты где память портишь по дороге.

NB>>PS: я домой, раньше чем в субботу вряд-ли посмотрю.

я тама ассертов вставил, комментов.
может чтего пропустил.
почитай, поборись с ассертами.

как резюме могу сказать: тебе сильно повезло, что валится в find_word

#include <assert.h>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct Node
{
  Node* children[8]; //< магические числа, это плохо
  int num;
  vector <pair <string, unsigned int> > words;
};

Node* create_node()
{
    Node* new_node = new Node;
    for (int i = 0; i < 8; i++)
        new_node->children[i] = NULL;
    new_node->num = 0;
    return new_node;
}

void add_node(Node* curr, int index)
{
assert( curr ); //< проверяем корректность поступивших данных. 
assert( index >= 0 && index < 8 ); //< даже если уверены что index всегда правильный.


    Node* new_node = create_node();
    curr->children[index] = new_node;
}

void walk (Node* curr)
{
assert( curr ); //< check node.

    cout << "Node with key "<<  curr->num + 2 << ",words: "; //< не понял, почему +2, ну да ладно.
    for (size_t i = 0; i < curr->words.size(); i++)
        cout << curr->words[i].first << "," << curr->words[i].second << " ";
    cout << endl;
    
    for (int i = 0; i < 8; i++) //< ты уж определись, индексы типа size_t или int.
        if (curr->children[i] != NULL)
           walk(curr->children[i]); 

}
int letter_to_int (char c)
{
    assert( c>= 97 && c<= 122 ); //< voodoo people -- magic people.
/// что будет если твоя функция вернет значение 8 или 9
    if ( ( c >= 97) && ( c <= 99))
       return 2;    
    else if ( ( c >= 100) && ( c <= 102))
       return 3;
    else if ( ( c >= 103) && ( c <= 105))
       return 4;
    else if ( ( c >= 106) && ( c <= 108))
       return 5;
    else if ( ( c >= 109) && ( c <= 111))
       return 6;
    else if ( ( c >= 112) && ( c <= 115))
       return 7;
    else if ( ( c >= 116) && ( c <= 118))
       return 8;
    else if ( ( c >= 119) && ( c <= 122))
       return 9;      

    return 2; //< на всякий случай.
}


void tree_input(Node* root, string word, unsigned int freq)
{
assert( root ); //< check node.
     Node* curr = root;
     pair <string, unsigned int> tmp;
     int key;
     size_t n; //< есть традиция объявляте переменные по мере необходимости.
     
     for (size_t i = 0; i < word.size(); i++)
     {
         key = letter_to_int(word[i]) - 2; //< ок. индекс корректируешь. норамально
         if (curr->children[key] == NULL)     
             add_node(curr, key);    
         curr = curr->children[key];
         curr->num = key; //< честно говоря, пока не совсем понятно назначение curr->num, ну да ладно.
     }    
   
     tmp.first = word;
     tmp.second = freq;     
     curr->words.push_back(tmp);     
     n = curr->words.size();
     key = 0;     
     if (n > 1)
     {
         for (size_t i = n - 2; i >= 0; i--) {//< не хотел огорчать, но size_t беззнаковый. получить значение < 0 не получится.
        assert ( i < n ); //< чтобы было понятно почему
             if (freq > curr->words[i].second) //< портишь память
                 key++;
             else
                 break;
    }
         if (key) //< не совсе понятно, что хотелось, но уже не важно.
         {
             curr->words.insert(curr->words.end() - key - 1, curr->words[n-1]);
             curr->words.erase(curr->words.end()); //< если надо удалить последний, то есть pop_back;
         }
     }
 
}

void find_word (Node* curr, string command, unsigned int fr_count) { 
    unsigned int num, freq; 
    pair <string, unsigned int> tmp;
     string t;
     
     
for (size_t i = 0; i < command.size(); i++) { 
    num = (unsigned int)command[i] - 48; //< voodoo people -- magic people.
    assert( num>=2 && num<=9 ); 
         curr = curr->children[num - 2];
     }
     
     fr_count = fr_count % curr->words.size(); //< честно говоря, не помню что будет при size == 0
     
     cout << curr->words[fr_count].first; 
         
     if (curr->words[fr_count].second < 1000)     
          curr->words[fr_count].second++;
     
     freq = curr->words[fr_count].second;
     
     num = 0;
     
     for (size_t i = fr_count - 1; i >=0; i--) { //< здесь та же проблема, что и ранее
        assert( i < fr_count ); 
             if (freq >= curr->words[i].second)
                 num++;
             else
                 break;
    }
     
     if (num)
     {
         tmp = curr->words[fr_count];
         curr->words.erase(curr->words.begin() + fr_count);
         curr->words.insert(curr->words.begin() + fr_count - num, tmp);
     }   
}

int main(int argc, char *argv[])

{
    vector < pair<string, unsigned int> > vocabulary;
 
    pair <string, unsigned int> temp;
    Node* root = create_node(); 
    // Test input
    temp.first = "ad";
    temp.second = 2;
    vocabulary.push_back(temp);
    temp.first = "be";
    temp.second = 1;
    vocabulary.push_back(temp);
    temp.first = "not";
    temp.second = 10;
    vocabulary.push_back(temp);
    temp.first = "or";
    temp.second = 5;
    vocabulary.push_back(temp);
    temp.first = "to";
    temp.second = 50;
    vocabulary.push_back(temp);
    for (size_t i = 0; i < vocabulary.size(); i++)    
        tree_input(root, vocabulary[i].first, vocabulary[i].second);
        
    walk(root);    
    find_word(root, "86", 0);    
   
    return 0;
}

Здравствуйте, K13, Вы писали:

E>>

struct Node
E>>{
E>>    std::auto_ptr<Node> children[10];
K13>// skipped
E>>}

K13>боюсь, будут проблемы при копировании такой структуры.
K13>auto_ptr идеально подходит для передачи параметров вместе с владением.
K13>в других случаях — очень опасная вещь.

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

Здравствуйте, Erop, Вы писали:

NB>>

NB>>  ~Node ();
NB>>

E>А что, думаешь узел детьми не владеет?..

хз. может в пуле освобождается. может у дитя несколько родителей.
вобщем, на усмотрение...

Будем считать, что жара совсем съела мозг, и потому я так туплю

Имеется структура следующего вида:

struct Node
{
  Node* children[10];
  vector<int> num;  
};

Как правильно написать на С++ инициализацию объекта типа Node и добавление нового элемента к существующему дереву чтобы потом не возникало проблем с памятью при добавлении неких значений в num?

P>Будем считать, что жара совсем съела мозг, и потому я так туплю

Имеется структура следующего вида:
Что-то я не понял этого вида. Почему num — вектор, а дети живут в статическом массиве? Неразумно.

P>Как правильно написать на С++ инициализацию объекта типа Node и добавление нового элемента к существующему дереву чтобы потом не возникало проблем с памятью при добавлении неких значений в num?
А что значит "правильно" и о каких проблемах ты беспокоишься?

Здравствуйте, Vamp, Вы писали:

V>А что значит "правильно" и о каких проблемах ты беспокоишься?

У меня по каким-то причинам вылетала ошибка сегментации при добавлении элемента к вектору. Структура хитрая, но для моей задачи вроде довольно удобная.

Можно даже опустить слово "правильно" и спросить просто "Как написать на С++ инициализацию объекта типа Node и добавление нового элемента к существующему дереву?"

P>Можно даже опустить слово "правильно" и спросить просто "Как написать на С++ инициализацию объекта типа Node и добавление нового элемента к существующему дереву?"

Гм, примерно вот так:

Node* node = new Node;
parent->children[index] = node;
node->num.push_back(10);

Наверное, тебе стоит раскрыть задачу.

Здравствуйте, Vamp, Вы писали:
V>Гм, примерно вот так:

V>

V>Node* node = new Node;
V>parent->children[index] = node;
node->>num.push_back(10);
V>

V>Наверное, тебе стоит раскрыть задачу.

Да, можно сделать что-то вроде

Node* create_node()
{
    Node* new_node = new Node;
    for (int i = 0; i < 10; i++)
        new_node->children[i] = NULL;
    return new_node;
}

void add_node(Node* curr, int index)
{
    Node* new_node = create_node();
    curr->children[index] = new_node;
}

А если инициализировать конструктором как все это будет выглядеть?

P>А если инициализировать конструктором как все это будет выглядеть?
Точно так же.

Здравствуйте, Pils, Вы писали:

P>Как правильно написать на С++ инициализацию объекта типа Node и добавление нового элемента к существующему дереву чтобы потом не возникало проблем с памятью при добавлении неких значений в num?

struct Node
{
    std::auto_ptr<Node> children[10];
    std:vector<int> num;

    void AddChildAt( std::auto_ptr<Node> child, int at )
    {
        assert( 0 <= at && at <= lengthof( children ) );
        children[at] = child;
    }
}

struct Node
E>{
E>    std::auto_ptr<Node> children[10];
// skipped
E>}

боюсь, будут проблемы при копировании такой структуры.
auto_ptr идеально подходит для передачи параметров вместе с владением.
в других случаях — очень опасная вещь.

Здравствуйте, Pils, Вы писали:

P>Будем считать, что жара совсем съела мозг, и потому я так туплю

Имеется структура следующего вида:

P>

P>struct Node
P>{
P>  Node* children[10];
P>  vector<int> num;  
P>};
P>

P>Как правильно написать на С++ инициализацию объекта типа Node и добавление нового элемента к существующему дереву чтобы потом не возникало проблем с памятью при добавлении неких значений в num?

template< std::size_t Capacity = 10 >
struct Node
{
  typedef std::size_t size_type;

  Node* children[Capacity];
  vector<int> num;  

  Node() : children(), num() {}
  ~Node ();

  void push_back ( Node * node ) {
     size_type i =0;
     for( ; i < Capacity; ++i ) if ( this->children[i] == 0 ) break;
     assert( i != Capacity );
     this->children[i] = node;
  }

private:
  Node ( Node const & );
  void operator = ( Node );
};

Здравствуйте, K13, Вы писали:

K13>боюсь, будут проблемы при копировании такой структуры.
K13>auto_ptr идеально подходит для передачи параметров вместе с владением.
K13>в других случаях — очень опасная вещь.

А думаешь с копированием исходной проблем не будет?

Здравствуйте, night beast, Вы писали:

NB>

NB>  ~Node ();
NB>

А что, думаешь узел детьми не владеет?..

Pils wrote:

> Как правильно написать на С++ инициализацию объекта типа Node и
> добавление нового элемента к существующему дереву чтобы потом не
> возникало проблем с памятью при добавлении неких значений в num?

Любая инициализация, вызывающая конструктор этой структуры,
будет правильной. Видимо, у тебя этого не происходило.

Posted via RSDN NNTP Server 2.1 beta

Pils wrote:
> А если инициализировать конструктором как все это будет выглядеть?

В С++ вообще-то НЕЛЬЗЯ НЕИНИЦИАЛИЗИРОВАТЬ конструктором.
Т.е. конечно же можно, но надо очень сильно постараться.

Posted via RSDN NNTP Server 2.1 beta

Вчера до описанных в теме советов так и не добрался, написал в итоге по тупому:

struct Node
{
  Node* children[10];
  vector <string>  words;  
};

Node* create_node()
{
    Node* new_node = new Node;
    for (int i = 0; i < 10; i++)
        new_node->children[i] = NULL;
    return new_node;
}

void add_node(Node* curr, int index)
{
    Node* new_node = create_node();
    curr->children[index] = new_node;
}

Далее в программе дерево указанным ниже образом заполняется, после заполнения сортируется массив, ну и затем по поступающим командам считываются нужные данные:


Node* tree_root = create_node();
…
for (;;)    
    tree_input(tree_root, input_word);

void tree_input(Node* root, string word)
{
     Node* curr = root;
      int key;  
     ...
     for (size_t i = 0; i < word.size(); i++)
     {
         key = letter_to_int(word[i]);
         
         if (curr->children[key] == NULL)
         {
             add_node(curr, key);
         }
         curr = curr->children[key];

     }
     
    curr->words.push_back(word); 
    ... 
}

Дома под wxDev-C++ все работает нормально, но для проверки я отсылаю исходник на удаленную машину, там он автоматом компилится под линукс с помощью g++ 4.3.2 и выдает sigsegv на первом же тесте (повторюсь, на домашнем компе с этими же тестами все работает как надо). Подскажите, в чем может быть проблема и как ее исправить?

Здравствуйте, Pils, Вы писали:

P>Дома под wxDev-C++ все работает нормально, но для проверки я отсылаю исходник на удаленную машину, там он автоматом компилится под линукс с помощью g++ 4.3.2 и выдает sigsegv на первом же тесте (повторюсь, на домашнем компе с этими же тестами все работает как надо). Подскажите, в чем может быть проблема и как ее исправить?

ulimit -c unlimited
./run_test #segmentation fault (core dumped)
gdb test.bin test.bin.core

ну и посмотреть в гугле команды gdb: bt, frame, print для начала.

Здравствуйте, XuMuK, Вы писали:

XMK>Здравствуйте, Pils, Вы писали:

XMK>ulimit -c unlimited
XMK>./run_test #segmentation fault (core dumped)
XMK>gdb test.bin test.bin.core

XMK>ну и посмотреть в гугле команды gdb: bt, frame, print для начала.

Вот косяк как раз в том, что линукса под рукой нет, и время на исходе.

За неимением линукса пришлось искать место возникновения проблемы тупо с помощью тестовой печати. Результаты интересные: дерево создается, все вершины и ключи на своих местах. Ошибка сегментации вылетает, когда на некотором этапе происходит вывод данных одной из вершин:

cout << curr->words[fr_count];

К этому моменту fr_count = 0; curr->words.size() = 1, нужный элемент там находится. В чем дело-то может быть

Help anyone?

Из-за чего при повторном обращении к одному и тому же элементу массива, по одному и тому же адресу, может вылезать ошибка?

Здравствуйте, Pils, Вы писали:

P>Help anyone?

P>Из-за чего при повторном обращении к одному и тому же элементу массива, по одному и тому же адресу, может вылезать ошибка?

ну ты эта, минимальный код, воспроизводящий проблему покажи.

Здравствуйте, night beast, Вы писали:

NB>ну ты эта, минимальный код, воспроизводящий проблему покажи.

После того, как дерево заполнено нужными данными, вызываем функцию поиска слова в дереве:

void find_word (Node* curr, string command, unsigned int fr_count)
{
     unsigned int num, freq;
     pair <string, unsigned int> tmp;
     
     for (size_t i = 0; i < command.size(); i++)
     {
         num = (unsigned int)command[i] - 48;
         curr = curr->children[num];
     }
     
     fr_count = fr_count % curr->words.size();

     cout << curr->words[fr_count].first; <-- Здесь вылетает ошибка  
}

К этому моменту обращаемся к элементу с индексом 0 массива размера 1, по тому же адресу, по которому обращались к этому элементу при обходе дерева, когда всё было ок.

Здравствуйте, Pils, Вы писали:

NB>>ну ты эта, минимальный код, воспроизводящий проблему покажи.

P>После того, как дерево заполнено нужными данными, вызываем функцию поиска слова в дереве:

минимальный компилируемый код. который можно отдать компилятору.
может ты где память портишь по дороге.

PS: я домой, раньше чем в субботу вряд-ли посмотрю.

Здравствуйте, night beast, Вы писали:
NB>минимальный компилируемый код. который можно отдать компилятору.
NB>может ты где память портишь по дороге.

NB>PS: я домой, раньше чем в субботу вряд-ли посмотрю.

#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct Node
{
  Node* children[8];
  int num;
  vector <pair <string, unsigned int> > words;
};

Node* create_node()
{
    Node* new_node = new Node;
    for (int i = 0; i < 8; i++)
        new_node->children[i] = NULL;
    new_node->num = 0;
    return new_node;
}

void add_node(Node* curr, int index)
{
    Node* new_node = create_node();
    curr->children[index] = new_node;
}

void walk (Node* curr)
{
    cout << "Node with key "<<  curr->num + 2 << ",words: ";   
    for (size_t i = 0; i < curr->words.size(); i++)
        cout << curr->words[i].first << "," << curr->words[i].second << " ";
    cout << endl;
    
    for (int i = 0; i < 8; i++)
        if (curr->children[i] != NULL)
           walk(curr->children[i]); 

}
int letter_to_int (char c)
{
    if ( ( c >= 97) && ( c <= 99))
       return 2;    
    else if ( ( c >= 100) && ( c <= 102))
       return 3;
    else if ( ( c >= 103) && ( c <= 105))
       return 4;
    else if ( ( c >= 106) && ( c <= 108))
       return 5;
    else if ( ( c >= 109) && ( c <= 111))
       return 6;
    else if ( ( c >= 112) && ( c <= 115))
       return 7;
    else if ( ( c >= 116) && ( c <= 118))
       return 8;
    else if ( ( c >= 119) && ( c <= 122))
       return 9;      
}


void tree_input(Node* root, string word, unsigned int freq)
{
     Node* curr = root;
     pair <string, unsigned int> tmp;
     int key;
     size_t n;  
     
     for (size_t i = 0; i < word.size(); i++)
     {
         key = letter_to_int(word[i]) - 2;    
         if (curr->children[key] == NULL)     
             add_node(curr, key);    
         curr = curr->children[key];
         curr->num = key;
     }    
   
     tmp.first = word;
     tmp.second = freq;     
     curr->words.push_back(tmp);     
     n = curr->words.size();
     key = 0;     
     if (n > 1)
     {
         for (size_t i = n - 2; i >= 0; i--)
             if (freq > curr->words[i].second)
                 key++;
             else
                 break;
         if (key)
         {
             curr->words.insert(curr->words.end() - key - 1, curr->words[n-1]);
             curr->words.erase(curr->words.end());
         }
     }
 
}

void find_word (Node* curr, string command, unsigned int fr_count)
{
     unsigned int num, freq;
     pair <string, unsigned int> tmp;
     string t;
     
     for (size_t i = 0; i < command.size(); i++)
     {
         num = (unsigned int)command[i] - 48;
         curr = curr->children[num - 2];
     }
     
     fr_count = fr_count % curr->words.size(); 
     
     cout << curr->words[fr_count].first; 
         
     if (curr->words[fr_count].second < 1000)     
          curr->words[fr_count].second++;
     
     freq = curr->words[fr_count].second;
     
     num = 0;
     
     for (size_t i = fr_count - 1; i >=0; i--)
             if (freq >= curr->words[i].second)
                 num++;
             else
                 break;
     
     if (num)
     {
         tmp = curr->words[fr_count];
         curr->words.erase(curr->words.begin() + fr_count);
         curr->words.insert(curr->words.begin() + fr_count - num, tmp);
     }   
}

int main(int argc, char *argv[])

{
    vector < pair<string, unsigned int> > vocabulary;
 
    pair <string, unsigned int> temp;
    Node* root = create_node(); 
    // Test input
    temp.first = "ad";
    temp.second = 2;
    vocabulary.push_back(temp);
    temp.first = "be";
    temp.second = 1;
    vocabulary.push_back(temp);
    temp.first = "not";
    temp.second = 10;
    vocabulary.push_back(temp);
    temp.first = "or";
    temp.second = 5;
    vocabulary.push_back(temp);
    temp.first = "to";
    temp.second = 50;
    vocabulary.push_back(temp);
    for (size_t i = 0; i < vocabulary.size(); i++)    
        tree_input(root, vocabulary[i].first, vocabulary[i].second);
        
    walk(root);    
    find_word(root, "86", 0);    
   
    return 0;
}

Здравствуйте, Pils, Вы писали:

P>void tree_input(Node* root, string word, unsigned int freq)
P>{
[…]
             curr->>words.erase(curr->words.end());

Так нельзя делать. end() — это за концом контейнера, его нельзя erase.

Здравствуйте, Centaur, Вы писали:

C>Здравствуйте, Pils, Вы писали:

C>

P>>void tree_input(Node* root, string word, unsigned int freq)
P>>{
C>[…]
             curr->>>words.erase(curr->words.end());
C>

C>Так нельзя делать. end() — это за концом контейнера, его нельзя erase.

Хм, да, действительно. Исправил, но дело было не в этом.

Здравствуйте, Pils, Вы писали:

http://codepad.org/22Hykk91

1. read the warnings

Здравствуйте, Pils, Вы писали:

P>

P>void find_word (Node* curr, string command, unsigned int fr_count)
P>{

     ...

P>     if (num)
P>     {
P>         tmp = curr->words[fr_count];
         curr->>words.erase(curr->words.begin() + fr_count);
         curr->>words.insert(
                             curr->words.begin() + fr_count - num  /// Ошибка тут: begin() + 0 - 1
                             , tmp);
P>     }   
P>}
P>

В данном конкретном случае ошибка в указанном месте: ты пытаешься передать в функцию вставки итератор begin()-1
Поведение, очевидно, зависит от реализации

vector::iterator
typedef T0 iterator;

The type describes an object that can serve as a random-access iterator for the controlled sequence. It is described here as a synonym for the implementation-defined type T0.

Ну и, как уже сказали выше, тебе вообще повезло, что программа доходит до этой точки

	От:	night beast
	Дата:	07.08.10 08:59
	Оценка:	1 (1) +1

	От:	night beast
	Дата:	04.08.10 04:37
	Оценка:	+1

	От:	night beast
	Дата:	04.08.10 06:22
	Оценка:	+1

	От:	Pils
	Дата:	03.08.10 17:21
	Оценка:

	От:	Vamp
	Дата:	03.08.10 17:24
	Оценка:

От:	K13	http://akvis.com
Дата:	04.08.10 04:32
Оценка:

От:	Caracrist	https://1pwd.org/
Дата:	08.08.10 05:46
Оценка:

	От:	Centaur
	Дата:	06.08.10 18:39
	Оценка:

	От:	GarikTot
	Дата:	09.08.10 12:42
	Оценка: