20

I'm trying to copy a map into a vector of pair, so I can then sort the vector by the second data member of the pairs. I have resolved this doing like this:

void mappedWordsListSorter(){
  for (auto itr = mappedWordsList.begin(); itr != mappedWordsList.end(); ++itr){
    vectorWordsList.push_back(*itr);
  }
  sort(vectorWordsList.begin(), vectorWordsList.end(), [=](pair<string, int>& a, pair<string, int>& b){return a.second > b.second;});
}

I need to find a way to do this without using a raw loop, using the standard library instead. I have come across a lot of examples doing this by only transferring either the keys or the values of the map. I need to copy into a vector of pairs<string, int>. What is the best way to do it?

Deduplicator
  • 44,692
  • 7
  • 66
  • 118
Victor
  • 201
  • 2
  • 3
  • 1
    @Lorand - The sort happens on the `second` item in the pair, which is not the key. – StoryTeller - Unslander Monica Dec 19 '18 at 15:37
  • 1
    @Lorand It seems that OP wants to perform the sort based on the values, not the keys. – JFMR Dec 19 '18 at 15:38
  • Exact duplicate, I think. https://stackoverflow.com/questions/684475 – Drew Dormann Dec 19 '18 at 15:39
  • 3
    Seems like that question should be flagged as a duplicate of this one, since the answer provided by @NathanOliver is way better than any of the answers to that question. Edit : Though that question includes sorting the result. – François Andrieux Dec 19 '18 at 15:40
  • @FrançoisAndrieux I agree, these answers are much higher quality. Is there precedent for flagging an old question as a duplicate of a new one? **Edit**: [There is.](https://meta.stackoverflow.com/questions/251938) I have marked the older question as a duplicate. The answers seemed to be of poorer quality. – Drew Dormann Dec 19 '18 at 15:41
  • Note: when you pass lambda write `[]` instead of `[=]` - the way you use it, it technically causes a huge performance blunder as it passes all available variables by copy (in Release compling it should factor out unnecessary copying, but it might destroy Debug runtime). – ALX23z Dec 19 '18 at 15:43
  • @DrewDormann I don't think there's anything about flagging duplicates that says newer questions have to be the ones that point to older ones. But I'm not confident enough with site policy to do it myself, I might have missed something. – François Andrieux Dec 19 '18 at 15:46
  • 1
    @ALX23z - I agree that `[=]` should not be present. But just because it's there doesn't mean *everything* gets copied. The lambda has to *use* something from the surrounding scope to capture it. – StoryTeller - Unslander Monica Dec 19 '18 at 15:46
  • 1
    @ALX23z Actually, it will only copy a variable is you use it in the lambda body. There is no performance penalty to use `[=]` if you don't use any of the variables in scope. – NathanOliver Dec 19 '18 at 15:46

3 Answers3

26

Just use std::vector's assign member function.

//no need to call reserve, bidirectional iterators or better will compute the size and reserve internally.
vectorWordsList.assign(mappedWordsList.begin(), mappedWordsList.end());

If you have existing values in the vector that you don't want overwritten then use insert instead like

vectorWordsList.reserve(vectorWordsList.size() + mappedWordsList.size()); // make sure we only have a single memory allocation
vectorWordsList.insert(vectorWordsList.end(), mappedWordsList.begin(), mappedWordsList.end());
NathanOliver
  • 171,901
  • 28
  • 288
  • 402
  • 1
    I would hope that `assign` would essentially `reserve` internally. – François Andrieux Dec 19 '18 at 15:41
  • 10
    @FrançoisAndrieux It most likely would if you passed random access iterators but since `map` has bidirectional iterators it requires a traversal to known how many elements to allocate space for so it isn't going to do that. – NathanOliver Dec 19 '18 at 15:43
  • 1
    @NathanOliver libstdc++ actually does essentially `reserve` internally. For any ForwardIterator, it will call `std::distance`, paying for a traversal for anything less than a RandomAccessIterator. You can trace [`std::vector::assign`](https://github.com/gcc-mirror/gcc/blob/2e0303d60a97ddfcdd8340184bb5dc45e0433327/libstdc%2B%2B-v3/include/bits/stl_vector.h#L719) to [here](https://github.com/gcc-mirror/gcc/blob/2e0303d60a97ddfcdd8340184bb5dc45e0433327/libstdc%2B%2B-v3/include/bits/vector.tcc#L289). – Justin Dec 19 '18 at 19:43
  • 1
    @Justin Cool. Thanks for finding that. I still like to be explicit, in case other implementations don't do this. – NathanOliver Dec 19 '18 at 19:47
  • Putting a `.resize(0)` before `.reserve()` might be an optimization if the elements should be replaced. – Deduplicator Dec 19 '18 at 20:46
  • Since `assign` doesn't require MoveInsertable if the iterator is forward or stronger, it must reserve and mustn't reallocate when given such iterators. Additionally, for the second case, `reserve` is an antipattern (it prevents exponential growth and can lead to quadratic behavior). – T.C. Dec 20 '18 at 11:58
  • `reserve` is still not advisable in the second case unless you know that you are not extending the vector further. If I run the second code fragment in a loop, it would reallocate *every iteration*, whereas if I just used `insert` without `reserve`, the exponential growth behavior would kick in and you'll only reallocate O(logN) times. Moreover, high quality implementations should pre-compute the size of the inserted range when given forward or stronger iterators, so the `reserve` provide no actual benefit. – T.C. Dec 21 '18 at 01:14
10

It's worth noting that if you are creating a vector for this purpose, you may use the vector's constructor directly:

std::vector<std::pair<FirstType,SecondType>> vectorWordsList( mappedWordsList.begin(), mappedWordsList.end() );

In C++17, you may also omit the vector's template arguments to have the compiler deduce them:

std::vector vectorWordsList( mappedWordsList.begin(), mappedWordsList.end() );
Drew Dormann
  • 59,987
  • 13
  • 123
  • 180
7

You can use std::copy and std::back_inserter:

std::copy(mappedWordsList.begin(), 
          mappedWordsList.end(), 
          std::back_inserter(vectorWordsList));

Honestly, I think that a range-for loop is clearer:

for(const auto& kv : mappedWordsList) 
     vectorWordsList.emplace_back(kv);

Regardless, you can use std::vector::reserve to preallocate memory on your target vector, avoiding unnecessary reallocations.

Vittorio Romeo
  • 90,666
  • 33
  • 258
  • 416