Thread: Inserting into vector in map of string and vector<string>

Originally Posted by tabstop

Let's say you have 26 strings (for convenience, a_map_s_v_s["a"] through a_map_s_v_s["z"]). You will have to create 26 vectors of strings to be mapped to, regardless of what approach you make. You've got approach 1:

Code:

vector<string> empty_vector;
not-really-for (key = "a"; key <= "z"; key[0]++) {
    a_map_s_v_s.insert(pair(key, empty_vector));
}
//then for every key, value
a_map_s_v_s[key].push_back(value_string)

Now approach 1 has a sub-approach 1a that I wouldl have to poke through the standard to see if it works, which is simply

Code:

//then for every key, value
a_map_s_v_s[key].push_back(value_string)

trusting that if key hasn't been used before, a freshly-made sparkly-new vector<string> is handed to you at that time by the [] operator. If this works, and I suspect it will, then that makes this version look a lot more awesome.

Well, after iMalc's post which I quoted, I kind of assumed that using approach 1 wouldn't actually require a call to map::insert(). In other words, you might rewrite your code to say the following instead:

Code:

/* This no longer needed
vector<string> empty_vector;

not-really-for (key = "a"; key <= "z"; key[0]++) {
    a_map_s_v_s.insert(pair(key, empty_vector));
}
*/
//then for every key, value
a_map_s_v_s[key].push_back(value_string)

i.e. because the [] operator will insert an element to the map if "key" doesn't already exist, and hence you can then immediately access the vector<string> object associated with "key", and use the member selector operator to access that vector's push_back() method which you can then use to add a string to said vector.

Approach 2 isn't that different from approach 1, really:
[code]

Code:

not-really-for (key = "a"; key <= "z"; key[0]++) {
    vector<string> empty_vector;
    //for all the values that go with this key
    empty_vector.push_back(value);
    a_map_s_v_s.insert(pair(key, empty_vector));
}

You would have to know all the end-result strings in one place, though.

Agreed. I'm wondering now which approach would work best in my situation. Its not a whole lot of difference, if you re-use the same vector<string> in approach 2 for every new string/vector<string> combination you want to create in the map, but it would save me from having to create a named vector<string> object if I use approach 1 (that is, if my assumption was accurate), and hence, less variable names I need to keep track of in my code. Also, with approach 2, you might still end up needing to use approach 1 if you needed to change something in the vector contained within the map after you already inserted it into the map. But I guess I'll decide once I start coding on this project again, which should be in the next couple of days.

Originally Posted by tabstop

Keep in mind that

Code:

a_map_s_v_s["hello"].push_back("world");

is doing nothing to the map. You're adding to the vector a_map_s_v_s["hello"], and therefore you need to be looking at vector::insert, which requires a position to insert into (because vectors are like that -- the ordering has to come from you, not from within).

The suggestion was to build the vector first, then insert the key,value pair, something like

Code:

