Member Avatar for Clockowl

Hi guys,

What am I doing wrong here? Program dies on me @ merge(). :(

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int afrom[4] = {0,0,1,2};
    int ato[4] = {1,2,3,4};
    vector<int> from(&afrom[0], &afrom[4]);
    vector<int> to(&ato[0], &ato[4]);
    vector<int> length;

    vector<int> all_nodes;
    sort(from.begin(), from.end());
    sort(to.begin(), to.end());
    merge(from.begin(), from.end(), to.begin(), to.end(), all_nodes.begin());

    return 0;
}

Thanks in advance,

  • 2 Contributors
  • 3 Replies
  • 136 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by Clockowl

Dani AI

Generated

Short diagnosis: std::merge writes to whatever output iterator you pass it. In the original snippet passed all_nodes.begin() while all_nodes had size 0, so the algorithm attempted to write through an iterator that was not dereferenceable — undefined behavior and a crash. was correct to point out that the destination must provide valid storage or be an inserter that appends.

Practical fixes:

  • Pre-size the destination so its elements exist before calling merge (then begin() is valid).
  • Use an output inserter that appends to the container, and optionally call reserve beforehand to avoid repeated reallocations.
  • Or collect everything into one container and use inplace_merge if that fits the design.

Key cautions and tips:

  • reserve does not create elements; it only increases capacity. Writing via begin() still requires that the vector’s size be large enough (resize or construct with size).
  • Both input ranges must be sorted with the same comparator before calling merge.
  • If a unique union is desired (no duplicates), use std::set_union or remove duplicates after merging.
  • When hunting similar crashes, enable checked iterators or run sanitizers (AddressSanitizer or the debug mode of the standard library) to catch out-of-bounds writes early.

Reference: details and guarantees for std::merge are documented at std::merge.

Recommended Answers

All 3 Replies

Member Avatar for Clockowl

Ugh. Nevermind. Forgot to allocate. That's sooooooooo C. xD

(Correct?) Working code:

int main() {
    int afrom[4] = {0,0,1,2};
    int ato[4] = {1,2,3,4};
    vector<int> from(&afrom[0], &afrom[4]);
    vector<int> to(&ato[0], &ato[4]);
    vector<int> length;

    vector<int> all_nodes(from.size() + to.size());
    sort(from.begin(), from.end());
    sort(to.begin(), to.end());

    merge(from.begin(), from.end(), to.begin(), to.end(), all_nodes.begin());
    

    return 0;
}
Member Avatar for Narue

all_nodes is an empty vector, merge is trying to access indices that don't exist. If you want all_nodes to be populated by std::merge, you can do it with a back_inserter:

#include <iterator>

merge(from.begin(), from.end(), to.begin(), to.end(), back_inserter(all_nodes));

Alternatively you can resize all_nodes so that you no longer overrun your memory:

vector<int> all_nodes(from.size() + to.size());
Member Avatar for Clockowl

Oh that back_inserter is nice. I'm reading up on the STL as of lately, so much to learn. :D Thanks Narue.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.