Re: constraints on types used for instantiating standard containers
On Mar 8, 3:27 am, "Ganny" <sggan...@gmail.com> wrote:
On Mar 8, 3:37 am, "Lance Diduck" <lancedid...@nyc.rr.com> wrote:
On Mar 7, 10:35 am, "Ganny" <sggan...@gmail.com> wrote:> For example,
use a type K qualified by const and volatile as a Key for
an associative container - what are the conditions that K should
satisfy and can it be CV-qualified - where are such constraints
specified in the standard? I checked 23.1.3 [lib.associative.reqmts]
and it doesn't clearly specify what Key or T can be.
thanks!
-ganesh
K has "const" applied automatically by the container. ie.
template <class K,class V> struct cont
:my_cont_impl<const K,V>
{
///};
I suppose it could be volatile, however, I've never tried it. volatile
implies that something changes outside the flow that the compiler can
discern (i.e. by another thread or via a port) The container itself of
course cannot tolerate this behaviour, it want all keys to change via
its interface so that it can maintain its invariant. So volatile keys
would be a pessimisation at best.
The other property is that the key is "strict weak comparable" So this
must hold
!comp(k1,k2)&&!comp(k2,k1)
for instance, if the comparator is the default, it becomes
!(k1<k2)&&!(k2<k1)
(Note: if !comp(k1,k2)&&!comp(k2,k1) implies equalfunc(k1,k2) [!
(k1<k2)&&!(k2<k1)=>(k1==k2)] this is called a "total ordering")
These requirement and more in depth explaination are on the SGI
website, or in any good reference on the STL.
Lance
Hi Lance,
I am specifically interested in knowing where the standard specifies
the constraints on Keys. For example, your explanation 'The other
property is that the key is "strict weak comparable".. ' is clearly
specified in 23.1.2[2] - [lib.associative.reqmts]. How about other
possible constraints - why is that such other constraints aren't
clearly or explicitly specified in the standard?
thanks!
-ganesh
The table following 23.1.2 does give all the constraints. The only
constraint is that Key is Assignable (in the table). The thing that
may be confusing is that "Assignable" is all you need, over and above
the basics of being publicly constructable and destructable, which is
required by the std::pair in 23.1.2[5].
To be precise, the *comparator* must define a strict weak ordering on
the keys -- the keys themselves do not have to be comparable at all.
It helps if they define their own operator< of course, for use with
the default comparator: this makes it a lot easier to make maps.
But give it a try. Make up a key like
struct MyKey{
std::string val;
};
This is already Assignable, and can be placed in a std::pair, but
lacks any comparators. Now make up a comparator function
struct Comp{
bool operator()(MyKey const&l,MyKey const&r)const{
return l.val.size()<r.val.size();
}
};
and make a map<MyKey,int,Comp>. This of course will map values based
on the size of a string, rather than contents. You can even have
runtime values inside the comparator objects:
struct Comp2{
int v;
Comp2(int _v):v(_v){}
bool operator()(MyKey const&l,MyKey const&r)const{
return l.val.size()+v<r.val.size();
}
};
You will see that other than the bare bones of being assignable,
constructable, and destructable, Key does not have to do much at all.
The REAL business happens in the comparator object.
Here are some keys that will not work:
struct MyBadKey{//not constructible
std::string& val;
};
Or
struct MyBadKey2{//not destructable
std::string val;
protected:
~MyBadKey2(){}
};
or
struct MyBadKey3{
std::string val;
private:
void operator=(MyBadKey2 const&);
};
But that is about the extent of it.
Hope that helps.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]