2

I was surprised to find out the vector::erase move elements on calling erase . I thought it would swap the last element with the "to-be-deleted" element and reduce the size by one. My first reaction was : "let's extend std::vector and over-ride erase()" . But I found in many threads like " Is there any real risk to deriving from the C++ STL containers? ", that it can cause memory leaks. But, I am not adding any new data member to vector. So there is no additional memory to be freed. Is there still a risk?

Some suggest that we should prefer composition over inheritance. I can't make sense of this advice in this context. Why should I waste my time in the "mechanical" task of wrapping every function of the otherwise wonderful std::vector class.? Inheritance indeed makes the most sense for this task - or am I missing something?

Community
  • 1
  • 1
Abhishek Anand
  • 3,789
  • 2
  • 21
  • 29
  • 7
    Why not just write a free function that does what you want? – Seth Carnegie Apr 14 '12 at 20:32
  • 1
    Doesn't that violate OOP principles? member functions should have EXCLUSIVE rights to modify member-data . Of course, I agree that OOP principles are not "god-sent", but I do appreciate the need of encapsulation to reason better about my programs – Abhishek Anand Apr 14 '12 at 20:50
  • 2
    @AbhishekAnand: To the contrary, the more member functions you have, the worst your encapsulation. – GManNickG Apr 14 '12 at 20:55
  • 1
    @Abhishek No, it definitely does not violate OOP principles. You would just use the interface; you wouldn't access internal data or make it a friend function (which _would_ violate OOP principles). Also, take a look at the `algorithm` header: there are dozens of functions that modify containers. If you do it the way you are thinking, then you run into the N*M problem. – Seth Carnegie Apr 14 '12 at 20:56
  • @SethCarnegie thanks... BTW, what is the N*M problem? – Abhishek Anand Apr 14 '12 at 21:05
  • @SethCarnegie: To be picky, but doesn't the `algorithm` header only contain functions which modify the *contents* of containers, by iterator ranges. – dalle Apr 14 '12 at 21:16
  • 1
    @AbhishekAnand the N*M problem is the thing that happens when you have N containers and M algorithms (a horribly large number), you must have N*M implementations. The solution is to make them templated non-member functions in which case you only have M implementations (which is optimal). – Seth Carnegie Apr 14 '12 at 21:16
  • @dalle no, for example `sort` does not modify the contents (the actual items) but the order of the elements. – Seth Carnegie Apr 14 '12 at 21:17
  • @SethCarnegie: The difference is that the functions in `algorithm` cannot add or remove elements in a collection, as the functions in `algorithm` operates on iterator ranges. In order to add/remove elements in a collection you need to use the correct member function, or the helper classes (such as `back_insert_iterator`, `front_insert_iterator` and `insert_iterator`) in the `iterator` header. – dalle Apr 14 '12 at 21:28

4 Answers4

11

Why not just write a standalone function that does what you want:

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

All credit to Seth Carnegie though. I originally used "std::swap".

cdiggins
  • 17,602
  • 7
  • 105
  • 102
4

Delicate issue. The first guideline you're breaking is: "Inheritance is not for code reuse". The second is: "Don't inherit from standard library containers".

But: If you can guarantee, that nobody will ever use your unordered_vector<T> as a vector<T> you're good. However, if somebody does, the results may be undefined and/or horrible, regardless of how many members you have (it may seem to work perfectly but nevertheless be undefined behaviour!).

You could use private inheritance, but that would not free you from writing wrappers or pulling member functions in with lots of using statements, which would almost be as much code as composition (a bit less, though).

Edit: What I mean with using statements is this:

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

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

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

You could do this with all member functions of std::vector. As you can see Derived is significantly less code than Composed.

bitmask
  • 32,434
  • 14
  • 99
  • 159
  • A bit less code? You wouldn't need any of those `using` statements with composition. – leftaroundabout Apr 14 '12 at 20:41
  • 2
    @leftaroundabout With composition you'd need to implement a whole bunch of forwarding functions instead of one liner `using` statements. – Praetorian Apr 14 '12 at 20:42
  • @leftaroundabout: No you wouldn't need the `using` statement in the first place. Instead you would need to implement a wrapper for every single `using` statement. Wrappers are a lot longer to write down and more prone to break with maintenance (perhaps even silently). However, I give you that the `vector` interface wouldn't change significantly between standards. – bitmask Apr 14 '12 at 20:44
  • 1
    Ah, I wasn't aware that `using` in the `public` section actually makes the inherited functions public. Something learned again! – leftaroundabout Apr 14 '12 at 20:49
  • There would not be THAT much `using`s as you think, especially compared to the number of `typedef` that you will need anyway if you want to be STL-compatible. However, you will need to think about what STL concepts you want to implement anyway (hint: not Sequence), and you may have to implement some operators wrappers if your current or future implementation of vector override operators using free functions. – BatchyX Apr 14 '12 at 20:51
  • @leftaroundabout: I edited the post to make this point a tad clearer. – bitmask Apr 14 '12 at 20:57
3

The risk of inheritance is in the following example:

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

That would cause problems because you deleted a pointer to a base class with no virtual destructor.
However if you always delete a pointer to your class like:

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

Or don't allocate it on the heap there is no danger. just don't forget to call the parent destructor in your destructor.

Daniel
  • 30,896
  • 18
  • 85
  • 139
  • all the data members are in base class. I AM NOT ADDING ANY NEW MEMBER IN better_vector. So the base class destructor should be able to do all the cleanup . Why would there be a memory leak? – Abhishek Anand Apr 14 '12 at 20:38
  • 5
    @AbhishekAnand: It doesn't matter. You're still invoking undefined behaviour, if you skip a derived class's destructor. It probably works with any compiler you test, but it's still a bad practice. – bitmask Apr 14 '12 at 20:50
2

I thought it would swap the last element with the "to-be-deleted" element and reduce the size by one.

vector::erase maintains order of elements while moving last element to erased element and reduce the size by one does not. Since vector implements array, there is no O(1) way to maintain order of elements and to erase at the same time (unless you remove the last element).

If maintaining order of elements is not important than your solution is fine, otherwise, you better use other containers (for example list, which implements doubly-linked list).

invisal
  • 11,075
  • 4
  • 33
  • 54