Не получается сделать шаблонную функцию

@SwetGen · Регистрация: 01.02.2018

Студворк — интернет-сервис помощи студентам

Всем привет.
Мне нужно сделать общую функцию для int и string.
Она должна принимать на вход два параметра: массив вектор и размер массива, только так, чтобы элементы массива можно было менять местами(т.е. надо ссылку или указатель использовать).

Должно получится что-то подобное:

C++
1
2
3
4
void insertSortStringI(type &a, int size)     // будет подставляться либо std::vector <std::string>, либо std::vector <int>
{
// код
}

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

@hoggy · 01.02.2018, 19:32

Сообщение от SwetGen

Должно получится что-то подобное:
void insertSortStringI(type &a, int size) // будет подставляться либо std::vector <std::string>, либо std::vector <int>
{
// код
}

http://rextester.com/ACMUG21323

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
#include <iostream>
 
#include <type_traits>
#include <cstddef>
#include <cassert>
#include <vector>
#include <string>
 
// будет подставляться либо std::vector <std::string>, 
// либо std::vector <int>
template<class T>
void insertSortStringI(::std::vector<T>& vec, const size_t size) 
{
    using vec_t = ::std::vector<T>;
    using elem_t = typename vec_t::value_type;
    enum { valid_str = ::std::is_same<elem_t, ::std::string>::value };
    enum { valid_int = ::std::is_same<elem_t, int          >::value };
    enum { valid = valid_str || valid_int };
    static_assert(
        valid, 
        "[ERROR] expect std::vector<std::string> or std::vector<int>"
    );
    
    assert(size<=vec.size() && "invalid size");
    std::cout <<"all rights!\n";
}
 
int main()
{
    ::std::vector<int> v1 {1,2,3,4,5,6};
    ::std::vector<::std::string> v2 {"1","2","3","4","5","6"};
    insertSortStringI(v1, 0);
    insertSortStringI(v2, 0);
}

@outoftime · 01.02.2018, 20:19

hoggy, ::std это типа "абсолютный путь" что-ли?

@hoggy · 01.02.2018, 20:29

Сообщение от outoftime

::std это типа "абсолютный путь" что-ли?

типа да.

1.
помогает компилятору быстрее находить имена символов,
что ускоряет компиляцию.
и дает профит к лучшей диагностике возможных проблем.
(на это можно забить)

2.
помогает IDE лучше находить имена символов под курсором.
(а вот это круто. +100500 к навигации по коду)

@SwetGen · 01.02.2018, 21:56 **[ТС]**

Спасибо, очень помогли. Код сократился вдвое.
Правда всё равно полотно какое-то получилось, но может кому пригодится.
Еще поэкспериментирую с его размером.

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <fstream>
#include <String>
 
std::string s = "-s"; // string
std::string i = "-i"; // int
std::string a = "-a"; // по возрастанию
std::string d = "-d"; // по убыванию
 
template<class T>
void insertSortI(std::vector<T> &arr, size_t size) // Сортировка вставками по возрастанию insertSortIncrease
{
    T tmp;
    for (int i = 1, j; i < size; ++i)
    {
        tmp = arr[i];
        for (j = i - 1; j >= 0 && arr[j] > tmp; --j)
            arr[j + 1] = arr[j];
        arr[j + 1] = tmp;
    }
}
 
template<class T>
void insertSortD(std::vector<T> &arr, size_t size) // Сортировка вставками по убыванию insertSortDecrease
{
    T tmp;
    for (int i = 1, j; i < size; ++i)
    {
        tmp = arr[i];
        for (j = i - 1; j >= 0 && arr[j] < tmp; --j)
            arr[j + 1] = arr[j];
        arr[j + 1] = tmp;
    }
}
 
