Как добиться большей эффективности повторной вставки в наборы в C ++

Question

Мне нужно изменить объект, который уже был вставлен в набор. Это не тривиально, потому что итератор в паре, возвращенной после вставки одного объекта, является константным итератором и не допускает изменений. Итак, мой план состоял в том, чтобы в случае неудачной вставки я мог скопировать этот объект во временную переменную, удалить его из набора, изменить его локально, а затем вставить свою измененную версию.

insertResult = mySet.insert(newPep);
    if( insertResult.second == false )
        modifySet(insertResult.first, newPep);

void modifySet(set<Peptide>::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<Peptide>::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);            

}

Однако это приводит к ошибке сегмента. Я надеюсь, что кто-то может сказать мне, почему эта вставка не удалась, или предложить другой способ изменить объект, который уже был вставлен в набор.

Полный исходный код можно посмотреть по адресу github .

Answer 1

Я согласен с Питером, что карта, вероятно, является лучшей моделью того, что вы делаете, особенно что-то вроде map<pep_key, Peptide::Peptide>, позволит вам сделать что-то вроде:

insertResult = myMap.insert(std::make_pair(newPep.keyField(), newPep));
if( insertResult.second == false )
    insertResult.first->second = newPep;  

Чтобы ответить на ваш вопрос,insert segfaults, потому что стирание делает недействительным итератор, поэтому вставка с ним (или его копией) аналогична разыменованию недействительного указателя.Единственный способ сделать то, что вы хотите, это использовать const_cast

insertResult = mySet.insert(newPep);
if( insertResult.second == false )
    const_cast<Peptide::Peptide&>(*(insertResult.first)) = newPep;

. Подход const_cast выглядит так, как будто он подойдет вам, но в целом это плохая идея.

Answer 2

Я надеюсь, что отвечать на мой вопрос неплохо, но я бы хотел, чтобы он был здесь на случай, если кто-то еще столкнется с этой проблемой.Ответ о том, почему моя попытка сбиться с сега была дана моему Academ Robot, но вот решение, чтобы сделать эту работу с набором.В то время как я ценю другие ответы и планирую узнать о картах, этот вопрос был об эффективной повторной вставке в set .

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% масштабируется.

Answer 3

std :: set :: insert возвращает парунасколько я знаю.В любом случае, прямое изменение элемента в любом наборе рискованно.Что если ваша модификация приводит к тому, что элемент сравнивается с другим существующим элементом?Что если он изменит позицию элемента в общем порядке элементов в наборе?В зависимости от реализации это приведет к неопределенному поведению.

Если ключ элемента остается прежним и изменяются только его свойства, то я думаю, что вам действительно нужна карта или неупорядоченная_карта вместо набора.

Answer 4

Как вы поняли, set немного беспорядочно, потому что у вас нет способа указать, какую часть объекта следует рассматривать как ключ, а какую часть вы можете безопасно изменить.

Обычный ответ - использовать map или unordered_map (если у вас есть доступ к C ++ 0x) и разрезать ваш объект на две половины: ключ и спутниковые данные.

Остерегайтесь типичного ответа: std::map<key_type, Peptide>, хотя это кажется простым, это означает, что вам нужно гарантировать, что ключевая часть объекта Peptide всегда соответствует ключу, с которым он связан, компилятор не поможет. *

Итак, у вас есть 2 варианта:

1. Разрежьте Peptide на две части: Peptide::Key и Peptide::Data, тогда вы можете безопасно использовать map.
2. Не предоставляйте никаких методов для изменения части 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;

Обратите внимание, что в случае обновления это означает создание нового объекта (конструктор по умолчанию), а затем его присвоение. Здесь это невозможно, потому что присвоение означает потенциально изменение ключевой части объекта.

Answer 5

std :: map сделает вашу жизнь намного проще, и я не удивлюсь, если она превзойдет std :: set для этого конкретного случая.Хранение ключа может показаться избыточным, но может быть тривиально дешевым (например: указатель на неизменяемые данные в пептиде с вашим собственным предикатом сравнения для правильного сравнения указателя).При этом вам не нужно возиться с постоянством значения, связанного с ключом.

Если вы можете изменить реализацию Peptide, вы можете полностью избежать избыточности, превратив Peptide в два отдельных класса: один дляключевая часть и одна для значения, связанного с ключом.