Форум программистов, компьютерный форум CyberForum.ru

Шаблоны. Древовидная сортировка - C++

Восстановить пароль Регистрация
 
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,412
29.12.2012, 21:00     Шаблоны. Древовидная сортировка #1
Реализую собственную версию древовидной сортировки на основе шаблонов. Нужно сравнение производить по объект функции. Тип шаблона -
C++
1
std::vector<std::pair<std::string, Test *> > Test
- некий абстрактный класс.
C++
1
2
3
4
5
6
7
8
9
10
class Test
{
    public:
        Test(); // конструктор по-умолчанию
        . . .
    protected:
        int day_;
        std::string month_;
        int year_;
};
Объект-функция
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class LessDate
{
    public:
        bool operator()(const std::pair<std::string, Test *> &,
                        const std::pair<std::string, Test *> &);
};
 
bool LessDate::operator()(const pair<string, Test *> &p1,
                          const pair<string, Test *> &p2)
{
    if (p1.second->getYear() == p2.second->getYear())
    {
        if (p1.second->getMonth() == p2.second->getMonth())
            return p1.second->getDay() < p2.second->getDay();
        else
            return p1.second->getMonth() < p2.second->getMonth();
    }
    else
        return p1.second->getYear() < p2.second->getYear();
}


Содержимое файла tree_sort.h с описанием функций:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef _TREE_SORT_H_
#define _TREE_SORT_H_
 
template <typename T>
struct Tree
{
    T a;         // данные
    Tree *left;  // левый  преемник
    Tree *right; // правый преемник
};
 
template <class Tree, typename T>
Tree* add_to_tree(Tree* root, T new_value);
 
template <class Tree, typename T>
void tree_to_vec(Tree* root, std::vector<T> &);
 
template <class Tree, typename T>
void sort_tree(std::vector<T> &v);
 
#endif


tree_sort.cpp
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <vector>
#include "tree_sort.h"
 
using namespace std;
 
 
template <class Tree, typename T>
Tree* add_to_tree(Tree* root, T new_value)
{
    if (!root) // если дошли до корня - создаем новый элемент
    {
        root = new Tree;
        root->a = new_value;
        root->left = root->right = 0;
        return root;
    }
 
    if (root->a < new_value)       // добавлем ветвь
        root->right = add_to_tree(root->right, new_value);
    else
        root->left  = add_to_tree(root->left,  new_value);
    return root;
}
 
template <class Tree, typename T>
void tree_to_vec(Tree* root, vector<T> &v) // процедура заполнения массива
{
    if (!root) return; // условие окончания - найден корень
    tree_to_vec(root->left, v); // обход левого поддерева
    v.push_back(root->a);
    tree_to_vec(root->right, v); // обход правого поддерева
    delete root;
}
 
template <class Tree, typename T>
void sort_tree(vector<T> &v) // собственно сортировка
{
   Tree *root = 0;
   for (T* it = v.begin(); it != v.end(); ++it) // заполнение дерева
      root = add_to_tree(root, *it);
   tree_to_vec(root, v); // заполнение массива
}