template<class T>
void FullArray(T type, std::string ad, std::ifstream &input_file, std::ofstream &output_file)
{
    if (type == s) {
        std::vector<std::string> arr;
        std::string var;
        while (input_file >> var) {
            arr.push_back(var);
        }
        int size = arr.size();
        if (ad == a) {
            insertSortI(arr, size);
        }
        if (ad == d) {
            insertSortD(arr, size);
        }
        for (int i = 0; i < size; i++) {
            output_file << arr[i] << std::endl;  // Записывает элементы массива в выходной файл
        }
        std::cout << "Elements successfully sorted." << std::endl;
    }
    else if (type == i) {
        std::vector<int> arr;
        int var;
        while (input_file >> var) {
            arr.push_back(var);
        }
        int size = arr.size();
        if (ad == a) {
            insertSortI(arr, size);
        }
        if (ad == d) {
            insertSortD(arr, size);
        }
        for (int i = 0; i < size; i++) {
            output_file << arr[i] << std::endl;
        }
        std::cout << "Elements successfully sorted." << std::endl;
    }
}
 
int main(int argc, char* argv[])
{
        std::string file_vh;
        std::string file_vyh;
        std::string type;
        std::string sort;
        std::cout << "Please enter:";
        std::cout << "1) the path to the input file " << "2) the path to the output file " << "3) the element type " << "4) sorting order:" << std::endl;
        std::cin >> file_vh >> file_vyh >> type >> sort; 
        // Например D:\in2.txt D:\out2.txt -s -a
        std::ifstream input_file(file_vh); // Входной файл
        std::ofstream output_file(file_vyh); // Выходной файл
 
        if ((type == s || type == i) && sort == a) { // По возрастанию 
            if (type == s) {
                FullArray(s, sort, input_file, output_file);
            }
            else {
                FullArray(i, sort, input_file, output_file);
            }
        }
        if ((type == s || type == i) && sort == d) { // По убыванию 
            if (type == s) {
                FullArray(s, sort, input_file, output_file);
            }
            else {
                FullArray(i, sort, input_file, output_file);
            }
        }
 
    return 0;
}

@hoggy · 01.02.2018, 22:08

Сообщение от SwetGen

void insertSortI(std::vector<T> &arr, size_t size)

Сообщение от SwetGen

int size = arr.size();
* * * * if (ad == a) {
* * * * * * insertSortI(arr, size);

бред.

или назовите хотя б одну причину,
зачем вы передаете размер контейнера вторым параметром?

@outoftime · 01.02.2018, 23:43

SwetGen, hoggy, что скажете?

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <algorithm>
#include <iterator>
#include <functional>
 
const ::std::string s = "-s"; // string
const ::std::string i = "-i"; // int
const ::std::string a = "-a"; // по возрастанию
const ::std::string d = "-d"; // по убыванию
 
template <class ValueType, class Comparator = ::std::less<ValueType>>
void insertSort(::std::vector<ValueType> &arr, Comparator comp = Comparator())
{
    for (int i = 1, j; i < arr.size(); ++i)
    {
        ValueType *tmp = &arr[i];
        for (j = i - 1; j >= 0 && comp(arr[j], *tmp); --j)
            arr[j + 1] = arr[j];
        arr[j + 1] = *tmp;
    }
}
 
template <typename ValueType, class Comparator = ::std::less<ValueType>>
void sort_file(::std::ifstream &input_file, ::std::ofstream &output_file,
               Comparator comp = Comparator())
{
    ::std::vector<ValueType> arr;
    ::std::copy(::std::istream_iterator<ValueType>{::std::cin},
                ::std::istream_iterator<ValueType>{},
                ::std::back_inserter(arr));
    ::insertSort(arr, comp);
    ::std::copy(arr.begin(), arr.end(),
                ::std::ostream_iterator<ValueType>(output_file, "\n"));
    ::std::cout << "Elements successfully sorted." << std::endl;
}
 
template <typename ValueType>
void sort_file(const ::std::string &sort, ::std::ifstream &input_file,
               ::std::ofstream &output_file)
{
    ::std::function<bool(ValueType, ValueType)> comp = ::std::less<ValueType>();
    if (sort == a)
        comp = ::std::greater<ValueType>();
    ::sort_file<ValueType>(input_file, output_file, comp);
}
 
void sort_file(const ::std::string &type, const ::std::string &sort,
               ::std::ifstream &input_file, ::std::ofstream &output_file)
{
    if (type == s)
        ::sort_file<::std::string>(sort, input_file, output_file);
    if (type == i)
        ::sort_file<int>(sort, input_file, output_file);
}
 
int main(int argc, char *argv[])
{
    std::string file_vh;
    std::string file_vyh;
    std::string type;
    std::string sort;
    std::cout << "Please enter:";
    std::cout << "1) the path to the input file "
              << "2) the path to the output file "
              << "3) the element type "
              << "4) sorting order:" << std::endl;
    std::cin >> file_vh >> file_vyh >> type >> sort;
    // Например D:\in2.txt D:\out2.txt -s -a
    std::ifstream input_file(file_vh);   // Входной файл
    std::ofstream output_file(file_vyh); // Выходной файл
 
    ::sort_file(type, sort, input_file, output_file);
}

@AndrSlav · 02.02.2018, 00:02

Сообщение от hoggy

assert(size<=vec.size() && "invalid size");

Это опечатка, или я не понимаю?

@hoggy · 02.02.2018, 00:43

Сообщение от outoftime

что скажете?

C++
1
2
3
4
5
6
7
8
9
10
11
template <class ValueType, class Comparator = ::std::less<ValueType>>
void insertSort(::std::vector<ValueType> &arr, Comparator comp = Comparator())
{
    for (int i = 1, j; i < arr.size(); ++i) 
    {
        ValueType *tmp = &arr[i];
        for (j = i - 1; j >= 0 && comp(arr[j], *tmp); --j)
            arr[j + 1] = arr[j];
        arr[j + 1] = *tmp;
    }
}

1.
почему у вас индекс элемента контейнера имеет знаковый тип?

2.
почему вы так просто знаковый тип подсовываете в аргументы там,
где ожидаются беззнаковые?

Code
1
conversion to ‘std::vector<int>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]

