нужен std :: vector with O (1) erase

Question

Я с удивлением обнаружил вектор :: erase move elements при вызове erase. Я думал, что он заменит последний элемент элементом «быть удаленным» и уменьшит размер на единицу. Моя первая реакция была: «Давайте продолжим std :: vector и over-ride erase()». Но я нашел во многих потоках, таких как «Is there any real risk to deriving from the C++ STL containers?», что может вызвать утечку памяти. Но я не добавляю ни одного нового элемента данных в вектор. Таким образом, нет дополнительной памяти для освобождения. Есть ли риск?

Некоторые полагают, что мы должны предпочесть композицию над наследованием. Я не могу понять этот совет в этом контексте. Почему я должен тратить свое время на «механическую» задачу обертывания каждой функции замечательного класса std :: vector.? Наследование действительно имеет наибольший смысл для этой задачи - или я чего-то не хватает?

Answer 1

Нежный выпуск. Первая рекомендация, которую вы нарушаете: «Inheritance is not for code reuse». Второе: «Не наследовать от стандартных библиотечных контейнеров».

Но: Если вы можете гарантировать, что никто никогда не будет использовать ваш unordered_vector<T> в качестве vector<T>, вы в порядке. Однако, если кто-то это делает, результаты могут быть неопределенными и/или ужасными, независимо от того, сколько у вас членов (может показаться, что он работает отлично, но, тем не менее, это неопределенное поведение!).

Вы можете использовать private наследство, но это не освобождает вас от написания оберток или вытягивать функции-члены в с большим из using заявлений, которые бы почти столько же, как код композиции (немного меньше, хотя).

---

Edit: Что я имею в виду using заявления заключается в следующем:

class Base { 
    public: 
    void dosmth(); 
}; 

class Derived : private Base { 
    public: 
    using Base::dosmth; 
}; 

class Composed { 
    private: 
    Base base; 
    public: 
    void dosmth() {return base.dosmth(); } 
}; 

Вы можете сделать это со всеми функциями членов std::vector. Как видите, Derived значительно меньше кода, чем Composed.

Answer 2

Риск наследования в следующем примере:

std::vector<something> *v = new better_vector<something>(); 
delete v; 

Это может вызвать проблемы, потому что вы удалили указатель на базовый класс, без виртуального деструктора.
Однако, если вы всегда удалить указатель на свой класс, как:

better_vector<something> *v = new better_vector<something>(); 
delete v; 

Или не выделяют его в куче нет никакой опасности. просто не забудьте вызвать родительский деструктор в деструкторе.

Answer 3

Почему просто не написать отдельную функцию, которая делает то, что вы хотите:

template<typename T> 
void fast_erase(std::vector<T>& v, size_t i) 
{ 
    v[i] = std::move(v.back()); 
    v.pop_back(); 
} 

Всей кредитного Сет Карнеги, хотя. Первоначально я использовал «std :: swap».

Answer 4

Я думал, что он заменит последний элемент элементом «to-be-deleted» и уменьшит размер на единицу.

vector :: erase сохраняет порядок элементов при перемещении последнего элемента на стертый элемент и уменьшает размер на единицу.Поскольку вектор реализует массив, нет способа O (1) поддерживать порядок элементов и стирать в одно и то же время (если вы не удалите последний элемент).

Если порядок заказов не важен, то ваше решение в порядке, в противном случае лучше использовать другие контейнеры (например, список, который реализует дважды связанный список).