std::merge invalidates source data because it uses move semantics

std::merge invalidates source data because it uses move semantics by Travis Vitek

Closed

as Fixed

Type:	Bug
ID:	680313
Opened:	7/21/2011 4:08:18 PM
Access Restriction:	Public
Moderator Decision:	Sent to Engineering Team for consideration

Workaround(s)

view

User(s) can reproduce this bug

The merge algorithm moves data from the source ranges into the destination, invalidating the source data. The C++03 standard isn't really clear about whether or not the input range is invalidated, but this is not consistent with what is expected.

I do not believe this behavior is consistent with previous versions of Visual Studio. None of the other implementations I've tested exhibit this behavior, and it is not consistent with the documented behavior of the function (http://msdn.microsoft.com/en-us/library/9ew9xdb2.aspx) or that of the C++0x draft (which explicitly says the source ranges are copied).

Details (expand)

Visual Studio 2010 SP1

Compile and run the code as shown below.

c:\test>type t.cpp
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

template <class T>
void dump (const std::vector<T>& v, std::ostream& os)
{
for (size_t i = 0; i < v.size(); ++i)
    os << " '" << v[i] << "' ";
os << "\n";
}

int main ()
{
using namespace std;

const string seq_1[] = {
    "1", "3", "2"
};

const string seq_2[] = {
    "6", "4", "5"
};

vector<string> v0 (seq_1, seq_1+ (sizeof seq_1 / sizeof *seq_1));
sort (v0.begin(), v0.end());

vector<string> v1 (seq_2, seq_2 + (sizeof seq_2 / sizeof *seq_2));
sort (v1.begin(), v1.end());

dump (v0, std::cout);
dump (v1, std::cout);

// reserve space for an appropriate number of elements
vector<string> tmp (v0.size() + v1.size());

// merge from v and v into tmp
merge (v0.begin(), v0.end(), v1.begin(), v1.end(), tmp.begin());

// dump each vector
dump (v0, std::cout);
dump (v1, std::cout);
dump (tmp, std::cout);

return 0;
}

c:\test>cl /nologo /EHsc /W4 t.cpp
t.cpp

c:\test>t.exe

English

Windows 7

English

c:\test>t.exe
'1' '2' '3'
'4' '5' '6'
'' '' ''
'' '' ''
'1' '2' '3' '4' '5' '6'

c:\test>t.exe
'1' '2' '3'
'4' '5' '6'
'1' '2' '3'
'4' '5' '6'
'1' '2' '3' '4' '5' '6'

File Name	Submitted By	Submitted On	File Size
t.cpp	Travis Vitek	7/21/2011	992 bytes

Posted by Microsoft on 8/15/2011 at 4:49 PM

Hi,

Thanks for reporting this bug. We've fixed it, and the fix will be available in VC11. Both the normal and predicate versions of std::merge() have been fixed.

If you have any further questions, feel free to E-mail me at stl@microsoft.com .

Stephan T. Lavavej
Visual C++ Libraries Developer

Posted by MS-Moderator10 [Feedback Moderator] on 7/21/2011 at 6:40 PM

Thank you for submitting feedback on Visual Studio 2010 and .NET Framework. Your issue has been routed to the appropriate VS development team for investigation. We will contact you if we require any additional information.

Posted by MS-Moderator01 on 7/21/2011 at 4:50 PM

Thank you for your feedback, we are currently reviewing the issue you have submitted. If this issue is urgent, please contact support directly(http://support.microsoft.com)

Posted by Viorel_ on 7/21/2011 at 11:35 PM

Use constant iterators:

    const auto & v0c = v0;
    const auto & v1c = v1;
    merge (v0c.begin(), v0c.end(), v1c.begin(), v1c.end(), tmp.begin());