3.
почему вы вот так просто сравнивание знаковые
и беззнаковые величины?

Code
1
warning: comparison between signed and unsigned integer expressions [-Wsign-compare]

4.
почему на каждой итерации вы каждый раз снова
рассчитываете размер коллекции?
он же у вас не изменяется.

5.
ValueType *tmp = &arr[i];
из каких соображений вы решили использовать именно указатель?

6.
почему компаратор передается по значению, а не по ссылке?

7.
если ваша функция в принципе не кидает исключений,
почему тогда отсутствует спецификатор noexcept ?

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

Добавлено через 25 секунд

Сообщение от AndrSlav

Это опечатка, или я не понимаю?

или не понимаете.

что вас смутило?

@AndrSlav · 02.02.2018, 01:12

Сообщение от hoggy

size<=vec.size()

Это понятно

Сообщение от hoggy

"invalid size"

Это условие ведь ни на что не влияет - это указатель и он всегда будет расцениваться как true?

@outoftime · 02.02.2018, 01:33

Сообщение от hoggy

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

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

Сообщение от hoggy

если ваша функция в принципе не кидает исключений,
почему тогда отсутствует спецификатор noexcept ?

Вот только узнал что он есть.

@hoggy · 02.02.2018, 02:13

Сообщение от AndrSlav

Это условие ведь ни на что не влияет

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

