Всем добрый день!!

Мне необходим контейнер с поддержкой следующих операций

1) вставка элемента
2) удаление элемента
3) итератор произвольного доступа (нужен проход по сортированному содержимому)

теперь о частоте вызова операций
предполагается что каждый вызов , вставки/удаления влечет за собой полный проход по сортированному контейнеру (при помощи итератора произвольного доступа) это одно из условий!!!

на первый взгляд 2 решения
1) std::vector , после вставки /удаления сортируемся
2) std::map ,но тут придется эмулировать итератор при помощи std::advance

Сравнение сложности операций
vector : map
вставка: n*log(n) , log(n)
удаление: n*log(n) , log(n)
проход: n , n*n

отсюда я делаю вывод выбрать 1 вариант.

какие могут быть еще варианты ?

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

А>какие могут быть еще варианты ?
могу предложить два варианта: boost::flat_map, aurgmented RB-tree с подсчетом детей справа и слева (за основу можно взять что-ни будь такое: http://kaba.hilvi.org/pastel/pastel/sys/redblacktree.htm )

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

А>3) итератор произвольного доступа (нужен проход по сортированному содержимому)

А зачем для прохода итератор произвольного доступа?

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

А>предполагается что каждый вызов , вставки/удаления влечет за собой полный проход по сортированному контейнеру (при помощи итератора произвольного доступа) это одно из условий!!!

А>на первый взгляд 2 решения
А>1) std::vector , после вставки /удаления сортируемся

Если уж так вот очень надо делать так, то лучше тогда не сортbроваться, а сдвигать "хвост" вектора, пока не найдёшь место для вставки...

Ну, что-то типа

std::vector<XXX> v;

if( v.size() == 0 || to_add > v.back() ) {
    v.push_back( to_add );
} else {
    v.push_back( v.back() );
    std::vector<XXX>::iterator i = v.end();
    for( i -= 2; i != v.begin() && i[-1] > to_add; --i ) {
        *i = i[-1];
    }
    *i = to_add;
}

Или, если думаешь, что swap для типа элемента работает быстрее копирования:

v.push_back( to_add );
for( std::vector<XXX>::iterator i = v.end() - 1; i != v.begin() && i[-1] > *i ; i-- ) {
    assert( *i == to_add );
    std::swap( i[-1], *i );
}

и то и то -- О(N), а не O(N ln N), как в случае с сортировкой после вставки...

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

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

А>>какие могут быть еще варианты ?
U>могу предложить два варианта: boost::flat_map, aurgmented RB-tree с подсчетом детей справа и слева (за основу можно взять что-ни будь такое: http://kaba.hilvi.org/pastel/pastel/sys/redblacktree.htm )


Для boost::flat_map вроде хуже чем с vector получается

вставка : log n
удаление : log n
проход : n*log(n)

мат ожидание сложности для boost::flat_map
(при условии что вставка, удаление, проход равновероятны + вставка и удаление порождают проход)

E = (log n + n*log(n)) *0,33 + (log n + n*log(n) )*0,33 + n*log(n)*0,33 = n*log(n) + 0.66*n

мат ожидание сложности для контейнера на основе std::vector
(при условии что вставка, удаление, проход равновероятны + вставка и удаление порождают проход)

E = (n*log(n) + n) *0,33 + (n*log(n)+ n)*0,33 + n*0,33 = 0.66*n*log(n) + n

для
>>для aurgmented RB-tree с подсчетом детей справа и слева
пока не вкурил как построить алгоритм

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

А>теперь о частоте вызова операций
А>предполагается что каждый вызов , вставки/удаления влечет за собой полный проход по сортированному контейнеру (при помощи итератора произвольного доступа) это одно из условий!!!

Тогда сортированный вектор, вставка в середину (поддержание упорядоченности). Это будет стоить O(N), но, поскольку там всё равно сразу же грядёт полный проход по коллекции, то это не страшно.

Или, если наблюдается реальный провал производительности, — придётся изгаляться.
Дополненные двоичные деревья (там, правда, нагрузка на менеджер кучи и на фрагментацию памяти — т.е. это не cache-friendly), B±деревья всякие...

Кстати, зачем нужен произвольный доступ к упорядоченной коллекции?
Не исчерпывается ли он быстрым поиском и последовательным доступом в окрестностях найденных элементов?

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

А>>теперь о частоте вызова операций
А>>предполагается что каждый вызов , вставки/удаления влечет за собой полный проход по сортированному контейнеру (при помощи итератора произвольного доступа) это одно из условий!!!

К>Тогда сортированный вектор, вставка в середину (поддержание упорядоченности). Это будет стоить O(N), но, поскольку там всё равно сразу же грядёт полный проход по коллекции, то это не страшно.

деку можно попробовать.

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

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

А>>предполагается что каждый вызов , вставки/удаления влечет за собой полный проход по сортированному контейнеру (при помощи итератора произвольного доступа) это одно из условий!!!

А>>на первый взгляд 2 решения
А>>1) std::vector , после вставки /удаления сортируемся

