Generic operations on C++ containers

Question

How to write generic operations on C++ STL containers? For example, Java has Collection interface, which every Java containers (except for maps) implements. I can do operations like add, remove, contains, and iterations regardless of whether the actual container is LinkedList, HashSet, ArrayBlockingQueue, etc. I find it very powerful. C++ has iterators, but what about operations like add and remove? vector has push_back, set has insert, queue has push. How to add something to C++ container in a generic way?

Answer 1

Iteration:

All standard containers have iterators which give ordered access to the elements of the containers. These can also be used in generic algorithms which work on any conforming iterator type.

Insertion:

All sequences and associative containers can have elements inserted into them by the expression c.insert(i, x) -- where c is a sequence or associative container, i is an iterator into c and x is a value that you want to add to c.

std::inserter and friends can be used to add elements to a sequence or associative container in a generic way.

Removal:

For any sequence or associative container the following code works:

while (true) {
    X::iterator it(std::find(c.begin(), c.end(), elem));
    if (it == c.end()) break;
    c.erase(it);
}

Where X is the type of the container, c is a container object and elem is an object with the value that you want to remove from the container.

For sequences there is the erase-remove idiom, which looks like:

c.erase(std::remove(c.begin(), c.end(), elem), c.end());

For associative containers you can also do:

c.erase(k);

Where k is a key corresponding to the element that you want to erase.

A nice interface to all of this:

See Boost.Range.

Note -- these are compile time substitutable, whereas the java ones are run time substitutable. To allow run-time substitution it is necessary to use type erasure (that is -- make a templated sub-class that forwards the required interface to the container that it is instantiated with).

Answer 2

Look at the header <algorithm>. There are plenty of generic algorithms in there for finding, sorting, counting, copying, etc, that work on anything providing iterators with various specified characteristics.

Answer 3

C++ has std::inserter and friends to add elements to a container in a generic way. They are in the header file iterator.