Code
1
Assertion `size<=vec.size() && "invalid size"' failed.

Сообщение от outoftime

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

вы не поняли вопроса:

Сообщение от hoggy

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

почему именно указатель, а не ссылка?

вы что, допускаете ситуацию,
что tmp может и не быть валидным
на протяжении выполнения алгоритма?

или что tmp может ссылаться на разные объекты
за период времени жизни?

@outoftime · 02.02.2018, 03:06

Сообщение от hoggy

почему именно указатель, а не ссылка?

А я и не знал что так можно

C++
1
2
3
4
5
6
    int a = 1;
    int &b = a;
    a = 2;
    ::std::cout << b << ::std::endl;
    b = 3;
    ::std::cout << a << ::std::endl;

Выводит 2 и 3.

@AndrSlav · 02.02.2018, 10:02

C++
1
2
3
4
5
6
7
8
9
10
void insertSort(::std::vector<ValueType> &arr, Comparator comp = Comparator())
{
    for (int i = 1, j; i < arr.size(); ++i)
    {
        ValueType *tmp = &arr[i];
        for (j = i - 1; j >= 0 && comp(arr[j], *tmp); --j)
            arr[j + 1] = arr[j];
        arr[j + 1] = *tmp;
    }
}

Так ведь не работает так.
У SwetGen правильный алгоритм.

@SwetGen · 02.02.2018, 11:26 **[ТС]**

Добавлено через 2 минуты

бред.

или назовите хотя б одну причину,
зачем вы передаете размер контейнера вторым параметром?

Да, он там не нужен.

@outoftime · 02.02.2018, 12:51

AndrSlav, действительно. Там жесткий прикол с беззнаковыми типами. SwetGen, hoggy, Переделал на итераторы.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class ValueType, class Comparator = ::std::less<ValueType>>
void insertSort(::std::vector<ValueType> &arr, Comparator comp = Comparator()) noexcept
{
    typedef typename ::std::vector<ValueType>::iterator Iterator;
    const Iterator _begin{arr.begin()}, _end{arr.end()};
    for (Iterator i{_begin + 1}, j; i != _end; ++i)
    {
        ValueType tmp = *i;
        for (j = i - 1; comp(*j, tmp); )
        {
            *(j + 1) = *j;
            if (j-- == _begin) break;
        }
        *(j + 1) = tmp;
    }
}

@hoggy · 02.02.2018, 13:08

Сообщение от outoftime

ValueType tmp = *i;

C++
1
ValueType& tmp = *i;

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class ValueType, class Comparator = ::std::less<ValueType>>
void insertSort(::std::vector<ValueType> &arr, Comparator comp = Comparator()) noexcept
{
    const auto beg = arr.begin();
    for(auto i = beg + 1, end = arr.cend(); i != end; ++i)
    {
        ValueType& tmp = *i;
        auto j = i - 1;
        while(comp(*j, tmp))
        {
            *(j + 1) = *j;
            if (j-- == beg) 
                break;
        }
        *(j + 1) = tmp;
    }
}

мне не нравится.
на итераторах как то закорючечно-нечитабельно получилось.

@kmqrce · 02.02.2018, 13:20

Как вариант:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <typename BidirectionalIterator, typename Comparator = std::less<>>
void insertion_sort(
    BidirectionalIterator first,
    BidirectionalIterator last,
    Comparator comparator = Comparator()
) {
    if (first != last) {
        for (auto i = first; ++i != last;) {
            auto j = i;
            auto x = std::move(*i);
            if (comparator(x, *first)) {
                std::move_backward(first, i, ++j);
                *first = std::move(x);
            }
            else {
                for (auto k = j; comparator(x, *(--k)); j = k) {
                    *j = std::move(*k);
                }
                *j = std::move(x);
            }
        }
    }
}

@AndrSlav · 02.02.2018, 13:28

Сообщение от outoftime

Там жесткий прикол с беззнаковыми типами.

Не с типами, там алгоритм не верный - нельзя ссылку/указатель использовать.

@outoftime · 02.02.2018, 13:40

Сообщение от hoggy

ValueType& tmp = *i;

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

Добавлено через 6 минут

Сообщение от kmqrce

std::move_backward(first, i, ++j);
*first = std::move(x);

Хорошая идея, как по мне ее можно использовать в обобщенном варианте. Сначала вычислить отрезок который надо сдвигать а потом его двигать и не надо будет условия if (comparator(x, *first)). Всё равно в else идет тот же move_backward только на вычисляемом отрезке

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит переходные токи и напряжения на элементах схемы. . . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,360 Записей в блоге: 5
	01.02.2018, 20:19
	hoggy, ::std это типа "абсолютный путь" что-ли? 0