Question posted in 
Multiple std::map.insert()’s using the same std::pair but with new values results in incorrect map values. How can I use a single struct and references without creating this behavior?
#include <iostream> // c++17 gcc 8.3.0-6 debian
#include <map>
#include <tuple>
using std::endl, std::cout, std::cerr;
struct Struct1 {
int s1_int1 {}, s1_int2 {};
std::string s1_str1 {};
struct Key {
decltype (s1_int1) & key_part1;
decltype (s1_int2) & key_part2;
} key { s1_int1, s1_int2 };
struct Value {
decltype (s1_str1) & value_part1;
} value { s1_str1 };
struct Compare {
bool operator()( Key const & lhs, Key const & rhs) const {
return std::tie( lhs.key_part1, lhs.key_part2 ) < std::tie( rhs.key_part1, rhs.key_part2 );
}
};
void print (std::string message) const {
cerr<<message<<">> s1_int1:"<< s1_int1<<", s1_int2:"<<s1_int2<<", s1_str1:"<<s1_str1<<endl;
}
};
void r_print( std::pair<Struct1::Key,Struct1::Value> const & pair, bool is_inserted ) {
cerr<<"is_inserted:"<<is_inserted<<", key.key_part1:"<<pair.first.key_part1<<", key.key_part2:"<<pair.first.key_part2<<", value.s1_str1:"<<pair.second.value_part1<<endl;
};
int main()
{
std::map<Struct1::Key, Struct1::Value, Struct1::Compare > my_map {};
Struct1 map_value1 {11,12,"s13"}, map_value2 = {21,22,"s23"};
map_value1.print("map_value :12");
auto const r1 = my_map.insert( {map_value1.key,map_value1.value} );
r_print( *r1.first, r1.second );
for (auto & [key,value]:my_map )
cerr<< "key.key_part1:"<<key.key_part1<<", key.key_part2:"<<key.key_part2<<", value.s1_str1:"<<value.value_part1<<endl;
map_value2.print("map_value2:22");
auto const r2 = my_map.insert( {map_value2.key,map_value2.value} );
r_print( *r2.first, r1.second );
for (auto & [key,value]:my_map )
cerr<< "key.key_part1:"<<key.key_part1<<", key.key_part2:"<<key.key_part2<<", value.s1_str1:"<<value.value_part1<<endl;
map_value1.s1_int1 = 31; map_value1.s1_int2 = 32; map_value1.s1_str1 = "s33";
map_value1.print("map_value :31");
auto const r3 = my_map.insert( {map_value1.key,map_value1.value} );
r_print( *r3.first, r1.second );
for (auto & [key,value]:my_map )
cerr<< "key.key_part1:"<<key.key_part1<<", key.key_part2:"<<key.key_part2<<", value.s1_str1:"<<value.value_part1<<endl;
cout << "###" << endl;
return 0;
}
In the output note how the map is built and then broken on the last insert due to the re-use of map_value1. I must be misunderstanding std::map, or something beyond that.
I think I partially understand why this may be occurring since the map is apparently not making a copy. But I have not observed this behavior when using std::vector.push_back(). As I read the cppreference entries for those member functions, I don’t see how the descriptions would inform me of the different behavior. Also I presume the c++ containers would offer similar behavior in the creation of container elements.
A simple answer some might suggest is to not make use of references in Struct1::Key, however I’m trying to have the top level data members be both easily accessible in the struct and also to easily create the pair for insertion into the std::map.
I suppose I could force a copy somehow, which is what I’m trying to avoid by using references. Or create an “new” variable for every insertion, but that seems unnecessary and might cause memory leaks or dangling pointers if done incorrectly (an error I could quite easily make).
The overall goal is to create in-memory database-like functionality.
I appreciate any insights you can offer.
Output:
map_value :12>> s1_int1:11, s1_int2:12, s1_str1:s13
is_inserted:1, key.key_part1:11, key.key_part2:12, value.s1_str1:s13
key.key_part1:11, key.key_part2:12, value.s1_str1:s13
map_value2:22>> s1_int1:21, s1_int2:22, s1_str1:s23
is_inserted:1, key.key_part1:21, key.key_part2:22, value.s1_str1:s23
key.key_part1:11, key.key_part2:12, value.s1_str1:s13
key.key_part1:21, key.key_part2:22, value.s1_str1:s23
map_value :31>> s1_int1:31, s1_int2:32, s1_str1:s33
is_inserted:1, key.key_part1:31, key.key_part2:32, value.s1_str1:s33
key.key_part1:31, key.key_part2:32, value.s1_str1:s33
key.key_part1:21, key.key_part2:22, value.s1_str1:s23
key.key_part1:31, key.key_part2:32, value.s1_str1:s33
###
2
Answers
It turns out that std::map requires value_types. I had references to values. To fix it I simply exchanged the references with the referenced values. Now the key and value are no longer references. There may well be a better explanation for the exact problem, but I don't really know it.
output:
It boils down to this:
Demo
You have a structure that contains “normal” members and reference members. The (implicitly defined) default constructor, as well as aggregate initialization, initialize the latter to refer to the former. You appear to assume that the latter are, or should be, always initialized to refer to the former – but that’s not the case. This structure also has an implicitly defined copy constructor, and that one performs member-wise copy – non-reference members of the copy get the same value as non-reference members of the original, while reference members of the copy are initialized to refer to the same objects as reference members of the original.
In my example, first
s1is initialized withs1.m == 42ands1.rreferring tos1.m. Thens2is copy-initialized from it; the result is thats2.rrefers tos1.m, nots2.m. Thens1.mis modified, ands2.rdutifully reflects this modification.Same thing happens with your
Struct1and, perhaps more importantly,Struct1::Key. The structure is copied into the map, and the reference members in the copy end up referring to the non-reference members in the original, not the copy. Then by updating members in the original, you effectively modify the key in the copy, at which point your program exhibits undefined behavior – the map relies on ordering of keys to be stable, and instead you are reordering them right under its feet.It’s not clear how to salvage your approach, and frankly, it doesn’t seem worth salvaging. You appear to believe that references are free, but in fact references are typically implemented as pointers underneath. A pair of references would likely use as much, or more, memory than a pair of ints (print
sizeof(Struct1)and2*sizeof(int) + sizeof(std::string); that might prove illuminating). You are not saving anything by copying references over if you just copied ints, but you are introducing major headaches.