Если все типы генов примерно одинакового размера, может быть выигрыш сделать что-то вроде этого:
union Gene
{
A a;
B b;
C c;
D d;
};
class Haplotype
{
std::vector<Gene> genes;
int aEnd, bEnd, cEnd;
public:
A getA(int idx) {
return genes[idx].a;
}
B getB(int idx) {
return genes[idx + aEnd].b;
}
C getC(int idx) {
return genes[idx + bEnd].c;
}
D getD(int idx) {
return genes[idx + cEnd].d;
}
};
Добавление нового гена данного типа в вектор можно выполнять за постоянное время (вам не нужно отталкивать все назад), если вам не важен порядок отдельных типов.
Например, если вам нужно добавить B, вы должны переместить его в точку первого C, затем переместить его в точку первого D, а затем нажать на него в конце. Затем вы увеличиваете каждый из bEnd
и cEnd
.
Например:
Первоначально: [A1, A2, A3, B1, B2, C1, C2, C3, C4, D1, D2, D3, D4, D5]
Добавить новый B на bEnd: [A1, A2, A3, B1, B2, B3, C2, C3, C4, D1, D2, D3, D4, D5]
Заменить выселенного C: [A1, A2, A3, B1, B2, B3, C2, C3, C4, C1, D2, D3, D4, D5]
Добавьте выселенный D в конце: [A1, A2, A3, B1, B2, B3, C2, C3, C4, C1, D2, D3, D4, D5, D1]
.
Чтобы удалить ген за постоянное время, вы должны сделать то же самое в обратном порядке. Суть в том, чтобы сохранить инвариант, что все As предшествуют всем B, которые предшествуют всем C, которые предшествуют всем D.
Эта схема позволяет вам обходиться меньшими издержками: только один int на тип (для хранения конечного индекса), в обмен на более уродливый код, немного дополнительных временных затрат при добавлении или удалении генов и невозможность Держите каждый набор генов в порядке вставки. Вам решать, стоят ли эти недостатки этого.
Кроме того, этот дизайн будет вызывать накладные расходы на элемент, если типы имеют существенно разные размеры, поскольку объединение должно быть как минимум таким же большим, как и его самый большой член.