9

I've never programmed with C++ professionally and working with (Visual) C++ as student. I'm having difficulty dealing with the lack of abstractions especially with the STL container classes. For example, the vector class doesn't contain a simple remove method, common in many libraries e.g. .NET Framework. I know there's an erase method, it doesn't make the remove method abstract enough to reduce the operation to a one-line method call. For example, if I have a 

std::vector<std::string>

I don't know how else to remove a string element from the vector without iterating thru it and searching for a matching string element. 

bool remove(vector<string> & msgs, string toRemove) {
if (msgs.size() > 0) {
    vector<string>::iterator it = msgs.end() - 1;   
    while (it >= msgs.begin()) {
        string remove = it->data();
        if (remove == toRemove) {
            //std::cout << "removing '" << it->data() << "'\n";
            msgs.erase(it);
            return true;
        }
        it--;
    }
}   
return false;

}

What do professional C++ programmers do in this situation? Do you write out the implementation every time? Do you create your own container class, your own library of helper functions, or do you suggest using another library i.e. Boost (even if you program Windows in Visual Studio)? or something else?

(if the above remove operation needs work, please leave an alternative method of doing this, thanks.)

T. Webster
  • 9,605
  • 6
  • 67
  • 94
  • I personally would use a library with more convenient containers. I like Qt. Of course, a plain list container with a convenient remove-by-value method (e.g. QList::removeAll()) kind of hides the complexity properties. Qt containers also have other beneficial properties like implicit sharing where returning by value is actually a relatively cheap operation. – Tilman Vogel Jul 03 '11 at 21:03
  • in case no one caught it, there's an error in the above code, which illustrates the point Kerrek SB made. It's the decrement. – T. Webster Jul 03 '11 at 22:39

3 Answers3

9

You would use the "remove and erase idiom":

v.erase(std::remove(v.begin(), v.end(), mystring), v.end());

The point is that vector is a sequence container and not geared towards manipulation by value. Depending on your design needs, a different standard library container may be more appropriate.

Note that the remove algorithm merely reorders elements of the range, it does not erase anything from the container. That's because iterators don't carry information about their container with them, and this is fully intentional: By separating iterators from their containers, one can write generic algorithms that work on any sensible container.