Вызов sort_tree:
C++
1
2
3
4
typedef std::vector<std::pair<std::string, Test *> > myVec;
myVec v;
// заполнение
sort_tree<myVec::value_type>(v);
Ругается на последнюю строку.
Код
undefined reference to `void sort_tree<std::pair<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, Test*>, std::pair<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, Test*> >(std::vector<std::pair<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, Test*>, std::allocator<std::pair<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, Test*> > >&)'|
Объект-функцию я даже пока не приделывал. Как правильно передавать тип в шаблонную функцию? Или в объявлении шаблонных функций накосячил?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.12.2012, 21:00     Шаблоны. Древовидная сортировка
Посмотрите здесь:

шаблоны C++
C++ Шаблоны
Шаблоны C++
C++ Пузырьковая сортировка.Шаблоны
C++ Древовидная структура
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
29.12.2012, 21:27     Шаблоны. Древовидная сортировка #2
Шаблоны инстанцируются на этапе компиляции, поэтому подключайте и определение, и реализацию.
Avazart
 Аватар для Avazart
6899 / 5139 / 252
Регистрация: 10.12.2010
Сообщений: 22,579
Записей в блоге: 17
29.12.2012, 21:52     Шаблоны. Древовидная сортировка #3
Шаблоны должны быть в одном файле т.е весь код в h-файле
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,412
31.12.2012, 17:01  [ТС]     Шаблоны. Древовидная сортировка #4
Сейчас решил протестировать функцию отдельно, немного изменив её:
ts.h
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#ifndef _TREE_SORT_H_
#define _TREE_SORT_H_
#include <vector>
#include <iterator>
 
template <typename T>
struct Tree
{
    T a;       
    Tree* left; 
    Tree* right;
};
 
template <class Tree, typename T>
Tree* add_to_tree(Tree* root, T new_value)
{
    if (!root)
    {
        root = new Tree;
        root->a = new_value;
        root->left = root->right = 0;
        return root;
    }
 
    if (root->a < new_value)
        root->right = add_to_tree(root->right, new_value);
    else
        root->left  = add_to_tree(root->left,  new_value);
    return root;
}
 
template <class Tree, typename T>
void tree_to_vec(Tree* root, std::vector<T> &v)
{
    if (!root) return;
    tree_to_vec(root->left, v);
    v.push_back(root->a);
    tree_to_vec(root->right, v);
    delete root;
}
 
template <class Tree, class InputIterator, typename T>
Tree* add(InputIterator begin, InputIterator end)
{
    Tree* root = 0;
    for (; begin != end; ++begin)
        root = add_to_tree(root, *begin);
    return root;
}
 
template <typename T>
void tree_sort(std::vector<T> &v)
{
    tree_to_vec(add (v.begin(), v.end()), v);
}
 
#endif

main.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <vector>
#include "ts.h"
 
int main()
{
    std::vector<int> v;
    v.push_back(4); v.push_back(2);
    v.push_back(3); v.push_back(2);
    tree_sort<int>(v);
    
    for (int i=0; i < 4; i++)
        std::cout << v[i] << " ";
}
Код
54 5 D:\My works in C++\ts.h [Error] no matching function for call to 'add(std::vector<int>::iterator, std::vector<int>::iterator)'
54 5 D:\My works in C++\ts.h [Error] candidate is: 
43 49 D:\My works in C++\ts.h template<class Tree, class InputIterator, class T> Tree* add(InputIterator, InputIterator)
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
31.12.2012, 17:21     Шаблоны. Древовидная сортировка #5
Цитата Сообщение от MrGluck Посмотреть сообщение
template <class Tree, class InputIterator, typename T> Tree* add(InputIterator begin, InputIterator end)
Тут три параметра шаблона, в аргументах используется только один, он не может вывести два остальных из ничего.

Добавлено через 5 минут
Что бы вызвать add, придётся явно указывать параметры шаблона:
C++
1
add<Tree<T>, typename std::vector<T>::iterator, T>(v.begin(), v.end())
Добавлено через 1 минуту
Или поменять прототип, например на такой:
C++
1
2
template<typename InputIterator>
Tree<typename std::iterator_traits<InputIterator>::value_type> * add(InputIterator, InputIterator);
Добавлено через 10 минут
И зачем здесь
Цитата Сообщение от MrGluck Посмотреть сообщение
tree_sort<int>(v);
указывать параметр шаблона?
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,412
02.01.2013, 22:06  [ТС]     Шаблоны. Древовидная сортировка #6
Последний момент остался. С обычными типами все нормально работает, с std:air<std::string, Test *> ругается.

Класс Test
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
class Test
{
    public:
        Test(); // конструктор по-умолчанию
        Test(int, const std::string &, int ); // аргументированный конструктор
        . . .
    protected:
        int day_;
        std::string month_;
        int year_;
};

tree_sort.h
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#ifndef _TREE_SORT_H_
#define _TREE_SORT_H_
#include <vector>
#include <iterator>
 
template <typename T>
struct Tree
{
    T a;
    Tree* left;
    Tree* right;
};
 
template <class Tree, typename T, class Compare>
Tree* add_to_tree(Tree* root, T new_value, Compare comp)
{
    if (!root)
    {
        root = new Tree;
        root->a = new_value;
        root->left = root->right = 0;
        return root;
    }
 
    if (comp(root->a, new_value))
        root->right = add_to_tree(root->right, new_value, comp);
    else
        root->left  = add_to_tree(root->left,  new_value, comp);
    return root;
}
 
template <class Tree, typename T>
void tree_to_vec(Tree* root, std::vector<T> &v)
{
    if (!root) return;
    tree_to_vec(root->left, v);
    v.push_back(root->a);
    tree_to_vec(root->right, v);
    delete root;
}
 
template <class Tree, class InputIterator, class Compare>
Tree* add(InputIterator begin, InputIterator end, Compare comp)
{
    Tree* root = 0;
    for (; begin != end; ++begin)
        root = add_to_tree(root, *begin, comp);
    return root;
}
 
template <typename T, class Compare>
void tree_sort(std::vector<T> &v, Compare comp)
{
    std::vector<T> u;
    tree_to_vec(add<Tree<T>,
        typename std::vector<T>::iterator>(v.begin(), v.end(), comp), u);
    v = u;
}
 
#endif

место вызова функции сортировки:
C++
1
2
3
typedef std::vector<std::pair<std::string, Test *> > myVec;
myVec v;
tree_sort(v, LessDate());
Объект-функция LessDate
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
bool LessDate::operator()(const pair<string, Test *> &p1,
                          const pair<string, Test *> &p2)
{
    if (p1.second->getYear() == p2.second->getYear())
    {
        if (p1.second->getMonth() == p2.second->getMonth())
            return p1.second->getDay() < p2.second->getDay();
        else
            return p1.second->getMonth() < p2.second->getMonth();
    }
    else
        return p1.second->getYear() < p2.second->getYear();
}


Добавлено через 1 минуту
Текст ошибок:
Кликните здесь для просмотра всего текста
Код
)\tree_sort.h|47|  required from 'Tree* add(InputIterator, InputIterator, Compare) [with Tree = Tree<std::pair<std::basic_string<char>, Test*> >; InputIterator = __gnu_cxx::__normal_iterator<std::pair<std::basic_string<char>, Test*>*, std::vector<std::pair<std::basic_string<char>, Test*> > >; Compare = LessDate]'|
)\tree_sort.h|55|  required from 'void tree_sort(std::vector<T>&, Compare) [with T = std::pair<std::basic_string<char>, Test*>; Compare = LessDate]'|
)\Program.cpp|254|  required from here|
)\tree_sort.h|7|warning: 'Tree<std::pair<std::basic_string<char>, Test*> >::a' should be initialized in the member initialization list [-Weffc++]|
)\tree_sort.h|7|warning: 'Tree<std::pair<std::basic_string<char>, Test*> >::left' should be initialized in the member initialization list [-Weffc++]|
)\tree_sort.h|7|warning: 'Tree<std::pair<std::basic_string<char>, Test*> >::right' should be initialized in the member initialization list [-Weffc++]|
)\tree_sort.h|19|note: synthesized method 'Tree<std::pair<std::basic_string<char>, Test*> >::Tree()' first required here |
||=== Build finished: 4 errors, 3 warnings ===|
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
02.01.2013, 22:24     Шаблоны. Древовидная сортировка #7
MrGluck, сможете максимально урезать код, сохранив при этом ошибку? Поскольку, скопировав ваш код и добавив геттеры, я не получил никаких ошибок компиляции. Кстати, вы текст ошибок не привели.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,412
02.01.2013, 22:40  [ТС]     Шаблоны. Древовидная сортировка #8
soon, текст ошибок вконце.
Да и ошибки связаны с неправильным построением. Скомпилил файл tree_sort.h и оно заработало!
Хз как исправить перестройку проекта, лишний раз убеждаюсь в ненужности этих IDE.
Всё работает, спасибо за поддержку.

И с прошедшим НГ)

Добавлено через 8 минут
P.S. В CodeBloacks(minGW) построение идет с ошибками, приведенными выше, в VS без проблем.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.01.2013, 23:46     Шаблоны. Древовидная сортировка
Еще ссылки по теме:

C++ Шаблоны
Шаблоны С++ C++
C++ Шаблоны функций, сортировка массивов

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
soon
02.01.2013, 23:46     Шаблоны. Древовидная сортировка
  #9

Не по теме:

MrGluck, я видел, но под катом нет ошибок есть только отсылки к строкам, выбивающим ошибки + 3 варнинга.

Цитата Сообщение от MrGluck Посмотреть сообщение
И с прошедшим НГ)
Вас тоже с наступившим

Yandex
Объявления
02.01.2013, 23:46     Шаблоны. Древовидная сортировка
Ответ Создать тему
Опции темы

Текущее время: 16:25. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru