When a container contains elements which has a pointer to the container itself, the standard version of swap through pointer exchange doesn't work, and the swap doesn't check any such possibility. Is there any way to tell the container that standard swap doesn't work, and to use some different version? What is the best way to implement such swap?
The following example explains the problem.
template<template<typename T,typename = std::allocator<T> > class H>
struct kid
{
typedef H<kid> home_type;
typedef int id_t;
kid(const home_type& home,int m,typename home_type::size_type c=-1)
: home_(&home)
, me_(m)
, idx_(c)
{
}
id_t me()const
{
return me_;
}
id_t cousin()const
{
return (*home_).size() < idx_ ? -1 : (*home_)[idx_].me();
}
private://default copy & assign ok???
const home_type* home_;
typename home_type::size_type idx_;
id_t me_;
};
int main()
{
typedef kid<std::vector> kid_t;
typedef std::vector<kid_t> home_t;
home_t home1,home2;//two neighbors
home1.push_back(kid_t(home1,1));//elderly kid
home1.push_back(kid_t(home1,2,0));//the cousins
home1.push_back(kid_t(home1,3,0));
home1.push_back(kid_t(home1,4,0));
home2.push_back(kid_t(home2,10));//first kid
home2.push_back(kid_t(home2,20));//second kid
home2.push_back(kid_t(home2,30,0));//cousin of first kid.
home2.push_back(kid_t(home2,40,1));//cousin of second kid
for(home_t::const_iterator it = home1.begin(); it!= home1.end(); ++it)
{
std::cout<<(*it).me()<<" "<<(*it).cousin()<<"\n";
}
std::cout<<"\n";
for(home_t::const_iterator it = home2.begin(); it!= home2.end(); ++it)
{
std::cout<<(*it).me()<<" "<<(*it).cousin()<<"\n";
}
std::cout<<"\nexchange home\n";
std::swap(home1,home2);//they exchanged their house, surely this doesn't work.
//what is the best way to do this?
for(home_t::const_iterator it = home1.begin(); it!= home1.end(); ++it)
{
std::cout<<(*it).me()<<" "<<(*it).cousin()<<"\n";
}
std::cout<<"\n";
for(home_t::const_iterator it = home2.begin(); it!= home2.end(); ++it)
{
std::cout<<(*it).me()<<" "<<(*it).cousin()<<"\n";
}
//all the kids got confused, they points to neighborhood kids as their cousins
}
In actual implementation, i have a class X with two vectors v1 & v2, while elements of v1 points to portion of v2. Simply swapping v1 & v2 doesn't work, as v1 contains pointer to v2 which also need to be updated. I am looking for the best way to implement such swap, without violating any encapsulation.
UPDATE
while i strongly dislike a public set_home for kid, as that is not part of kid's api and violates encapsulation, i also realized std::vector is not good. A dedicated home class is needed. A pointer based solution can always be done, as every level of indirection gives additional maneuverability. But that merely changes the problem rather than solving it.
One thing should be noted is that kids are not freestanding objects, they need home, and that is encoded in signature of kid. I feel that, a nothrow swap just swaps the pointer is too optimistic view. The swap for container should know whether it can do that optimization. This kind of problem also happens when storing std::vector of std::tr1::function, where the functor itself stores the reference/iterator to the vector.
I have this solution which just gives selective access to *set_home* to the home class using friendship, and stored as value rather than pointer.
But i still don't like the solution very much as i feel that swap should be intelligent enough to check if it can do what it want to do, as it already has information about *value_type* (here kid instance) which it doesn't use at all.
Here is the updated code.
template<template<typename T,typename = std::allocator<T> > class H>
struct kid
{
typedef H<kid> home_type;
typedef int id_t;
kid(const home_type& home,int m,typename home_type::size_type c=-1)
: home_(&home)
, me_(m)
, idx_(c)
{
}
id_t me()const
{
return me_;
}
id_t cousin()const
{
return (*home_).size() < idx_ ? -1 : (*home_)[idx_].me();
}
private:
friend home_type;
void relocate(home_type& home)
{//private, not part of api.only home_type can call it.
home_ = &home;
}
private://default copy & assign ok???
const home_type* home_;
typename home_type::size_type idx_;
id_t me_;
};
template<typename T,typename Alloc = std::allocator<T> >
class home
{
typedef std::vector<T> base_t;
base_t h_;
public:
typedef typename base_t::size_type size_type;
typedef typename base_t::iterator iterator;
typedef typename base_t::const_iterator const_iterator;
void push_back(const T& t)
{
h_.push_back(t);
}
size_type size()const
{
return h_.size();
}
const T& operator[](size_type i)const
{
return h_[i];
}
iterator begin()
{
return h_.begin();
}
iterator end()
{
return h_.end();
}
void swap(home<T,Alloc>& other)//nothrow swap if allocators are equal, though O(N).
{
using std::swap;
swap(h_,other.h_);
for(iterator i = begin(), e = end();i!+ e; ++i)
{
(*i).relocate(h_);
}
for(iterator i = other.begin(), e = other.end();i!+ e; ++i)
{
(*i).relocate(other.h_);
}
}
};
int main()
{
typedef kid<home> kid_t;
typedef home<kid_t> home_t;
home_t home1,home2;//two neighbors
home1.push_back(kid_t(home1,1));//elderly kid
home1.push_back(kid_t(home1,2,0));//the cousins
home1.push_back(kid_t(home1,3,0));
home1.push_back(kid_t(home1,4,0));
home2.push_back(kid_t(home2,10));//first kid
home2.push_back(kid_t(home2,20));//second kid
home2.push_back(kid_t(home2,30,0));//cousin of first kid.
home2.push_back(kid_t(home2,40,1));//cousin of second kid
for(home_t::const_iterator it = home1.begin(); it!= home1.end(); ++it)
{
std::cout<<(*it).me()<<" "<<(*it).cousin()<<"\n";
}
std::cout<<"\n";
for(home_t::const_iterator it = home2.begin(); it!= home2.end(); ++it)
{
std::cout<<(*it).me()<<" "<<(*it).cousin()<<"\n";
}
std::cout<<"\nexchange home\n";
using std::swap;
swap(home1,home2);//they exchanged their house, surely this doesn't work.
//what is the best way to do this?
for(home_t::const_iterator it = home1.begin(); it!= home1.end(); ++it)
{
std::cout<<(*it).me()<<" "<<(*it).cousin()<<"\n";
}
std::cout<<"\n";
for(home_t::const_iterator it = home2.begin(); it!= home2.end(); ++it)
{
std::cout<<(*it).me()<<" "<<(*it).cousin()<<"\n";
}
//everything is fine here.
}