Здравствуйте, alsemm, Вы писали:

A>Здравствуйте, c-smile, Вы писали:

CS>>Здравствуйте, Алексей Семенюк, Вы писали:

А>>>Аннотация:
А>>>В статье приводится пример реализации нестандартного контейнера, позволяющего обеспечить приемлемую скорость доступа к произвольному элементу и вставки/удаления в произвольную позицию.

CS>>А это случайно не про sparse arrays статья ?
A>Нет, статья не про разряженные массивы

Похоже, это очередная реализация skip list.

CS>>Ссылки по теме:
CS>>http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node9.html
CS>>http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node47.html
CS>>http://math.nist.gov/sparselib++/

ЗЫ. А на счет реализации — я бы концы строк держал в std::vector<char*>
и не мучался. В векторе вставка для POD типов реализована через memmov,
что дает приемлемые показатели быстродействия даже для 10000 строк.

Здравствуйте, Sergeem, Вы писали:

...

S>Похоже, это очередная реализация skip list.

CS>>>Ссылки по теме:
CS>>>http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node9.html
Идем по ссылке и читаем что есть разряженный массив:
This chapter explores sparse arrays. A sparse array is an array where nearly all of the elements have the same value (usually zero), and this value is a constant, known ahead of time.
Вроде не то.

CS>>>http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node47.html
CS>>>http://math.nist.gov/sparselib++/

S>ЗЫ. А на счет реализации — я бы концы строк держал в std::vector<char*>
S>и не мучался. В векторе вставка для POD типов реализована через memmov,
S>что дает приемлемые показатели быстродействия даже для 10000 строк.
Согласен, производительность вставки/удаления будет приемлемой, так же как и доступ к строке по индексу. Но вот реализация int getLineFromChar(int chrIdx); будет тормозной.

Здравствуйте, eugals, Вы писали:

E>Здравствуйте, Алексей Семенюк, Вы писали:

АС>>Статья:

E>А почему нельзя было воспользоваться спецификой предметной области?
E>Вроде же в текстовых редакторах существует такая вещь, как "текущая строка", соответственно, кешируя последний запрошенный указатель, а также его индекс, можно было бы получить очень неплохую скорость поиска/редактирования.
E>Перемещения по тексту тоже обычно происходят последовательно — вверх/вниз на строку/экран. Зная номер текущей строки и имея двусвязный список, вполне реально быстро искать соседние буферы.

E>Или нет?
Все так. Однако бывает что и не последовательно (пример: в MSVC "Ctrl+G").
Забавно получается: вы предлашаете двухсвязный список, тут http://www.rsdn.ru/Forum/Message.aspx?mid=887921&amp;only=1

Автор: Sergeem
Дата: 07.11.04

vector<char*>. Сегментированный список — это и есть компромис между двумя крайностями.

Здравствуйте, alsemm, Вы писали:


S>>ЗЫ. А на счет реализации — я бы концы строк держал в std::vector<char*>
S>>и не мучался. В векторе вставка для POD типов реализована через memmov,
S>>что дает приемлемые показатели быстродействия даже для 10000 строк.
A>Согласен, производительность вставки/удаления будет приемлемой, так же как и доступ к строке по индексу. Но вот реализация int getLineFromChar(int chrIdx); будет тормозной.

Если честно, я не совсем понял для чего эта функция вообще нужна. Обычно хранится пара номер строки/индекс в строке...

АС>Статья:
Отличная статья.

Никак не могу разобратся только, как сделать segmented_list для очень большого списка таких структур
struct data
{
int id;
void *p;
}
для быстрого поиска по id.


объявляю:
typedef list <data> datalist;
typedef segmented_list <data> slist;


для того чтобы потом быстро искать:
int finding_id=23000;
sl.find(cmp_int_idx(finding_id));


главня проблема как объявить теперь этот:
class cmp_int_idx

Здравствуйте, Аноним, Вы писали:

АС>>Статья:
А>Отличная статья.

А>Никак не могу разобратся только, как сделать segmented_list для очень большого списка таких структур
А>struct data
А>{
А> int id;
А> void *p;
А>}
А>для быстрого поиска по id.


А>объявляю:
А>typedef list <data> datalist;
А>typedef segmented_list <data> slist;


А>для того чтобы потом быстро искать:
А>int finding_id=23000;
А>sl.find(cmp_int_idx(finding_id));


А>главня проблема как объявить теперь этот:
А>class cmp_int_idx

забыл сказать что добавил описание

class segmented_list
{
.............
public:
...........

template<class Key>
iterator
find(const Key &key)
{
return hopper_.lower_bound(key);
}
};