Why isn't vector::operator[] implemented similar to map::operator[]?

Question

Is there any reason for std::vector's operator[] to just return a reference instead of inserting a new element? The cppreference.com page for vector::operator says here

Unlike std::map::operator[], this operator never inserts a new element into the container.

While the page for map::operator[] says

"Returns a reference to the value that is mapped to a key equivalent to key, performing an insertion if such key does not already exist."

Why couldn't vector::operator[] be implemented by calling vector::push_back or vector::insert like how map::operator[] calls insert(std::make_pair(key, T())).first->second;?

The way `std::map::operator[]` is actually implemented causes much enough confusion already. UB is fine for `std::vector` accessed out of bounds. — πάντα ῥεῖ, May 05 '16 at 02:08
Imagine what would happen if we wrote `some_vector[1000]` while `some_vector` was of size 10. Well, I just don't know what to imagine with the 990 entries in the middle. — , May 05 '16 at 02:18
@KerrekSB, how so? There are no middle entries to be initialized in the map. — Tyler, May 05 '16 at 02:20
@KerrekSB I would say it has problems, but not he same problem, just like what Tyler has said. — , May 05 '16 at 02:22
@Tyler: No, if you say it that way, then there's indeed a difference. But if you consider "initializing enough elements to make sense", then both map and vector could reasonably value-initialize the required elements that make the access valid. — Kerrek SB, May 05 '16 at 02:22
@KerrekSB OK, I would say I agree they are the same *kind of* problem. But "1 vs many" still differs enough. It is imaginable that someone would justify the design decision with this difference. — , May 05 '16 at 02:29
I think the distinction of the question, though, is why does `std::map::operator[]()` insert an element, *even if just accessing* a non-existent key? — scottbb, May 05 '16 at 02:30

jplatte · Accepted Answer · 2016-05-05T02:26:58.773

8

Quite simply: Because it doesn't make sense. What do you expect

std::vector<int> a = {1, 2, 3};
a[10] = 4;

to do? Create a fourth element even though you specified index 10? Create elements 3 through to 10 and return a reference to the last one? Neither would be particularily intuitive.

If you really want to fill a vector with values using operator[] instead of push_back, you can call resize on the vector to create the elements before settings them.

Edit: Or, if you actually want to have an associative container, where the index is important apart from ordering, std::map<int, YourData> might actually make more sense.

edited May 05 '16 at 02:26

answered May 05 '16 at 02:18

jplatte

1,121
11
21

2

It may be worth stressing the crucial point: For `map`, the operator inserts at most that one element at the given key. For `vector`, you would also have to insert *other* elements at other indexes. – Kerrek SB May 05 '16 at 02:20
+1. Also worth mentioning that C++ considers performance concerns more than many of languages (e.g., Java). This is why `vector::operator[]` performs no bounds checking; you can opt-in to them manually if you feel you need them, but C++ wants to have no overhead here. Even if inserting non-existent elements in a vector made sense, it would contradict the performance goals pretty directly. As with a desire for bounds-checking, if you desire elements be inserted for you, you can build a higher-level class on top of vector yourself and opt-in. – GManNickG May 05 '16 at 02:55
@GManNickG So basically, if I would like to insert non-existent elements, then I am forced to use a map because of vector being a sequence container? – 1337ninja May 07 '16 at 08:13
1

@1337ninja: No. Like I wrote you can use `resize` and `push_back` for `std::vector`. It really depends on your use case and you haven't explained it very well yet. – jplatte May 07 '16 at 12:28

score 2 · Answer 2 · answered May 05 '16 at 02:42

A map and a vector are completely different concepts. A map is an "associative container" whereas a vector is a "sequence container". Delineating the differences is out of the scope of this answer, though at the most superficial of levels, a map is generally implemented as a red-black tree, while a vector is a convoluted wrapper over a C-style array (elements stored contiguously in memory).

If you want to check if an element already exists, you would need to resize the entire container. But what happens if you decide to remove the element? What do you do with the entries you just created? With a map:

std::map<int, int> m; 
m[1] = 1; 
m.erase(m.begin());

This is a constant operation.

With a vector:

std::vector<int> v;
// ... initialize some values between 25 and 100
v[100] = 1;
v.erase(v.begin() + 25, v.end());

This is a linear operation. That's horribly inefficient (comparatively) to a map. While this is a contrived example, it's not hard to imagine how this could blow up in other scenarios. At a minimum, most people would go out of their way to avoid operator[] which as a cost in of itself (maintenance and code complexity).

+1 because you touched on the fact that vectors and pointers are based on two separate data structures. Vectors are pretty much fancy arrays, while maps are based off of pointers. Maps are great if you need to use iterators to search. While Vectors are awesome if you know what element you need in array. — Caperneoignis, May 05 '16 at 03:01

score 0 · Answer 3 · edited May 23 '17 at 11:52

Is there any reason for std::vector's operator[] to just return a reference instead of inserting a new element?

std::vector::operator[] is implemented in an array-like fashion because std::vector is a sequence container (i.e., array-like). Standard arrays for integral types cannot be accessed out of bounds. Similarly, accessing std::vector::operator[] with an index outside of the vector's length is not allowed either. So, yes, the reasons it is not implemented as you ask about is because in no other context, do arrays in C++ act like that.

std::map::operator[] is not a sequence container. Its syntax makes it similar to associative arrays in other languages. In terms of C++ (and its predecessor, C), map::operator[] is just syntactic sugar. It is the "black sheep" of the operator[] family, not std::vector::operator[].

The interesting part of the C++ specification regarding is that accessing a map with a key that doesn't exist, using std::map::operator[], adds an element to the map. Thus,

#include <iostream>
#include <map>
int main(void) {
   std::map<char, int> m;
   m['a'] = 1;
   std::cout << "m['a'] == " << m['a'] << ", m.size() == " << m.size() << std::endl;
   std::cout << "m['b'] == " << m['b'] << ", m.size() == " << m.size() << std::endl;
}

results in:

m['a'] == 1, m.size() == 1
m['b'] == 0, m.size() == 2

See also: Difference between map[] and map.at in C++? :

[map::at] throws an exception if the key doesn't exist, find returns aMap.end() if the element doesn't exist, and operator[] value-initializes a new value for the corresponding key if no value exists there.

Why isn't vector::operator[] implemented similar to map::operator[]?

3 Answers3