Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
outoftime
║XLR8║
511 / 433 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
#1

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

02.08.2010, 21:16. Просмотров 969. Ответов 12
Метки нет (Все метки)

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

Можно ли посмотреть в нормальном виде описание STL методов и функций? - C++
Допустим, мне нужно посмотреть, какие члены-функции есть в библиотеке <vector>. Чтобы это сделать, я создаю какой-нибудь вектор, вызываю,...

Как посмотреть реализацию функций STL? - C++
Доброго времени суток. Вопрос возник в процессе выполнения упражнений из книги "Язык программирования C++" Страуструпа. Он предлагает...

как можно сортировать с помошью STL - C++
имеется массив с парными элементами pair<int,string> p; сначала идет рейтинг , потом имя певицы, 4 pamela anderson 5 madonna ...

Разработать класс с набором функций для управления односвязным списком - C++
Добрый день, форумчане! Обращаюсь к вам с просьбой, с чего начать мне выполнение данного задания, какие элементы использовать. Или хотя...

Создайте dll с произвольным набором простых функций — на ваше усмотрение - C++
Уважаемые форумчане, есть такая задачка "Создайте dll с произвольным набором простых функций - на ваше усмотрение. Создайте еще одну...

Как можно получить итератор на элемент обрабатываемый в лямбде в функции for_each?STL - C++
Как можно получить итератор на элемент обрабатываемый в лямбде? for_each(arr.begin(), arr.end(), (char n) {if (n == dubl)...

12
CyBOSSeR
Эксперт С++
2304 / 1674 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
02.08.2010, 21:24 #2
Единственное переносимое решение данной проблемы, как мне видится, это разработка своего набора функций для решения соответсвующих задач.
0
Хохол
Эксперт С++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
02.08.2010, 21:32 #3
outoftime, не совсем понял, это надо штоли?
C++
1
2
3
4
5
6
7
8
class mystring : public std::string
{
public:
    int find(const std::string &s)
    {
        //КМП
    }
};
Если да, то на контесте некогда такой фигней заниматься, проще писать обычную функцию.
0
outoftime
║XLR8║
511 / 433 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
02.08.2010, 21:37  [ТС] #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 секунд
Хохол, да, оно, спасибо
0
Хохол
Эксперт С++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
02.08.2010, 21:37 #5
А чем плох этот вариант?
0
outoftime
║XLR8║
511 / 433 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
02.08.2010, 21:47  [ТС] #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 не представляю жизнь без обьектов вообще..
0
CyBOSSeR
Эксперт С++
2304 / 1674 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
02.08.2010, 21:48 #7
Цитата Сообщение от outoftime Посмотреть сообщение
Можете сказать хотя-бы как это называется?
Это наследование. Все таки вариант с отдельными функциями более предпочтителен.
0
outoftime
║XLR8║
511 / 433 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
02.08.2010, 21:56  [ТС] #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, Можете обосновать? Это влияет на время работы или что-то еще?
0
Хохол
Эксперт С++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
02.08.2010, 21:57 #9
В наследовании вы конечно покопайтесь, но на контесте лучше не используйте.
Кстати, вот такое
str a = "hello";
не скомпилится без бубна.
0
outoftime
║XLR8║
511 / 433 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
02.08.2010, 22:00  [ТС] #10
Цитата Сообщение от Хохол Посмотреть сообщение
Кстати, вот такое
str a = "hello";
не скомпилится без бубна.
Да, вот это уже проблема...
0
CyBOSSeR
Эксперт С++
2304 / 1674 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
02.08.2010, 22:02 #11
Цитата Сообщение от outoftime Посмотреть сообщение
Можете обосновать? Это влияет на время работы или что-то еще?
Дело не в скорости. Во - первых, вам понадобится переопределить все возможные конструкторы, операторы присваивания и т.п.. Во-вторых, вариант с функциями гораздо нагляднее, не надо разбиратся, что это за класс такой str. В-третьих, есть еще и и строки из широких символов - std::wstring.
0
outoftime
║XLR8║
511 / 433 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
02.08.2010, 22:19  [ТС] #12
Т.е. вердикт: не зарабатывать себе гемор на одно место а использовать функции.
0
CyBOSSeR
Эксперт С++
2304 / 1674 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
02.08.2010, 22:27 #13
Цитата Сообщение от outoftime Посмотреть сообщение
Т.е. вердикт: не зарабатывать себе гемор на одно место а использовать функции.
Да, именно так. Набор функций - лучшее решение.
0
02.08.2010, 22:27
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.08.2010, 22:27
Привет! Вот еще темы с ответами:

сколько сортировочных функций в STL? - C++
сколько сортировочных функций в STL?

Как можно объяснить выполнение этих функций? - C++
void push(st *s, int i) // функция заталкивания элемента в стек { s-&gt;data = i; } int pop(st *s) // функция извлечения элемента...

Что можно почитать по STL и паттернам? - C++
всем привет, хотелось бы почитать что ни будь про stl в частности про виртуальные методы, паттерны, вьюхи и тд

Можно ли в ЕГЭ в С части использовать STL - C++
всем привет, можно ли в части Ц, где нужно самому писать программу использовать контейнеры и алгоритмы из STL ?


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

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