Idiomatic modern C++ would try to follow that pattern whenever applicable: Expose your data through iterators and use generic algorithms to manipulate it.

Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084
  • SB: so the general answer for C++ scenarios requiring abstraction is that idiomatic modern C++ has patterns to help us do so with STL, and so we don't need additional libraries for this? – T. Webster Jul 03 '11 at 21:01
  • While being nice and generic, isn't this quite expensive depending on the concrete container class? This may still be OK with something like linked lists, but with a vector, the reordering is quite heavy-weight. – Tilman Vogel Jul 03 '11 at 21:04
  • @Tilman: It really depends. Of course the complexity is linear in the elements moved, but if the elements are swappable or move-constructible (C++0x), you might be surprised by how little you end up paying. Of course if you need to erase a lot from the middle and by value, other containers may well be more appropriate! – Kerrek SB Jul 03 '11 at 21:12
  • 1
    @T. Webster: For all the purely abstract computational data handling, the standard library (please don't say "STL") contains a surprising amount of ready-made algorithms which are probably more efficient and correct than you could write them yourselves. Of course you'll need other libraries for frameworky stuff like terminal hanlding, graphics, networking, images, fonts, etc. But do take a look at Boost, which is a huge library that follows the C++ standard library design philosophy. – Kerrek SB Jul 03 '11 at 21:14
  • @Kerrek SB: Seems like Boost has these algorithms, too, while making them easier to find/use. It's just I've been using the standard library because I figured the standard library is more of an industry standard, and Boost seems like it would be more difficult to use in Visual Studio or on Windows. – T. Webster Jul 03 '11 at 21:22
  • 1
    @T. Webster: Compared to C++98, Boost shouldn't be replicating anything from the standard library, merely extending it. But lots of the new C++0x library was originally implemented in Boost, so nowadays there's some overlap (e.g. random, regex, functional, unordered containers, tuples, memory, thread, atomic). Use the standard if you can. I was just pointing out Boost as an example of the standard philosophy -- even complicated stuff like graphs is designed with a clean separation of interface and implementation. – Kerrek SB Jul 03 '11 at 21:24
  • 2
    @T. Webster: Boost isn't hard at all to use on Visual Studio. In fact, I think it's quite a bit easier because Boost supports Visual Studio's auto linking feature. And boostpro provides handy installers for boost precompiled [here](http://boostpro.com/download/) – Benjamin Lindley Jul 03 '11 at 21:44
  • 2
    @Tilman: Note that the fact that the operation is showing you the cost in terms of the `remove`+`erase` does not make it more costly. With contiguous memory being an invariant, the cost of removing an element from the middle is *always* going to be linear in the size of the container. The STL (I am using STL as I am referring to the original Stepanov library) is focused on genericity and performance, whenever there is an operation that can be implemented more efficiently in an specific container, that operation is added to the container itself. – David Rodríguez - dribeas Jul 03 '11 at 21:45
  • 2
    ... In this particular case, contrary to what you indicate in your comment, the cost of the *remove+erase* idiom is the same for vectors and lists, but in the case of lists, the same operation can be implemented more efficiently, and because of that, `std::list` implements its own specific `remove` function as a member. The question of performance is something that the user needs to solve, not the library. If you need to use a vector *remove-erase* is as fast as it can get, if you need anything faster, don't use a vector. – David Rodríguez - dribeas Jul 03 '11 at 21:50
  • @dribeas, sorry, I somehow imagined, there was a way, the linked-list-iterators could be relinked without copying which is not the case. +1 – Tilman Vogel Jul 03 '11 at 22:04
  • @Kerrek SB: what about using ? http://stackoverflow.com/questions/1016307/list-iterator-remove – T. Webster Jul 04 '11 at 14:31
  • 1
    @T. Webster: In `list` you can just call the member function `remove`. The point is that for *sequence* containers finding by value is linear in time, no matter what. But in `vector` you have the additional burden of moving memory around, while in `list` the actual removal (once you *found* an element) is essentially free -- that's the whole point of the `list` container, and that's why it has its own special member function. Also, the generic algo needs random access iterators, which `list` doesn't have. (That's why it also has it's own `sort` member.) – Kerrek SB Jul 04 '11 at 14:37
  • What's wrong with the term 'STL'? It's certainly commonly used and understood. And if it's good enough for Stroustrup (from http://www2.research.att.com/~bs/DnE2005.pdf: 'the STL (the “Standard Template Library”; that is, the containers and algorithm framework of the ISO C++ standard library)'), it's good enough for me. – Michael Burr Jul 09 '11 at 05:43
  • @Michael: Yeah, the term is generally understood, but the standard itself never mentions it -- I guess it's just unnecessary to keep this term alive. Strings and iostreams are also templated, and basic_string-instantiations can be very useful, too, so "STL" is a somewhat artificial selection... unless of course you mean [the real STL](http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Stephan-T-Lavavej-Advanced-STL-5-of-n) :-) – Kerrek SB Jul 09 '11 at 14:05
4

Have you considered std::remove_if?

http://www.cplusplus.com/reference/algorithm/remove_if/

0

IMO, professionally, it is perfectly logical to write up custom implementation do custom tasks, especially if the standard doesn't provide that. This is much better than writing (read: copy-paste) the same stuff again and again. One may also take advantage of inline function, template functions, macros to place same stuff in one place. This reduces any bugs that may encounter while re-using the same stuff (which may go somewhat wrong while pasting). It also makes it possible to correct the bug in one place.

Templates and macros, if properly designed, are very useful - they aren't code bloat.

Edit: Your code needs improvement:

  • bool remove(vector & msgs, cosnt string& toRemove);
  • To iterator over a collection, a for loop is sufficient. There is no need to check for size, take last iterator, check with begin, get data and all.
  • There is no need to waste a string - just compare it, and remove.

For your problem, I believe a map or set would fit much better.

Ajay
  • 18,086
  • 12
  • 59
  • 105