Есть список некоторых обьектов.
В нем последовательно ищутся подинтервалы вызовом std::search и заменяются на новые. Элементы нового подинтервала не должны принимать участие в последующих поисках std::search, то есть вставленные элементы как бы заранее не равны, тем элементам которые будут искаться. Как бы такое реализовать?
Надеюсь более менее понятно обьяснил.
Была мысль сохранять начало и конец вновь вставленного интервала, и написать свой search, где в предикат передавать итераторы не разименовывая и там сравнивать. Но у листа итераторы не поддреживают <, >
Здравствуйте, placement_new, Вы писали:
_>Здравствуйте, placement_new, Вы писали:
_>Была мысль сохранять начало и конец вновь вставленного интервала, и написать свой search, где в предикат передавать итераторы не разименовывая и там сравнивать. Но у листа итераторы не поддреживают <, >
Можно, еще сохранять всю последовательность, а не только начала и конец, но мне кажется это не православным, такой алгоритм.
Здравствуйте, placement_new, Вы писали:
_>Есть список некоторых обьектов. _>В нем последовательно ищутся подинтервалы вызовом std::search и заменяются на новые. Элементы нового подинтервала не должны принимать участие в последующих поисках std::search, то есть вставленные элементы как бы заранее не равны, тем элементам которые будут искаться. Как бы такое реализовать?
Фактически, первый же найденный и заменённый интервал разрывает список — поскольку следующий поиск не может пересечься с заменённым куском, и будет либо строго до, либо строго после.
После второй замены — список будет разорван уже на три части... Ну и так далее.
Отсюда идея: пусть на входе будет последовательность интервалов, и на выходе тоже последовательность интервалов.
Демострашилка
#include <list>
#include <string>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <cstring>
template<class It> struct range
{
typedef It iterator;
It begin, end;
range() {}
range(It b, It e) : begin(b), end(e) {}
bool empty() const { return begin==end; }
ptrdiff_t size() const { return distance(begin,end); }
};
template<class It> range<It> make_range(It b, It e) { return range<It>(b,e); }
template<class R> struct found // результат search
{
R before, here, after;
bool failed() const { return here.empty() && after.empty(); }
};
// для наглядности, будем потрошить строку...typedef char E;
typedef std::list<E> data_t; // список символов
// задача выражена в виде двух произвольных интервалов: что на что меняемtypedef std::string::const_iterator ToFind, ToReplace; // интервалы берём из строкиtypedef std::pair< range<ToFind>, range<ToReplace> > task_t;
typedef range<data_t::iterator> chunk_t;
typedef std::list<chunk_t> chunks_t; // list принципиально - иначе процедура замены немного усложнится (из-за инвалидации при вставке-удалении)
task_t make_task(std::string const& f, std::string const& r)
{
return task_t(make_range(f.begin(), f.end()), make_range(r.begin(), r.end()));
}
// немножко вывода
std::ostream& operator << (std::ostream& ost, chunk_t const& chunk)
{
ost << "<";
std::copy(chunk.begin, chunk.end, std::ostream_iterator<char>(ost, ""));
ost << ">";
return ost;
}
std::ostream& operator << (std::ostream& ost, chunks_t const& chunks)
{
std::copy(chunks.begin(), chunks.end(), std::ostream_iterator<chunk_t>(ost, ""));
return ost;
}
std::ostream& operator << (std::ostream& ost, data_t const& data)
{
ost << "'";
std::copy(data.begin(), data.end(), std::ostream_iterator<char>(ost, ""));
ost << "'";
return ost;
}
// процедура массовой замены - должна знать и сам контейнер, и коллекцию кусочковvoid replace(data_t& data, chunks_t& chunks, task_t const& task)
{
if(task.first.empty()) return;
std::cout << data << " as " << chunks << " ~ " << (&*task.first.begin) << " / " << (&*task.second.begin) << std::endl;
chunks_t::iterator ci = chunks.begin();
while(ci != chunks.end())
{
chunk_t& chunk = *ci;
std::cout << chunk << "..." << std::endl;
data_t::iterator di = std::search(chunk.begin, chunk.end, task.first.begin, task.first.end);
if(di == chunk.end) // не найдено
{
std::cout << " skipped" << std::endl;
++ci;
continue;
}
data_t::iterator dj = di; std::advance(dj, task.first.size());
ptrdiff_t headsize = std::distance(chunk.begin, di);
// выполняем замену: добавляем новое, удаляем старое
std::cout << "0: " << data << std::endl;
data.insert(di, task.second.begin, task.second.end); // di по-прежнему указывает на искомую серию
std::cout << "I: " << data << std::endl;
data.erase(di, dj); // при этом инвалидируется di - придётся отсчитывать заново от chunk.begin
std::cout << "E: " << data << std::endl;
std::cout << " splitted to ";
// добавляем головной кусокif(headsize != 0) // в противном случае, кстати, chunk.begin тоже инвалидирован
{
di = chunk.begin; std::advance(di, headsize);
chunk_t newchunk(chunk.begin, di);
chunks.insert(ci, newchunk);
std::cout << newchunk;
}
else
{
std::cout << "nothing";
}
std::cout << " and ";
// добавляем (переписываем) хвостовой кусокif(dj == chunk.end)
{
std::cout << "nothing";
chunks.erase(ci++); // хвост пуст - удаляем (и продолжим забег уже со следующего куска)
}
else
{
chunk.begin = dj; // хвост не пуст - подправляем (и продолжим забег по данному куску)
std::cout << chunk;
}
std::cout << std::endl;
// и теперь, в зависимости от твоей задачи, либо продолжаем забег с данным task, либо завершаем работу
}
std::cout << data << " as " << chunks << std::endl << "---------------" << std::endl;
}
int main()
{
std::string source = "mama myla ramu, rama krasnel so sramu";
data_t data(source.begin(), source.end());
chunks_t chunks(1, chunk_t(data.begin(),data.end()));
// строки заданий здесь создаются временные - но они живут до конца выполнения replace
replace(data, chunks, make_task("ma", "panama"));
replace(data, chunks, make_task("am", "abram"));
replace(data, chunks, make_task("m", "z"));
// а вот так можно/нужно разнести задания и исполнение
std::vector< std::pair<std::string, std::string> > ts;
ts.push_back( std::make_pair("ma", "panama") );
for(int i=0, n=ts.size(); i!=n; ++i)
replace(data, chunks, make_task(ts[i].first, ts[i].second));
}
Здравствуйте, placement_new, Вы писали:
_>Есть список некоторых обьектов. _>В нем последовательно ищутся подинтервалы вызовом std::search и заменяются на новые. Элементы нового подинтервала не должны принимать участие в последующих поисках std::search, то есть вставленные элементы как бы заранее не равны, тем элементам которые будут искаться. Как бы такое реализовать? _>Надеюсь более менее понятно обьяснил.
В общем, реализация основана на обертке класса SearchObject вокруг std::search. Внутри класса запоминаютя интервалы по которым производился поиск, и потом они благополучно избегаются при следующем вызове SearchObject.search. Причем специфика реализации такова, что созданный объект класса SearchObject жестко привязан к контейнеру по которому идет поиск. Применение Object.search() к другому контейнеру приведет к ошибке, зато те контейнеры которые задают прототип поиска могут быть любые. Для каждого экземпляра контейнера нужно создавать новый объект поиска SearchObject. Для использования SearchObject::search(..., unsigned int interval) в отличие от std::search :
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(
ForwardIterator1 _First1,
ForwardIterator1 _Last1,
ForwardIterator2 _First2,
ForwardIterator2 _Last2
); , нужно указать дополнительный параметр intеrval = Last2 — First2, так как оператор "-" не определен для некоторых контейнеров (std::list<> например) и нельзя тогда было сравнивать подинтервалы. В остальном у них синтаксис совпадает. Так как использубтся шаблоны, то итераторы могут быть любые( в том числе простые указатели), главно чтобы операции ++ и * применялись к итератору.
Еще мысль есть написать свой итератор для контейнера по которому идет поиск, так чтобы он как-то взаимодействовал с std::search. То есть итератор должен как-то запоминать те куски, которые std::search нашел. Ну это так, мысли в слух.
Итак, ...
template<class ForwardIterator>
class Pair{
public:
explicit Pair(ForwardIterator f, int s):from_(f), size_(s){}
ForwardIterator from_;
unsigned int size_;
};
Перекуём баги на фичи!
