Container access and allocation through the same operator?

Question

I have created a container for generic, weak-type data which is accessible through the subscript operator.

The std::map container allows both data access and element insertion through the operator, whereas std::vector I think doesn't.

What is the best (C++ style) way to proceed? Should I allow allocation through the subscript operator or have a separate insert method?

EDIT

I should say, I'm not asking if I should use vector or map, I just wanted to know what people thought about accessing and inserting being combined in this way.

Answer 1

In the case of Vectors: Subscript notation does not insert -- it overwrites.

This rest of this post distils the information from item 1-5 of Effective STL.

If you know the range of your data before hand -- and the size is fixed -- and you won't insert at locations which has data above it -- then you can use insert into vectors without unpleasant side-effects.

However in the general case vector insertions have implications such as shifting members upward and doubling memory when exhausted (which causes a flood of copies from the old vector's objects to locations in the new vector ) when you make ad hoc insertions. Vectors are designed for when you know the locality characteristics of your data..

Vectors come with an insert member function... and this function is very clever with most implementations in that it can infer optimizations from the iterators your supply. Can't you just use this ?

If you want to do ad-hoc insertions of data, you should use a list. Perhaps you can use a list to collect the data and then once its finalized populate a vector using the range based insert or range based constructor ?

Answer 2

it depends what you want. A map can be significantly slower than a vector if you wish to use the thing like an array. A map is very helpful if the index you want to use is non-sequential and you have LOADS of them. Its usually quicker to just use a vector, sort it and do a binary search to find what you are after. I've used this method to replace maps in tonnes of software and I still haven't found something where it was slower to do this with a vector.

So, IMO, std::vector is the better way, though a map MIGHT be useful if you are using it properly.

Answer 3

Separate insert method, definitely. The operator[] on std::map is just stupid and makes the code hard to read and debug. Also you can't access data from a const context if you're using a operator[] to insert (which will lead to un-const-cancer, the even-more evil cousin of const-cancer).