Why std::pair does not work with some STL containers?

Question

It seems that some containers accept std::pair<const int, int> as a value type, but some do not. The problem is of course in the const part.

I did some googling and found that only std::vector requires copy-assignable data. However, std::pair<const int, int> works just fine with std::vector, std::set and std::list (and perhaps other containers), but not with std::map and std::priority_queue (the latter really bugs me).

The following compiles without problems (gcc 6.1.0)

std::vector<std::pair<const int, int>> vector;
vector.push_back(std::make_pair(3, 5));
std::set<std::pair<const int, int>> set;
set.insert(std::make_pair(3, 5));
std::list<std::pair<const int, int>> list;
list.push_back(std::make_pair(3, 5));

But this results in compilation errors:

std::priority_queue<std::pair<const int, int>> pq;
pq.push(std::make_pair(3, 5));
std::map<int, std::pair<const int, int>> map;
map[2] = std::make_pair(3, 5);

error: assignment of read-only member ‘std::pair<const int, int>::first’

What is the reason behind this? Shouldn't std::map and std::set have the same behavior given that they have the same underlying implementation? Why does it work with std::vector although it requires to move data?

The containers were not designed to contain `const` elements. [See this thread](http://stackoverflow.com/questions/6954906/does-c11-allow-vectorconst-t) — M.M, Oct 12 '16 at 19:46
I don't understand your confusion. You're attempting an assignment and are complaining that you are not able to assign to constants. — Kerrek SB, Oct 12 '16 at 19:48
@S.K.: `vector[0] = std::make_pair(3, 5);` won't work either. — Jarod42, Oct 12 '16 at 19:50
@KerrekSB I am not complaining, I just want to understand why different containers behave differently and whether this is an expected behavior or not. — S. K., Oct 12 '16 at 19:50
The containers were written for non-const contents and the behaviour you get is mostly coincidental based on what the library writers did to implement the non-const variants — M.M, Oct 12 '16 at 19:52
That has nothing to do with containers. You're simply attempting to assign to a constant. — Kerrek SB, Oct 12 '16 at 19:52
_"Shouldn't std::map and std::set have the same behavior ..."_: to test this you need to make the pair<> the key of the map. — Richard Critten, Oct 12 '16 at 21:35

T.C. · Accepted Answer · 2016-10-12T20:03:36.703

8

Anything that requires assignment will break.

vector::push_back doesn't require assignment, only copy/move construction.
ditto for set::insert.
ditto for list::push_back.
priority_queue::push needs to move around the existing elements to maintain the heap property (via std::push_heap), which requires assignment.
map[2] = stuff; is literally an assignment. Use map::insert or map::emplace if you want it to work.

edited Oct 12 '16 at 20:03

answered Oct 12 '16 at 19:57

T.C.

133,968
17
288
421

`vector::push_back` actually requires to move elements around. – Slava Oct 12 '16 at 20:02
@Slava It's copy/move construction on reallocation, not assignment. – T.C. Oct 12 '16 at 20:03
@Slava It does. Where did I say it doesn't? – T.C. Oct 12 '16 at 20:06
Then I do not understand why for `std::vector` to move elements it does not require assignments, but for `std::push_heap` it does. – Slava Oct 12 '16 at 20:07
@Slava `vector` is moving everything to a new location. `push_heap` reorders elements within the sequence, for which assignment is more efficient. – T.C. Oct 12 '16 at 20:09
1

Erasing elements from a vector or deque also requires assignment. – Kerrek SB Oct 12 '16 at 20:13
@KerrekSB I think for a deque, `pop_front` and `pop_back` do not require assignment. – Brian Bi Oct 12 '16 at 20:26
@T.C. Thanks for the answer. I really think that container should not copy the data inside using the assignment operator because this is not a behavior intended by the user and therefore should not limit the use of the container. One solution is to use in-place copy-constructors. For example this is a simple container that does this and can be used with non-copy-assignable types: `template class MyContainer { Data data[10]; int cpt = 0; public: void set(int i, Data const & d) { new (&data[i]) Data(d); } Data const & get(int i) const { return data[i]; } };` – S. K. Oct 12 '16 at 20:38
@S.K. You have to destroy first or you just leaked whatever `Data` owned. Regardless, destroy + reconstruct can be considerably more expensive than assignment. The designers sensibly decided not to pessimize everyone else's code for some pathological corner cases. – T.C. Oct 12 '16 at 20:45
@T.C. You are right about the need for destruction. I understand the performance issue, but I still think that, for example, being unable to use std::priority_queue on non-copy-assignable data because it internally tries to copy the data (something that does not concern me as a user and does not fall under my control) is either bad implementation or a design flaw. – S. K. Oct 12 '16 at 21:41

score 1 · Answer 2 · edited Oct 12 '16 at 20:33

Problem

Let's look at your error more deeply:

error: assignment of read-only member ‘std::pair::first’

Solution

There is no solution to this! As you can see here, there is a member that is only in read mode.

 std::priority_queue<std::pair<const int, int>> pq;

Here you can see const int. Well, the const modifier makes it so that the variable can be only in read mode and can't be changed! That's your problem here. If you try to assign a constant, well this results in an error because your attempting to change a constant while it is in only READ mode.

References

cpprefrence

Why std::pair does not work with some STL containers?

2 Answers2

Problem

Solution

References