Мне нужно реализовать структуру данных - таблицу так, чтобы можно было быстро вставлять строки и столбцы в любое место. Таблица должна состоять из булевых значений. То есть что-то типа Код (Text): typedef std::vector< std::vector<bool> > table; Но в случае с векторами добавление элементов будет работать медленно. Имеет смысл заюзать связный список, но, по видимому, таких списков не бывает. То есть нужно что-то типа: Код (Text): struct cell { cell* right; cell* bottom; vool value; }; То есть каждый элемент списка должен иметь 2 ссылки: на тот, который справа от него и на тот, который ниже. В таком случае добавление новой строки будет сводиться к добавлению элементов в вертикальные списки. Аналогично добавление колонки - в горизонтальные. Может есть стандартные контейнеры для реализации моей задачи? Или нужно писать свой? Основная моя задача - именно построение этой таблицы, а не обращение к её элементам. Данные будут читаться только один раз - при отображении. Нужно максимально оптимизировать процесс заполнения.
Booster, про обычный лист я знаю. Но он ведь не подходит для решения моей задачи. Или я чего-то не понимаю?
cupuyc typedef std::list< std::list<bool> > table; ^) Кто сказал, что вставка в вектор это медленно? Был проведён соответствующий тест? Почему был выбран лист? Почему не map/hash_map?
list<list<bool> > Тут не поможет. Знаю я, допустим, что нужно добавить колонку между второй и третьей. Как быть? Для каждой строки мотать в цикле итератор? Как-то косячно. ------------------------------------------------------------------------------------------------------ Объясню задачу более конкретно. Есть, скажем, такая табличка Код (Text): 1.2 3.4 7.7 8.1 1.0 0 0 1 1 2.1 0 0 0 0 3.3 1 1 0 0 5.6 1 1 0 1 У каждой строки и каждого столбца есть идентефикатор - некоторое вещественное число. Идентефикаторы должны идти по порядку. Я хочу добавить в этот список новую колонку с идентефикатором 4.1. Как я это реализую. Создаю 2 сета - один для строк, другой для столбцов Код (Text): struct cell { cell* right; cell* bottom; bool value; }; struct elem { double value; cell* list; operator < (..) }; typedef std::set<elem> elems; elems rows; elems cols; Сейчас всё это нужно объединить в класс - таблица и написать методы добавления строки и столбца. Добавление строки займёт времени пропорциональное количеству столбцов. Добавление стобца - пропорционально количеству строк. Если делать с векторами, то время добавления будет порядка количество строк * количество столбцов. Задачка чисто алгоритмическая, так что нужен оптимальный вариант.
Значит надо писать свой велосипед. Ещё можно создать маленький класс, который собственно и будет хранить дополнительную вертикальную связь вместе со значением.
У этого варианта тоже куча недостатков. Мало того, что велосипед, так ещё избыточность ссылок. В общем х.з. Видать придётся решать задачу именно так.
Если таблица будет пополняться только вставками строк и столбцов, можно их не встявлять, а добавлять в конец. А для каждого столбца/строки завести "порядковый номер", по которому в конце отсортировать.
связные списки и резиновые вектора связаны с частой (ре)аллокацией. этот момент будет отнимать большую часть времени при заполнении. не зная подробностей специфики задачи оттолкнусь от заданного формата в вид таблицы и требования к максимальной скорости заполнения я бы это дело реализовал на расширяемых таблицах. причем расширяться должно с помощью цепочек (не векторов!). можно и в ширь, можно и в длинь. из начальных координат сразу получаем номер подтаблицы и ячейку в ней. быстрее хэша. данные в таблице могут быть в виде изначально null-ёваных ссылок на реальные данные или в целях борьбы с фрагментацией и тормозами от лишних разбросанных обращений к памяти - в виде таблиц с флагами занятости и типа данных и юнионом по допустимым типам данных. не могущие жить без классов могут оформить это в виде классов, но если нужна скорость - желательно сразу посмотреть во что оно скомпилилось. в зависимости от размеров подтаблиц скорость может быть достигнута (тонкости работы озу)
cupuyc Зачем изобретать велосипеды, когда в сообщениях 4 и 8 есть более чем исчерпывающие решения? А ваш велосипед памяти ест в 96(при выравнивании на 4 байта) раз больше возможного минимума, да еще и лишнего кода будет в нём.
#4 и #8 проблемы не решают. Да и мой вариант тоже её не решает. Можете сами убедиться, продумав логику вставки новых строк и столбцов. В общем я уже придумал другой вариант, так что тема не актуальна. Вообще, можно сказать, обошёлся без таблички. Точнее, я для каждой строки храню области пересечений с каждым столбцом. Для этого и понадобился сортированный список. Я взял std::set. Ещё такой вопрос. Как можно в потоке ввода пропустить все белые символы? Только тупо мотать цикл? Код (Text): while (true) { char const c = sin::peek(); if (is_white(c)) { sin.seekg(1, std::ios_base::seekdir::cur); } else { break; } }
я бы свой вектор написал оптимизированый в байтовый бул в котором аллокатор сразу выделяет средний максимум который будет в таблице по вертикали к примеру а потом сделал массив векторов и была бы таблица либо вектор векторов заоптимизированый в бинарное дерево а зачем seek? там вроде обычный get() есть - да, только крутить цикл
cupuyc С хеш таблицей я вообще не вижу проблем вставки новых строк и столбцов. Да и в последовательной записи значений вмести с "номерами" строк и столбцов с последующей сортировкой - тоже. Или у вас основная задача отличается от заявленной в первом сообщении?
Black_mirror, нет, я всё правильно написал. Просто Вы не продумываете логику вставки. Для нумерованной таблицы они вставятся, и довольно быстро, но порядок данных в таблице нарушится. Учитывайте, что нумеруются как строки, так и столбцы. Для list<list<bool> > вставлять элементы значительно сложней. Если нужно вставить столбец в середину списка, то придётся мотать итератор для каждой строки. В любом случае объём вычислений получается ~количество строк * количество столбцов.
Ещё вопросик появился. Есть множество структур: Код (Text): std::set<some_struct> ... struct some_struct { float v1; float v2; bool operator < (some_struct const& a) { return v1 < a.v1; } }; Перебирая элементы множества мне нужно модифицировать значения v2. Но так сделать не получается (на VC полечается, на gcc нет), т.к. итератор от std::set возвращает const reference. Понятно, почему он так делает, но я ведь не нарушу целостность дерева, т.к. сравнивание элементов идёт по v1, модифицировать мне нужно v2. Как тут оптимальней? Сделать mutable v2 или const_cast?
>каждый элемент списка должен иметь 2 ссылки: на тот, который справа от него и на тот, который ниже Деревья бывают разными Алсо, задачу переписать можно. Есть более конкретный пример?