vector<string> bunch_o_strings;
bunch_o_strings.push_back("one");
bunch_o_strings.push_back("two");
bunch_o_strings.push_back("three);
bunch_o_strings.push_back("world");
a_map_s_v_s.insert(pair("hello", bunch_o_strings));

It might be make_pair instead of pair, because I just typed that into this little box and didn't test it.

Well actually it's inserting an empty vector into the map if the key value "hello" doesn't currently exist in the map, thus no insert is necessary.

I would actually avoid building a vector, and then using insert, because that results in the copying of the vector (in fact potentially twice; Once in building the pair, and once upon inserting that pair).
An improvement would be:

Code:

vector<string> bunch_o_strings;
bunch_o_strings.push_back("one");
bunch_o_strings.push_back("two");
bunch_o_strings.push_back("three");
bunch_o_strings.push_back("world");
a_map_s_v_s["hello"].swap(bunch_o_strings);

The [] operator of the map creates an empty vector and returns that by reference. The vector has a swap method and we use this to exchange the contents of bunch_o_strings and the new empty vector, in constant time. This has the possible added bonus that if there was actually something already mapped from "hello" then it will now be in bunch_o_strings (which might be useful behaviour).
Take a moment to wrap your head around that....

Another possibly even better alternative is to get a reference to the actual vector inside the map (creating it if necessary) and inserting directly into that:

Code:

vector<string> &bunch_o_strings = a_map_s_v_s["hello"];
bunch_o_strings.push_back("one");
bunch_o_strings.push_back("two");
bunch_o_strings.push_back("three");
bunch_o_strings.push_back("world");

This has the possible advantage that if "hello" is already mapped, then all you end up doing is appending further strings into its mapped vector.

insert certainly can be useful at times, but it has negligible advantage here imho.

Originally Posted by iMalc

Another possibly even better alternative is to get a reference to the actual vector inside the map (creating it if necessary) and inserting directly into that:

Code:

vector<string> &bunch_o_strings = a_map_s_v_s["hello"];
bunch_o_strings.push_back("one");
bunch_o_strings.push_back("two");
bunch_o_strings.push_back("three");
bunch_o_strings.push_back("world");

This has the possible advantage that if "hello" is already mapped, then all you end up doing is appending further strings into its mapped vector.

But doesn't approach 1 do this as well (that is, the bolded part)?

Originally Posted by Programmer_P

But doesn't approach 1 do this as well (that is, the bolded part)?

If approach 1 is coming from tabstop's earlier posts with different approaches, then that is rather the point. All he does is insert empty vectors which is what would happen anyway per a_map_s_v_s["hello"] if "hello" is new. You want to use insert for basically two reasons: to note whether insertion fails or succeeds, and also if it fails, so you can preserve the original value. The operator[] will just create or overwrite key, value pairs. Except, push_back is not really an operation for vectors that overwrites anyway so you are not in danger of changing keys unexpectedly.

I interpreted your post, at first, to mean the difference between the reference to map["hello"] method, and the vector building method which iMalc implemented, and had this to say about that:

No, and a small example could prove it:

Code:

#include <vector>
#include <string>
#include <map>
#include <iostream>
using namespace std;
void wysiwyg(map<string, vector<string> > &the_map)
{
    for(map<string, vector<string> >::iterator i = the_map.begin(); i != the_map.end(); ++i) {
        cout << i->first << " ->\n\t";
        for(vector<string>::iterator j = i->second.begin(); j != i->second.end(); ++j) {
            cout << *j << ", ";
        }
        cout << '\n';
    }
}
void foo(map<string, vector<string> > &the_map)
{
    vector<string> bunch_o_strings;
    bunch_o_strings.push_back("one");
    bunch_o_strings.push_back("two");
    bunch_o_strings.push_back("three");
    bunch_o_strings.push_back("world");
    the_map["hello"].swap(bunch_o_strings);
    wysiwyg(the_map);
}
void bar(map<string, vector<string> > &the_map)
{
    vector<string> &bunch_o_strings = the_map["hello"];
    bunch_o_strings.push_back("one");
    bunch_o_strings.push_back("two");
    bunch_o_strings.push_back("three");
    bunch_o_strings.push_back("world");
    wysiwyg(the_map);
}
int main()
{
    map<string, vector<string> > a_map_s_v_s;
    foo(a_map_s_v_s);
    bar(a_map_s_v_s);
    foo(a_map_s_v_s);
}

#if 0
My output:

hello ->
        one, two, three, world,
hello ->
        one, two, three, world, one, two, three, world,
hello ->
        one, two, three, world,
#endif

If you were right then we would have " one, two, three, world, one, two, three, world, one, two, three, world," at the end, but we swap in the new vector that map["hello"] points to in the foo function. The swap behavior is either right or wrong like iMalc said.

Originally Posted by whiteflags

If approach 1 is coming from tabstop's earlier posts with different approaches, then that is rather the point. All he does is insert empty vectors which is what would happen anyway per a_map_s_v_s["hello"] if "hello" is new.

Oops. Actually, I was talking about my modified version of tabstop's approach 1, which looks like this:

Code:

/* This no longer needed
vector<string> empty_vector;

not-really-for (key = "a"; key <= "z"; key[0]++) {
    a_map_s_v_s.insert(pair(key, empty_vector));
}
*/
//then for every key, value
a_map_s_v_s[key].push_back(value_string)

which is based off the assumption (which is hopefully correct) that using the [] operator with such a map followed by the vector::push_back() method will not create a new vector<string> object as the mapped value associated with "key" if "key" already exists in said map, but will instead just access it, and push_back() the string you pass as "value_string". And of course, if key doesn't already exist in map, it will automatically create a new vector<string> object which can then be immediately accessed for push_back() or any other vector operations.

You want to use insert for basically two reasons: to note whether insertion fails or succeeds, and also if it fails, so you can preserve the original value.

It doesn't appear like map::insert() can be used for adding strings to a vector<string> mapped value inside a map. I was thinking maybe it could since Bubba suggested using insert instead of the [] operator, but I don't think it can be used for this type of operation.

The operator[] will just create or overwrite key, value pairs. Except, push_back is not really an operation for vectors that overwrites anyway so you are not in danger of changing keys unexpectedly.

I'm sorry. I didn't quite get that. If you're saying using the [] operator followed by push_back with the vector<string> object associated with the key you passed to [] will cause the vector<string> object to be recreated if key already exists in map, then why did you say "you are not in danger of changing keys unexpectedly"? Wouldn't it overwrite the key as well as the mapped value of the map if the [] operator overwrites elements in the map if key already exists, and hence, cause the key to "change" (unexpectedly || expectedly) ?

EDIT: Just re-read the map::operator[] reference at:

operator[] - C++ Reference

and learned that it has the expected behavior (my assumption was correct): if key already exists in map, then it will return a reference to its mapped value. It will not replace ("overwrite") the key or mapped value, thus it does indeed have the same effect as iMalc's bolded part of his post which I quoted.

I interpreted your post, at first, to mean the difference between the reference to map["hello"] method, and the vector building method which iMalc implemented, and had this to say about that:

No, and a small example could prove it:

Code:

#include <vector>
#include <string>
#include <map>
#include <iostream>
using namespace std;
void wysiwyg(map<string, vector<string> > &the_map)
{
    for(map<string, vector<string> >::iterator i = the_map.begin(); i != the_map.end(); ++i) {
        cout << i->first << " ->\n\t";
        for(vector<string>::iterator j = i->second.begin(); j != i->second.end(); ++j) {
            cout << *j << ", ";
        }
        cout << '\n';
    }
}
void foo(map<string, vector<string> > &the_map)
{
    vector<string> bunch_o_strings;
    bunch_o_strings.push_back("one");
    bunch_o_strings.push_back("two");
    bunch_o_strings.push_back("three");
    bunch_o_strings.push_back("world");
    the_map["hello"].swap(bunch_o_strings);
    wysiwyg(the_map);
}
void bar(map<string, vector<string> > &the_map)
{
    vector<string> &bunch_o_strings = the_map["hello"];
    bunch_o_strings.push_back("one");
    bunch_o_strings.push_back("two");
    bunch_o_strings.push_back("three");
    bunch_o_strings.push_back("world");
    wysiwyg(the_map);
}
int main()
{
    map<string, vector<string> > a_map_s_v_s;
    foo(a_map_s_v_s);
    bar(a_map_s_v_s);
    foo(a_map_s_v_s);
}

#if 0
My output:

hello ->
        one, two, three, world,
hello ->
        one, two, three, world, one, two, three, world,
hello ->
        one, two, three, world,
#endif

If you were right then we would have " one, two, three, world, one, two, three, world, one, two, three, world," at the end, but we swap in the new vector that map["hello"] points to in the foo function. The swap behavior is either right or wrong like iMalc said.

If I was right about what? Your code appears to have the expected results:

The first foo() call adds the strings "one", "two", "three", and "world" to the vector<string> mapped value object associated with the "hello" key inside the map you created in int main.
The call to wysiwyg() inside foo() simply outputs the contents of the maps, hence producing the output:

hello ->
one, two, three, world,

like you said.
The call to bar() operates on the same map you passed to foo(), and simply adds an identical set of strings to that vector<string> object, and then outputs the contents of the map by another call to wysiwyg(), hence why the content of the vector<string> mapped value object which was outputted in the first call to that function is simply doubled in the second call.
Then the second call to foo() swapped the contents of the vector<string> object of the map which you passed with the same thing that was outputted the first time foo() and then wysiwyg() was called, since foo() creates a new local vector<string> object each time it is called, adds to it the strings "one", "two", "three", and "world", then swaps the content of the map's vector<string> with that local vector<string>.

I'm not surprised by the behavior of your code, and I'm not sure what you thought you were correcting me on, no offense.

Actually, I was talking about my modified version of tabstop's approach 1, which looks like this:

Good. We are talking about the same piece of code. I maintain that there is no substantial difference between using insert and operator[] -- which is your question -- because you do not need any of the protection which insert offers. Here's why:

I'm sorry. I didn't quite get that. If you're saying using the [] operator followed by push_back with the vector<string> object associated with the key you passed to [] will cause the vector<string> object to be recreated if key already exists in map, then why did you say "you are not in danger of changing keys unexpectedly"?

Normally map's operator[] is used in this manner:

Code:

map[key] = value;

Now let's go into specifics, where the value is a vector. Let's assume that the entire vector is important then. vector::operator= does something like this:

Code:

return vector(rhs).swap(*this);

It is not map::operator= here, because map::operator[] performs the value access. The effect is that the whole vector is replaced.

The push_back operation does not have the semantics of assignment. Instead, the vector is extended by one element. Taking that into account, map::operator[] does everything insert would do in any case for key: return the vector which the key points to. You would have to drop the vector itself to lose all of the values.

The take-away here is that the only benefit you get from inserting empty vectors into the map is perceived clarity.

An aside: I don't want to say maps with vector things in them are strange, but if this is just your way of getting a key to access many values, a multimap may suffice.

Originally Posted by http://www.cplusplus.com/reference/stl/multimap/

Multiple-key map
Maps are a kind of associative containers that stores elements formed by the combination of a key value and a mapped value, much like map containers, but allowing different elements to have the same key value.

Take it or leave it. :shrug:

If I was right about what? I'm not surprised by the behavior of your code, and I'm not sure what you thought you were correcting me on, no offense.

By "if you were right" I was answering your question in an inappropriate context, where I thought you were asserting that the results of foo() and bar() would be the same. It turned out to be more trouble than it was worth to keep that around. The topical portion of my post actually was written later, when I understood you were referring to tabstop's code instead of iMalc's.

Originally Posted by Bubba

..which is a very good reason for using insert.

Except like already mentioned, map::insert() wont let you operate on a vector<string> mapped value inside the map...

Originally Posted by Programmer_P

Except like already mentioned, map::insert() wont let you operate on a vector<string> mapped value inside the map...

Not true, insert returns a pair<iterator , bool>, which means pair.first->second is your vector.

Originally Posted by whiteflags

Not true, insert returns a pair<iterator , bool>, which means pair.first->second is your vector.

Yeah, but that approach looks like this:

Code:

#include <iostream>
#include <vector>
#include <map>
#include <string>

using namespace std;

int main() {

  typedef vector<string> vector_str_t;
  map<string, vector_str_t> a_map;
  typedef map<string, vector_str_t>::iterator it_t;
  string str = "A String";
  vector<string> vct;
  pair<it_t, bool> pr = a_map.insert(make_pair(str, vct));
  pr.first->second.push_back("#1");
  pr.first->second.push_back("#2");
  pr.first->second.push_back("#3");
  str = "A String 2";
  pair<it_t, bool> pr2 = a_map.insert(make_pair(str, vct));
  pr2.first->second.push_back("#4");
  pr2.first->second.push_back("#5");
  pr2.first->second.push_back("#6");
  str = "A String 3";
  pair<it_t, bool> pr3 = a_map.insert(make_pair(str, vct));
  pr3.first->second.push_back("#7");
  pr3.first->second.push_back("#8");
  pr3.first->second.push_back("#9");
  
  for (it_t it = a_map.begin(); it != a_map.end(); it++) {
       cout<< "Current element of map:\n\n"
                << "Key contains: " << it->first << endl;
       cout<< "Mapped value contains: ";
       vector<string> vct = it->second;
       for (unsigned int i = 0; i < vct.size(); i++) {
            if (i != 0) 
                cout<< "\t\t       ";
            cout<< vct.at(i) <<endl;
       }
  }

   return 0;

}

Code result: C++ code - 44 lines - codepad

while to do the equivalent thing with the map:perator[], one only has to do this:

Code:

#include <iostream>
#include <vector>
#include <map>
#include <string>

using namespace std;

int main() {

  typedef vector<string> vector_str_t;
  map<string, vector_str_t> a_map;
  a_map["A String"].push_back("#1");
  a_map["A String"].push_back("#2");
  a_map["A String"].push_back("#3");
  a_map["A String 2"].push_back("#4");
  a_map["A String 2"].push_back("#5");
  a_map["A String 2"].push_back("#6");
  a_map["A String 3"].push_back("#7");
  a_map["A String 3"].push_back("#8");
  a_map["A String 3"].push_back("#9");
  
  typedef map<string, vector_str_t>::iterator it_t;
  for (it_t it = a_map.begin(); it != a_map.end(); it++) {
       cout<< "Current element of map:\n\n"
                << "Key contains: " << it->first << endl;
       cout<< "Mapped value contains: ";
       vector<string> vct = it->second;
       for (unsigned int i = 0; i < vct.size(); i++) {
            if (i != 0) 
                cout<< "\t\t       "; 
            cout<< vct.at(i) <<endl;
       }
       cout<<endl;
  }

   return 0;

}

Code result: C++ code - 38 lines - codepad

As you can see, not only is using the [] operator a lot more cleaner and easier to understand, it provides immediate access and alteration to the vector<string> mapped value object, and you don't have to create a named vector<string> object before inserting into the map. Also, map::insert() doesn't actually provide the access to the vector<string> mapped value (or at least, not directly). pair<mapIteratorType, bool> objectName does, which makes my earlier statement (or at least, what I really meant by it) still true.

Originally Posted by Programmer_P

As you can see, not only is using the [] operator a lot more cleaner and easier to understand, it provides immediate access and alteration to the vector<string> mapped value object, and you don't have to create a named vector<string> object before inserting into the map.

The immediate access is an illusion though: operator[] has the same complexity as insert, i.e., it runs in logarithmic time. You probably could avoid this with something like:

Code:

vector_str_t& batch1 = a_map["A String"];
batch1.push_back("#1");
batch1.push_back("#2");
batch1.push_back("#3");

This effectively does the same thing as in the former example, but with different syntax.

By the way, if you were trying to use the number of lines to emphasize your point: you could have reduced the former example by 3 lines by simply not using the str variable. The difference is negligible. There is a difference in readability, but it is not that hard anyway.

EDIT:
Incidentally, I just realised that you stated that with operator[] "you don't have to create a named vector<string> object before inserting into the map". This is true, but it is true of the former example too. The vct variable (which could have been declared const) was just for readability.

Originally Posted by laserlight

The immediate access is an illusion though: operator[] has the same complexity as insert, i.e., it runs in logarithmic time. You probably could avoid this with something like:

Code:

vector_str_t& batch1 = a_map["A String"];
batch1.push_back("#1");
batch1.push_back("#2");
batch1.push_back("#3");

This effectively does the same thing as in the former example, but with different syntax.

Does this approach really make the operation of adding strings to a vector<string> mapped value object inside the map any faster? It looks to me like that's just another way of writing:

Code:

a_map["A String"].push_back("#1");
a_map["A String"].push_back("#2");
a_map["A String"].push_back("#3");

since the operator [] returns a reference to the mapped value that was just inserted (or if key already existed, a reference to the mapped value that's associated with key), which is why .push_back("whatever")) directly following that operator works. So the only difference with your code is that a new named reference is created, then used to access the vector<string> mapped value. So if anything, I would think your code would actually run slower (IF there's any noticeable difference at all).

By the way, if you were trying to use the number of lines to emphasize your point: you could have reduced the former example by 3 lines by simply not using the str variable. The difference is negligible. There is a difference in readability, but it is not that hard anyway.

Oops. You caught me. That is indeed what I was "trying" (scratch that - "actually") doing: using the number of lines to emphasize my point. And yes, I noticed that the str variable could be omitted from my first example code, and make it 3 lines shorter, which would bring it to 41 lines, as opposed to 38 lines, which is how long the second example is. But still, even with the str variable omitted, that's still a 3:1 ratio of difference between the two approaches, which can add up if you have a lot of map<string, vector_str_t>s (like I'm going to have in the class I'm writing right now).

EDIT:
Incidentally, I just realised that you stated that with operator[] "you don't have to create a named vector<string> object before inserting into the map". This is true, but it is true of the former example too. The vct variable (which could have been declared const) was just for readability.

Can you please provide example code for the statement you just pronounced as fact?
I do not see how you can use insert() without passing a named vector<string> object to the second parameter of make_pair() if the map is a map<string, vector_str_t>.

Does this approach really make the operation of adding strings to a vector<string> mapped value object inside the map any faster?

Yes. As you were told, both operator[] and insert run in logarithmic time, so performing that access once and saving the location of the value, you can do some things in constant time as opposed to a recurring logarithmic time.

Further, map[key] has the same affect of map.insert(make_pair( key, value_type() )).first->second. So you could write:

Code:

vector_str_t& batch1 = a_map.insert( make_pair( string("A String"), vector_st_t() )).first->second;
batch1.push_back("#1");
batch1.push_back("#2");
batch1.push_back("#3");

They have the exact same performance cost.

The value in preferring insert is that the bool it returns in the pair let's you know whether insert was successful. Careful use prevents you from overwriting values mistankenly, as in map[key] = value;

In this particular case, we're discussing the benefits of syntactic sugar, unless you can think of a use case for insert's bool.

Originally Posted by Programmer_P

Can you please provide example code for the statement you just pronounced as fact?
I do not see how you can use insert() without passing a named vector<string> object to the second parameter of make_pair() if the map is a map<string, vector_str_t>.

For example:

Code:

pair<it_t, bool> pr = a_map.insert(make_pair("A String", vector_str_t()));
pr.first->second.push_back("#1");
pr.first->second.push_back("#2");
pr.first->second.push_back("#3");

You can actually see it used in whiteflags' canonical example of how operator[] would be implemented with insert.

Originally Posted by whiteflags

The value in preferring insert is that the bool it returns in the pair let's you know whether insert was successful. Careful use prevents you from overwriting values mistankenly, as in map[key] = value;

Indeed, but as there was no check for a failed (i.e., attempted duplicate) insertion, it was not very useful anyway, heh.

Originally Posted by whiteflags

Yes. As you were told, both operator[] and insert run in logarithmic time, so performing that access once and saving the location of the value, you can do some things in constant time as opposed to a recurring logarithmic time.

Further, map[key] has the same affect of map.insert(make_pair( key, value_type() )).first->second. So you could write:

Code:

vector_str_t& batch1 = a_map.insert( make_pair( string("A String"), vector_st_t() )).first->second;
batch1.push_back("#1");
batch1.push_back("#2");
batch1.push_back("#3");

They have the exact same performance cost.

Ahh..ok. I get it. I probably will use the reference approach then, though I'm going to do it with the [] operator, not insert, since its easier to type and read.

The value in preferring insert is that the bool it returns in the pair let's you know whether insert was successful. Careful use prevents you from overwriting values mistankenly, as in map[key] = value;

In this particular case, we're discussing the benefits of syntactic sugar, unless you can think of a use case for insert's bool.

Yes, that's true. But the reason I didn't do anything with the bool part of the pair which was returned by insert was because its irrelevant. I don't need to check its value with map<string, vector_str_t>s because I would not be using the syntax:

map[key] = value;

unless I was doing it on purpose to replace the existing vector<string> mapped value object, and if I was doing it on purpose, it doesn't matter that "key" already existed in map, since we're replacing the vector<string> its associated with intentionally, hence there's no reason to check the value of the bool. The syntax:

map[key].push_back(string);

will just add a string to the existing vector<string> mapped value object if key already exists, and if key doesn't already exist, a new element with key and a vector<string> mapped value object will be created, so the element will only be created once.