E>Если уж так вот очень надо делать так, то лучше тогда не сортbроваться, а сдвигать "хвост" вектора, пока не найдёшь место для вставки...

E>Ну, что-то типа

E>std::vector<XXX> v;

E>if( v.size() == 0 || to_add > v.back() ) {
E>    v.push_back( to_add );
E>} else {
E>    v.push_back( v.back() );
E>    std::vector<XXX>::iterator i = v.end();
E>    for( i -= 2; i != v.begin() && i[-1] > to_add; --i ) {
E>        *i = i[-1];
E>    }
E>    *i = to_add;
E>}

Или, если думаешь, что swap для типа элемента работает быстрее копирования:

E>v.push_back( to_add );
E>for( std::vector<XXX>::iterator i = v.end() - 1; i != v.begin() && i[-1] > *i ; i-- ) {
E>    assert( *i == to_add );
E>    std::swap( i[-1], *i );
E>} 
E>

E>и то и то -- О(N), а не O(N ln N), как в случае с сортировкой после вставки...

Да , это хороший вариант , наверное он мне подходит

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

К>Кстати, зачем нужен произвольный доступ к упорядоченной коллекции?
т.к. есть сторонний фреймверк которому надо скормить данные
а работает он по схеме
1) сколько дашь элементов
2) дай такой то элемент

К>Не исчерпывается ли он быстрым поиском и последовательным доступом в окрестностях найденных элементов?
спасибо за совет . я подумаю

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


К>Тогда сортированный вектор, вставка в середину (поддержание упорядоченности). Это будет стоить O(N), но, поскольку там всё равно сразу же грядёт полный проход по коллекции, то это не страшно.

это по сути то про что писал Егор , чуть выше.
вставка n
удаление n
проход n


К>Дополненные двоичные деревья (там, правда, нагрузка на менеджер кучи и на фрагментацию памяти — т.е. это не cache-friendly), B±деревья всякие...
тут можно идею доп деревьев чуть поподробнее ? без учета нагрузки на фрагментацию памяти

какой из показателей вставка , удаление , проход улучшиться ?

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

NB>Здравствуйте, Кодт, Вы писали:

А>>>теперь о частоте вызова операций
А>>>предполагается что каждый вызов , вставки/удаления влечет за собой полный проход по сортированному контейнеру (при помощи итератора произвольного доступа) это одно из условий!!!

К>>Тогда сортированный вектор, вставка в середину (поддержание упорядоченности). Это будет стоить O(N), но, поскольку там всё равно сразу же грядёт полный проход по коллекции, то это не страшно.

NB>деку можно попробовать.

в моем случае не катит

вставка n
вырезание n
проход с учетом произвольного доступа n*n

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

AD>Для boost::flat_map вроде хуже чем с vector получается
виноват, имелся в виду flat_set и его сложность совпадает с sorted array, т.к. по сути это он и есть

>>>для aurgmented RB-tree с подсчетом детей справа и слева
AD>пока не вкурил как построить алгоритм

ссылка по теме: http://www.rsdn.ru/forum/cpp.applied/5380434.flat#5380434

Автор: kolobok55
Дата: 02.12.13

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

К>Или, если наблюдается реальный провал производительности, — придётся изгаляться.
К>Дополненные двоичные деревья (там, правда, нагрузка на менеджер кучи и на фрагментацию памяти — т.е. это не cache-friendly), B±деревья всякие...
1) зато у них есть плюс : элементы не копируются при вставке\удалении других элементов
2) кастомные аллокаторы решают проблему фрагментациии памяти и локализации данных. есть в бусте и в студии >=2012, #include <allocators>

при оценке сложности алгоритмов желательно учитывать кол-во копирований элементов, это может критически повлиять на общую производительность
стратегий передвигания элементов в sorted array может быть несколько (зависит от типа данных):
1) поэлементное копирование
2) поэлементный move \ swap
3) групповой memmove

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

