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

STL и string - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 1, средняя оценка - 4.00
dzrkot
zzzZZZ...
 Аватар для dzrkot
516 / 346 / 53
Регистрация: 11.09.2013
Сообщений: 1,977
04.06.2014, 12:53     STL и string #1
начал тут 1 задачу на форуме решать
в text1 какой-то текст, мы ищем в нем слова str и после них вставляем слова str2

вообщем я не могу придумать решение при помощи STL, по идее применяю search. записываю результат в итератор
, затем insert в позицию этого итератора, если it1==txt.end() то выходим ....вообещм подскажите не умею решать такого плана задачи пока что =(
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 <fstream>
#include <algorithm>
 
using namespace std;
 
int main()
{
ifstream in("text1.txt");
string str,txt,str2;
while(!in.eof())
  {
  getline(in,str);
  txt+=str+'\n';
  }
cout<<"enter search word : "<<endl;
cin>>str;
cout<<"enter cin word : "<<endl;
cin>>str2;
str2=" "+str2+" ";
string::iterator it1=txt.begin();
int i=0;
 
while(it1!=txt.end())
  {
  cout<<*(it1=search(it1,txt.end(),str.begin(),str.end()));
     if(it1!=txt.end())
  txt.insert(it1,str2.begin(),str2.end());
  }
cout<<endl<<txt;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ilot
Модератор
Эксперт С++
1767 / 1142 / 223
Регистрация: 16.05.2013
Сообщений: 3,020
Записей в блоге: 5
Завершенные тесты: 1
04.06.2014, 13:44     STL и string #2
Тонкость в том, что в классе string (впрочем как и в vector) нет подходящей ф-и insert. Проблема возникает из-за того, что вставка может привести к перераспределению памяти для контейнера и как следствие все итераторы станут валидными. Думаю здесь лучше выполнять вставку копированием. Т.е. вводим вспомогательную строку в которую будем записывать исходную строку кусками. В тех местах где будет вхождение искомой подстроки мы добавляем к временной другую подстроку и продолжаем поиск подстроки дальше.
Примерная реализация(не проверял) :
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
  std::string text;
  std::string output;
  std::string w1, w2;
 
  std::cout << "Input w1: ";
  std::cin >> w1;
  std::cout << "Input w2: ";
  std::cin >> w2;
 
  //Заносим исходный текст в text
/*
...
*/
  
  std::string::iterator iterlo = text.begin();
  std::string::iterator iterhi = text.begin();
 
  do {
    iterhi = std::search(iterlo, text.end(), w1.begin(), w1.end());
    std::copy(iterlo, iterhi, std::back_inserter(output));
    if (iterhi != text.end())
      output += w1 + ' ' + w2;
    iterlo = iterhi + w1.size();
    iterhi = iterlo;
  } while(iterhi != text.end());
dzrkot
zzzZZZ...
 Аватар для dzrkot
516 / 346 / 53
Регистрация: 11.09.2013
Сообщений: 1,977
04.06.2014, 13:49  [ТС]     STL и string #3
Цитата Сообщение от Ilot Посмотреть сообщение
Тонкость в том, что в классе string (впрочем как и в vector) нет подходящей ф-и insert. Проблема возникает из-за того, что вставка может привести к перераспределению памяти для контейнера и как следствие все итераторы станут валидными. Думаю сдесьлучше выполнять вставку копирование. Т.е. вводим вспомогательную строку в которую будем записывать исходную строку кусками. В тех местах где будет вхождение искомой подстроки мы добавляем к временной другую подстроку и продолжаем поиск подстроки дальше.
спасибо, такой вариант мне показался менее эстетичным, я думал что можно решить это именно вставкой, мб как-то через insert_iterator (но для string вроде его нет). Как вариант ещё перегнать из string в другой контейнер, и там делать вставку, но проще уж тогда действительно использовать доп string и конкатенацию
Ilot
Модератор
Эксперт С++
1767 / 1142 / 223
Регистрация: 16.05.2013
Сообщений: 3,020
Записей в блоге: 5
Завершенные тесты: 1
04.06.2014, 14:12     STL и string #4
insert_iterator это врапер для метода insert. Что в лоб, что по лбу. Можно конечно использовать посимвольную вставку
C++
1
iterator insert (iterator position, const value_type& val);
Но я думаю вы понимаете, к чему приведет эта идея...
Однако не все так плохо. У нас ведь есть списки. Посимвольная вставка для них имеет такую же сигнатуру, что и для других контейнеров, но выполняется за константное время. Эти соображения наводят нас на мысль, что все же лучше использовать не контейнер string, а list.
SatanaXIII
04.06.2014, 15:24
  #5

Не по теме:

Цитата Сообщение от Ilot Посмотреть сообщение
и как следствие все итераторы станут валидными
Перестанут быть, наверное имелось в виду.

IGPIGP
04.06.2014, 17:09
  #6

Не по теме:

Цитата Сообщение от Ilot Посмотреть сообщение
все итераторы станут валидными
Цитата Сообщение от SatanaXIII Посмотреть сообщение
Перестанут быть, наверное имелось в виду.
да бывает. Главное же понятно, что
все не итераторы станут валидными
вернее
не все итераторы станут валидными
то есть старые лучше не использовать, после каждой операции.

0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
04.06.2014, 18:48     STL и string #7
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Либо я чего-то не понял, либо одно из двух...

Цитата Сообщение от Ilot Посмотреть сообщение
Тонкость в том, что в классе string (впрочем как и в vector) нет подходящей ф-и insert.
Как нет?
http://www.cplusplus.com/reference/s...string/insert/

Цитата Сообщение от Ilot Посмотреть сообщение
Думаю здесь лучше выполнять вставку копированием
Омг, зачем? Идти по строке и на ее основе строить новую где-то в третьем месте... Сложно. И получаются двойные затраты по памяти. Как отметил выше, есть insert, который решает задачу. Инвалидация итераторов? И черт с ними - не будем вообще их использоавть.

Цитата Сообщение от Ilot Посмотреть сообщение
У нас ведь есть списки. Посимвольная вставка для них имеет такую же сигнатуру, что и для других контейнеров, но выполняется за константное время.
Только аллокаций памяти на каждый символ нам не хватало.

От слов к коду:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <string>
 
int main() {
    std::string origin = "list string vector list map map list vector string list";
    const std::string search_str = "list";
    const std::string additional_str = "&&";
    
    size_t pos = 0;
    
    while ((pos = origin.find(search_str, pos)) != std::string::npos) {
        pos += search_str.size();
        origin.insert(pos, additional_str);
        pos += additional_str.size();
    }
    
    std::cout << origin << std::endl;
    
    return 0;
}
http://ideone.com/Atkrz3
Psilon
Master of Orion
 Аватар для Psilon
5742 / 4690 / 619
Регистрация: 10.07.2011
Сообщений: 14,162
Записей в блоге: 5
Завершенные тесты: 4
04.06.2014, 18:55     STL и string #8
Сообщение было отмечено автором темы, экспертом или модератором как ответ
dzrkot, а что если регулярками? Они как раз для таких случаев и нужны. За один проход чтобы осуществить все замены.

Добавлено через 3 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <string>
#include <regex>
 
using namespace std;
 
int main() {
    const string origin = "list string vector list map map list vector string list";
    const string search_str = "list";
    const string additional_str = "&&";
    regex e(search_str);
    string result = regex_replace(origin, e, "$0" + additional_str);
    cout << result << endl;
    return 0;
}
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
04.06.2014, 18:57     STL и string #9
Psilon, из пушки по воробьям. Такое же двойное использование памяти + регулярки же. Краткость записи, конечно, соблазнительна, но они явно для задач более сложных.
Psilon
Master of Orion
 Аватар для Psilon
5742 / 4690 / 619
Регистрация: 10.07.2011
Сообщений: 14,162
Записей в блоге: 5
Завершенные тесты: 4
04.06.2014, 19:03     STL и string #10
0x10, двойное использование памяти - возможно, но вот скорость должна быть выше. Насколько я помню, там идет всего лишь один проход по строке КМП-алгоритмом с построением суффиксного дерева. А в случае с find будет N+1 проходов по строке. При этом при insert афайк приходится все равно докидывать конец массива дальше, чтобы вставляемая строка влезла. Ну и краткость, конечно, куда без неё

Добавлено через 2 минуты
Краткость записи, конечно, соблазнительна, но они явно для задач более сложных.
ятп они подходят для большинства типичных работ со строками. В первую очередь тех, которые подразумевают несколько проходов по строке, когда можно обойтись одним. Сколько бы приколов и анекдотов ни ходило про регулярки, они в своей области очень хороший инструмент (если не заходит речь про валидацию email-адресов, конечно )
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
04.06.2014, 19:27     STL и string #11
Цитата Сообщение от Psilon Посмотреть сообщение
А в случае с find будет N+1 проходов по строке.
У меня ровно один проход - в find передается позиция, с которой начинать поиск.

Добавлено через 21 минуту
Пононял тесты - ок, верю - с регулярками получается быстрее.
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6172 / 2901 / 284
Регистрация: 04.12.2011
Сообщений: 7,719
Записей в блоге: 3
05.06.2014, 03:39     STL и string #12
Цитата Сообщение от 0x10 Посмотреть сообщение
Как нет?
0x10, не уверен, но думаю Ilot, не имел ввиду, что её нет. Вставка в последовательный контейнер (особенно где-то в начало) это тоже перевыделение, пусть и не посимвольное. У ассоциативного контейнера поэлементное выделение, но один раз.
Мощность холивара пропорциональна количеству вставок в одну и ту же строку.
Psilon, вчера я чуток помучился с replace С#. Причем если бы меня спросили, то ответил бы, что ф-ция член возвращает новую копию строки. Но никто (и я сам себя) не спросил... Пару часов ломился. Вызываю, а строка как дуська не меняется! Потом посмотрел в документацию и в первых же словах нашёл.
Родство ситуации в том, что в многобайтовой кодировке replace-фрагмент может не соответствовать замещаемому по размеру и получается та же дилемма, что и при вставке. Авторы почли за лучшее сделать то, о чём Ilot говорит. Или я не понял как всегда.
Voivoid
 Аватар для Voivoid
580 / 256 / 12
Регистрация: 31.03.2013
Сообщений: 1,284
05.06.2014, 08:30     STL и string #13
boost::replace
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.06.2014, 08:42     STL и string
Еще ссылки по теме:

STL String. Вывести слово и после него количество символов C++
C++ Использование библиотеки STL , контейнер string. Дан массив слов.Надо удалить все цифры из слов
C++ Какое одинаковое значение можно вернуть из функций <string> f () и vector < <string> > f()?

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

Или воспользуйтесь поиском по форуму:
Ilot
Модератор
Эксперт С++
1767 / 1142 / 223
Регистрация: 16.05.2013
Сообщений: 3,020
Записей в блоге: 5
Завершенные тесты: 1
05.06.2014, 08:42     STL и string #14
Цитата Сообщение от 0x10 Посмотреть сообщение
Как нет?
Ключевое слово:
Цитата Сообщение от Ilot Посмотреть сообщение
Тонкость в том, что в классе string (впрочем как и в vector) нет подходящей ф-и insert.
Т.е. нет функции вставляющей строку и возвращающей итератор за последним символом вставленной строки. Есть только функция член вставляющая символ.
Цитата Сообщение от 0x10 Посмотреть сообщение
Омг, зачем? Идти по строке и на ее основе строить новую где-то в третьем месте... Сложно. И получаются двойные затраты по памяти.
Верно двойные затраты по памяти. Зато нет квадратичных затрат при смещении символов во время вставки.
Цитата Сообщение от 0x10 Посмотреть сообщение
Только аллокаций памяти на каждый символ нам не хватало.
Согласен. Это может быть тоже плохим решением. Чрезмерное использование памяти.
Спасибка за то что никогда не умел работать с size_type и npos.
Yandex
Объявления
05.06.2014, 08:42     STL и string
Ответ Создать тему
Опции темы

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