Как достигнуть лучшей перевставки эффективности в наборы в C++
Я должен изменить объект, который был уже вставлен в набор. Это не тривиально, потому что итератор в паре, возвращенной из вставки отдельного объекта, является итератором константы и не позволяет модификации. Так, мой план состоял в том, что, если вставка перестала работать, я мог бы скопировать тот объект во временную переменную, стереть ее из набора, изменить ее локально и затем вставить мою измененную версию.
insertResult = mySet.insert(newPep);
if( insertResult.second == false )
modifySet(insertResult.first, newPep);
void modifySet(set::iterator someIter, Peptide::Peptide newPep) {
Peptide tempPep = (*someIter);
someSet.erase(someIter);
// Modify tempPep - this does not modify the key
someSet.insert(tempPep);
}
Это работает, но я хочу сделать свою вставку более эффективной. Я пытался делать другой итератор и установить его равный someIter в modifySet. Затем после удаления someIter у меня все еще был бы итератор к тому местоположению в наборе, и я мог использовать это в качестве местоположения вставки.
void modifySet(set::iterator someIter, Peptide::Peptide newPep) {
Peptide tempPep = (*someIter);
anotherIter = someIter;
someSet.erase(someIter);
// Modify tempPep - this does not modify the key
someSet.insert(anotherIter, tempPep);
}
Однако это приводит к отказу seg. Я надеюсь, что кто-то может сказать мне, почему эта вставка перестала работать, или предложите другой способ изменить объект, который был уже вставлен в набор.
Полный исходный код может быть просмотрен в GitHub.
5 ответов
Надеюсь, это неплохой тон, чтобы ответить на мой собственный вопрос, но я бы хотел, чтобы он был здесь, на случай, если у кого-то еще когда-нибудь возникнет эта проблема. Ответ о том, почему моя попытка seg не удалась, был дан моему академическому роботу, но вот решение, чтобы заставить эту работу работать с набором. Хотя я ценю другие ответы и планирую изучить карты, этот вопрос касался эффективной повторной вставки в набор .
void modifySet(set<Peptide>::iterator someIter, Peptide::Peptide newPep) {
if( someIter == someSet.begin() ) {
Peptide tempPep = (*someIter);
someSet.erase(someIter);
// Modify tempPep - this does not modify the key
someSet.insert(tempPep);
}
else {
Peptide tempPep = (*someIter);
anotherIter = someIter;
--anotherIter;
someSet.erase(someIter);
// Modify tempPep - this does not modify the key
someSet.insert(anotherIter, tempPep);
}
}
В моей программе это изменение снизило время выполнения примерно на 15%, с 32 до 27 секунд. Мой больший набор данных в настоящее время обрабатывается, и я скрещиваю пальцы, чтобы оценить масштаб улучшения на 15%.
Я согласен с Питером в том, что карта, вероятно, является лучшей моделью того, что вы делаете, в частности, что-то вроде map , позволит вам сделайте что-нибудь вроде:
insertResult = myMap.insert(std::make_pair(newPep.keyField(), newPep));
if( insertResult.second == false )
insertResult.first->second = newPep;
Чтобы ответить на ваш вопрос, вставка segfaults, потому что erase делает недействительным итератор, поэтому вставка с ним (или его копией) аналогична разыменованию недопустимого указателя. Я вижу, что единственный способ сделать то, что вы хотите, - это использовать const_cast
insertResult = mySet.insert(newPep);
if( insertResult.second == false )
const_cast<Peptide::Peptide&>(*(insertResult.first)) = newPep;
, подход const_cast выглядит так, как будто он будет работать для того, что вы делаете, но в целом это плохая идея.
Как вы поняли, set немного запутан, потому что у вас нет способа указать, какая часть объекта должна рассматриваться для ключа, а какая часть вы можете модифицируйте безопасно.
Обычный ответ - использовать карту или unordered_map (если у вас есть доступ к C ++ 0x) и разрезать объект на две половины: ключ и спутник. данные.
Остерегайтесь типичного ответа: std :: map , хотя это кажется простым, это означает, что вам нужно гарантировать, что ключевая часть объекта Peptide всегда сопоставьте ключ, с которым он связан, компилятор не поможет.
Итак, у вас есть 2 альтернативы:
- Разрезать
пептидпополам:Peptide :: KeyиPeptide :: Data, тогда вы можете использоватькартабезопасно. - Не предоставляйте никакого метода для изменения части
Peptide, которая определяет ключ, тогда вы можете использовать типичный ответ.
Наконец, обратите внимание, что есть два способа вставить в -подобный объект map.
insert: вставить, но не удается, если значение уже существуетoperator []: вставить или обновить (что требует создания пустого объекта)
Итак, решение будет:
class Peptide
{
public:
Peptide(int const id): mId(id) {}
int GetId() const;
void setWeight(float w);
void setLength(float l);
private:
int const mId;
float mWeight;
float mLength;
};
typedef std::unordered_map<int, Peptide> peptide_map;
Обратите внимание, что в случае обновления это означает создание нового объекта (конструктор по умолчанию) и последующее присвоение ему.Здесь это невозможно, потому что присвоение означает возможное изменение ключевой части объекта.
std :: map сделает вашу жизнь намного проще, и я не удивлюсь, если он превосходит std :: set в данном конкретном случае. Хранение ключа может показаться избыточным, но может быть тривиально дешевым (например, указатель на неизменяемые данные в Peptide с вашим собственным предикатом сравнения для правильного сравнения указателя). При этом вам не нужно беспокоиться о постоянстве значения, связанного с ключом.
Если вы можете изменить реализацию Peptide, вы можете полностью избежать избыточности, разделив Peptide на два отдельных класса: один для ключевой части и один для значения, связанного с ключом.
std::set::insert возвращает пару
Если ключ элемента остается неизменным и меняются только его свойства, то, думаю, вам действительно нужна карта или неупорядоченная карта, а не набор.