AD>Да , это хороший вариант , наверное он мне подходит
Рад, что помог.
Если я верно понял о чём речь, то тебе после добавления, надо ещё и всё просканировать. Возможно можно циклы совместить, но это имеет смысл только для очень длинного вектора, который в кэш не лезет, иначе получишь усложнение кода без всякой пользы.

В любом случае, если ты расскажешь, зачем нужно сканировать ветор после добавления, и зачем нужен итератор с произвльным доступом, а не двунаправленный например, то может тебе что-то более глобальное тут подскажут.
Например, если произвольный доступ нужен только для +- 1..2, то может оказаться более быстрым std::list, хотя в целом он более медленный. В общем если расскажешь больше, могут дать более хороший совет.

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

NB>деку можно попробовать.
А что это даст?

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

NB>>деку можно попробовать.
E>А что это даст?

чуть быстрее вектора с некоторых случаях работает.

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

NB>чуть быстрее вектора с некоторых случаях работает.
Ну эти "некоторые случаи", в основном, сводятся к добавлению/удалению в начало, а это вроде как не особо надо ТС...
Тут, скорее, может стоило бы посмотреть в сторону какой-то деревянной коллекции с индексом в векторе, который строится,перестраивается по требованию и, возможно, по кускам.

например, если у нас будет какое-то дерево, которое по элементу быстро умеет получить номер в упорядоченной последовательности, и в качествеитератора, позволяет использовать указатель на узел, то можно было бы иметь дерево с данными + индекс в виде вектора итераторов узлов. Тогда после добавления, мы сразу бы получали и место в индексе, куда надо вставить новый итератор...

то есть, например, если у нас в узле дерева, скажем красно-чёрного будет лежать число элементов в поддереве, а само дерево будет на указателях + прошитое + на отдельном непрерывном аллокаторе, что бы данные по куче не размазывать, то, доавление/удаление элемента будет не сильно дороже, а в результате процедуры добавления/удаления, получим сразу и число элементов ДО модифицируемого элемента + быстрый индекс в векторе, куда вставки будут на memmove'ах...
Правда получим лишнюю косвенность при запросе элемента по индексу. В общем, если я верно понял задачу ТС, ему это не надо...

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

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

AD>>Да , это хороший вариант , наверное он мне подходит
E>Рад, что помог.
E>Если я верно понял о чём речь, то тебе после добавления, надо ещё и всё просканировать. Возможно можно циклы совместить, но это имеет смысл только для очень длинного вектора, который в кэш не лезет, иначе получишь усложнение кода без всякой пользы.

E>В любом случае, если ты расскажешь, зачем нужно сканировать ветор после добавления, и зачем нужен итератор с произвльным доступом, а не двунаправленный например, то может тебе что-то более глобальное тут подскажут.
E>Например, если произвольный доступ нужен только для +- 1..2, то может оказаться более быстрым std::list, хотя в целом он более медленный. В общем если расскажешь больше, могут дать более хороший совет.

есть некий фреймверк который отображает items
для этого ему (фреймверку ) я должен передать model из которой он извлечет данные

class CModel
{
public:
    size_t count();
    TItem  data(size_t index);
}

дальше он показывает показывает model.
соответственно данные добавляются новые / удаляются / редактируются (при всем этом должен поддерживаться сортировка)
вот как то так.
Соответственно после каждой каждой модификации данный модуль отображения должен перерисовать данные

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

E>Здравствуйте, night beast, Вы писали:


E>например, если у нас будет какое-то дерево, которое по элементу быстро умеет получить номер в упорядоченной последовательности, и в качествеитератора, позволяет использовать указатель на узел, то можно было бы иметь дерево с данными + индекс в виде вектора итераторов узлов. Тогда после добавления, мы сразу бы получали и место в индексе, куда надо вставить новый итератор...

правильно я понимаю что как только возникает дерево , то сразу произвольный доступ по индексу мы выполняем за log n ?

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

AD>Соответственно после каждой каждой модификации данный модуль отображения должен перерисовать данные
а он реально сканирует все данные хаотично при таком апдейте? А то может, например, у него есть там какой-то курсор, который он как-топ озиционирует, и потом он от курсора просто получает скока ему надо итемов подряд?
Если второе, то моет просто можно приделать в модель механизм кэширования позиции и строить инекс не на всю коллекуию. а только на нужную часть? Ну там постранично, например?