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

Как можно расширить STL своим набором функций? - C++

Восстановить пароль Регистрация
 
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
02.08.2010, 21:16     Как можно расширить STL своим набором функций? #1
За предисловие сгодится то что я запорол контест из-за того, что юзал STL типа
C++
1
a.find(b) != string::npos
Когда нормальные решения были типа
C++
1
kmp(a,b) != -1
Собственно вопрос: как можно добавить к класу строк свою функция поиска строки в подстроке, к примеру, за алгоритмом Кнута-Мориса-Прата?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.08.2010, 21:16     Как можно расширить STL своим набором функций?
Посмотрите здесь:

C++ как можно сортировать с помошью STL
Можно ли узнать размер одного элемента в STL контейнере? C++
C++ Разработать класс с набором функций для управления односвязным списком
C++ Как можно найти вхождение подстроки в строку без строковых функций?
C++ сколько сортировочных функций в STL?
Создайте dll с произвольным набором простых функций — на ваше усмотрение C++
Где можно найти код реализации библиотеки STL C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2295 / 1665 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
02.08.2010, 21:24     Как можно расширить STL своим набором функций? #2
Единственное переносимое решение данной проблемы, как мне видится, это разработка своего набора функций для решения соответсвующих задач.
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
02.08.2010, 21:32     Как можно расширить STL своим набором функций? #3
outoftime, не совсем понял, это надо штоли?
C++
1
2
3
4
5
6
7
8
class mystring : public std::string
{
public:
    int find(const std::string &s)
    {
        //КМП
    }
};
Если да, то на контесте некогда такой фигней заниматься, проще писать обычную функцию.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
02.08.2010, 21:37  [ТС]     Как можно расширить STL своим набором функций? #4
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
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
typedef vector<int> VI;
 
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
#define MIN(a,b) ( (a) < (b) ? a : b )
 
int kmp(string &s, string &t){
    string sn = s + "#" + t;
    int n = sn.size(), ns = s.size();
    VI p(n);
    FOR(i,1,n) {
        int k = p[i-1];
        while (sn[k] != sn[i] && k) k = p[k-1];
        if (sn[k] == sn[i]) ++k;
        if ((p[i]=k) == ns) return i - 2*ns;
    }
    return -1;
}
 
int main() {
    freopen("test.txt", "r", stdin);
    string a, b;
    cin >> a >> b;
    cout << kmp(a,b) << endl;
    return 0;
}
Т.е. только так?

Добавлено через 29 секунд
Хохол, да, оно, спасибо
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
02.08.2010, 21:37     Как можно расширить STL своим набором функций? #5
А чем плох этот вариант?
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
02.08.2010, 21:47  [ТС]     Как можно расширить STL своим набором функций? #6
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 <string>
#include <vector>
 
using namespace std;
 
typedef vector<int> VI;
 
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
#define MIN(a,b) ( (a) < (b) ? a : b )
 
class str : public std::string {
public:
    int find(str &t){
        string sn = *this + "#" + t;
        int n = sn.size(), ns = this->size();
        VI p(n);
        FOR(i,1,n) {
            int k = p[i-1];
            while (sn[k] != sn[i] && k) k = p[k-1];
            if (sn[k] == sn[i]) ++k;
            if ((p[i]=k) == ns) return i - 2*ns;
        }
        return -1;
    }
};
 
int main() {
    freopen("test.txt", "r", stdin);
    str a, b;
    cin >> a >> b;
    cout << a.find(b) << endl;
    return 0;
}
Вот что я хотел. Спасибо.

Добавлено через 2 минуты
Хохол, Можете сказать хотя-бы как это называется? Мне интересно покопать глубже.

Добавлено через 2 минуты
Цитата Сообщение от Хохол Посмотреть сообщение
Если да, то на контесте некогда такой фигней заниматься, проще писать обычную функцию.
А если это все у меня будет заготовлено? Я если чесно после javascript не представляю жизнь без обьектов вообще..
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2295 / 1665 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
02.08.2010, 21:48     Как можно расширить STL своим набором функций? #7
Цитата Сообщение от outoftime Посмотреть сообщение
Можете сказать хотя-бы как это называется?
Это наследование. Все таки вариант с отдельными функциями более предпочтителен.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
02.08.2010, 21:56  [ТС]     Как можно расширить STL своим набором функций? #8

Не по теме:

Хохол, мне больше нравится, к примеру, когда пишу длинку перегружать операторы умножение для векторов, так как часто бывает нужно написать бинорное подношение к степени, которое пишется в 5 строк:

C++
1
2
3
4
5
int BinPow(int a, int n) {
    VI res(1,1), b(1,a);
    while (n) n & 1 ? res *= b, --n : b *= b, n >>= 1;
    return res;
}

Цитата Сообщение от CyBOSSeR Посмотреть сообщение
Все таки вариант с отдельными функциями более предпочтителен
CyBOSSeR, Можете обосновать? Это влияет на время работы или что-то еще?
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
02.08.2010, 21:57     Как можно расширить STL своим набором функций? #9
В наследовании вы конечно покопайтесь, но на контесте лучше не используйте.
Кстати, вот такое
str a = "hello";
не скомпилится без бубна.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
02.08.2010, 22:00  [ТС]     Как можно расширить STL своим набором функций? #10
Цитата Сообщение от Хохол Посмотреть сообщение
Кстати, вот такое
str a = "hello";
не скомпилится без бубна.
Да, вот это уже проблема...
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2295 / 1665 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
02.08.2010, 22:02     Как можно расширить STL своим набором функций? #11
Цитата Сообщение от outoftime Посмотреть сообщение
Можете обосновать? Это влияет на время работы или что-то еще?
Дело не в скорости. Во - первых, вам понадобится переопределить все возможные конструкторы, операторы присваивания и т.п.. Во-вторых, вариант с функциями гораздо нагляднее, не надо разбиратся, что это за класс такой str. В-третьих, есть еще и и строки из широких символов - std::wstring.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
02.08.2010, 22:19  [ТС]     Как можно расширить STL своим набором функций? #12
Т.е. вердикт: не зарабатывать себе гемор на одно место а использовать функции.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.08.2010, 22:27     Как можно расширить STL своим набором функций?
Еще ссылки по теме:

Как можно объяснить выполнение этих функций? C++
Как посмотреть реализацию функций STL? C++
Можно ли добавлять статические объекты классов в STL контейнеры? C++
Где можно посмотреть коды шаблонов STL? C++
C++ Что можно почитать по STL и паттернам?

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

Или воспользуйтесь поиском по форуму:
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2295 / 1665 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
02.08.2010, 22:27     Как можно расширить STL своим набором функций? #13
Цитата Сообщение от outoftime Посмотреть сообщение
Т.е. вердикт: не зарабатывать себе гемор на одно место а использовать функции.
Да, именно так. Набор функций - лучшее решение.
Yandex
Объявления
02.08.2010, 22:27     Как можно расширить STL своим набором функций?
Ответ Создать тему
Опции темы

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