[STDCXX-16] __rb_tree::operator=() does not store rhs' comparison object in lhs

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 4.1.2
• Fix Version/s: 4.2.0
• Component/s: 23. Containers

Environment

All

• Assignee: Farid Zaripov
• Reporter: Martin Sebor
• Created: 29/Aug/05 04:01
• Updated: 14/Mar/07 18:28
• Resolved: 14/Mar/07 17:23

Description

-------- Original Message --------
Subject: tree::operator=() does not store rhs' comparison object in lhs
Date: Mon, 8 Aug 2005 21:48:50 -0400
From: Boris Gubenko
To: Martin Sebor <[e-mail]>

A customer reported a problem with set STL container using a program
from "The C++ Standard Library - A Tutorial and Reference" by Nicolai
Josuttis. See attached. The program generates expected result with
STLPort and gnu libstdc++, but generates a wrong result with any
version of RW library I tried it with.

The problem is that tree' assignment operator does not store rhs'
comparison object in lhs (I'd expect map container to have the same
problem). As a result, after assignment, the target container continues
to use the comparison object that it used before the assignement. It
violates 23.1.2 - Associative containers [lib.associative.reqmts],
para 11:

11 When an associative container is constructed by passing a
comparison object the container shall not store a pointer or
reference to the passed object, even if that object is passed by
reference. When an associative container is copied, either through
a copy constructor or an assignment operator, the target container
shall then use the comparison object from the container being copied,
as if that comparison object had been passed to the target container
in its constructor.

The proposed fix is the same one-liner for any version of RW library,
just the name of the member is different. See below for HP-UX.

Thanks,
Boris

granite> aCC -V
aCC: HP aC++/ANSI C B3910B A.05.50 [May 15 2003]
granite> aCC setcmp.cpp && a.out
coll1: 1 2 4 5 6 7
coll2: 7 6 5 4 2 1
coll1: 3 7 6 5 4 2 1
coll1 and coll2 have different sorting criterion
granite> aCC setcmp.cpp -I. && a.out
coll1: 1 2 4 5 6 7
coll2: 7 6 5 4 2 1
coll1: 7 6 5 4 3 2 1
coll1 and coll2 have same sorting criterion
granite> diff rw/tree.cc /opt/aCC/include_std/rw/tree.cc
83,85d82
< #if !defined(__FIXCXXL1932)
< _C_key_compare = __x._C_key_compare;
< #endif
granite>

print.hpp
---------
/* The following code example is taken from the book

• "The C++ Standard Library - A Tutorial and Reference"
• by Nicolai M. Josuttis, Addison-Wesley, 1999
  *
• (C) Copyright Nicolai M. Josuttis 1999.
• Permission to copy, use, modify, sell and distribute this software
• is granted provided this copyright notice appears in all copies.
• This software is provided "as is" without express or implied
• warranty, and with no claim as to its suitability for any purpose.
  */
  #include <iostream>

/* PRINT_ELEMENTS()

• - prints optional C-string optcstr followed by
• - all elements of the collection coll
• - separated by spaces
  */
  template <class T>
  inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="")
  {
  typename T::const_iterator pos;

std::cout << optcstr;
for (pos=coll.begin(); pos!=coll.end(); ++pos)

{ std::cout << *pos << ' '; }

std::cout << std::endl;
}

setcmp.cpp
----------
/* The following code example is taken from the book

• "The C++ Standard Library - A Tutorial and Reference"
• by Nicolai M. Josuttis, Addison-Wesley, 1999
  *
• (C) Copyright Nicolai M. Josuttis 1999.
• Permission to copy, use, modify, sell and distribute this software
• is granted provided this copyright notice appears in all copies.
• This software is provided "as is" without express or implied
• warranty, and with no claim as to its suitability for any purpose.
  */
  #include <iostream>
  #include <set>
  #include "print.hpp"
  using namespace std;

// type for sorting criterion
template <class T>
class RuntimeCmp {
public:
enum cmp_mode

{normal, reverse}

;
private:
cmp_mode mode;
public:
// constructor for sorting criterion
// - default criterion uses value normal
RuntimeCmp (cmp_mode m=normal) : mode(m) {
}
// comparison of elements
bool operator() (const T& t1, const T& t2) const

{ return mode == normal ? t1 < t2 : t2 < t1; }

// comparison of sorting criteria
bool operator== (const RuntimeCmp& rc)

{ return mode == rc.mode; }

};

// type of a set that uses this sorting criterion
typedef set<int,RuntimeCmp<int> > IntSet;

// forward declaration
void fill (IntSet& set);

int main()
{
// create, fill, and print set with normal element order
// - uses default sorting criterion
IntSet coll1;
fill(coll1);
PRINT_ELEMENTS (coll1, "coll1: ");

// create sorting criterion with reverse element order
RuntimeCmp<int> reverse_order(RuntimeCmp<int>::reverse);

// create, fill, and print set with reverse element order
IntSet coll2(reverse_order);
fill(coll2);
PRINT_ELEMENTS (coll2, "coll2: ");

// assign elements AND sorting criterion
coll1 = coll2;
coll1.insert(3);
PRINT_ELEMENTS (coll1, "coll1: ");

// just to make sure...
if (coll1.value_comp() == coll2.value_comp())

{ cout << "coll1 and coll2 have same sorting criterion" << endl; }

else

{ cout << "coll1 and coll2 have different sorting criterion" << endl; }

}

void fill (IntSet& set)
{
// fill insert elements in random order
set.insert(4);
set.insert(7);
set.insert(5);
set.insert(1);
set.insert(6);
set.insert(2);
set.insert(5);
}