swapping container with self referencing element

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 va开发者_如何学JAVAlue_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.
}

---

you can implement std::swap for your type:

void std::swap(std::vector<kid_t> &first,std::vector<kid_t> &second)
{
  //here is your implementation or three lines of default swap
}

---

I don't see any way of doing this using swap. The only way I can think of is providing a move function in kid which moves a kid from one home to the other. Then write your own function to move the kids around.

---

I agree that problem is in the design, but I think it's actually fairly simple to state: you're using object addresses as a form of object identity. This is a perfectly fine thing to do (it's precisely why C++ forbids 0-size objects - so each fully derived object has its own distinct address, and hence distinct identity), but if you do so, you should not treat your objects as value types, and randomly copy them around - or let any other class, such as std::vector, do so.

So, when it comes to semantics, when you swap two vectors that you have in your code, you aren't effectively swapping kids: you're killing kids in each house, and creating clones of them in the opposite house. Which is probably not quite the intended business logic.

I agree with Matthieu here that, if you use object addresses as object identity like that, then you need to allocate the kids yourself, and store pointers to them in your vector. If homes truly own kids, then use either vector<shared_ptr<kid_t>> or boost::ptr_vector. If homes do not own kids, and a kid can live without a home without being mercy-killed, then have a singleton list<kid_t> that owns and allocates all kids (and, being a list, will never reallocate implicitly), and then use vector<kid_t*> with pointers to objects in that list for every home.

---

The problem here seems more a problem of design than a problem of swap.

You (basically) use a pointer to a variable you did not assign yourself as an identifier of the kid... so of course as soon as the kids are moved around, it's going to break. (well it's slightly better than a pointer actually, but not by much)

You have 2 solutions:

• the basic > instantiate them yourselves
• the more complicated > factory + id

And of course you also have the problem that you tied up Home and its implementation... but I'll let you write a proper Home class by yourself. By the way, since the number of templates parameters of a STL container depend both on the container and on the actual implementation of the STL you are using, your solution is far less generic than using a real class ;)

Basic:

class kid
{
public:
  kid(kid* related = 0): m_related(related) {}
  // methods
private:
  // other attributes
  kid* m_related;
};

int main(int argc, char* argv[])
{
  Home home1, home2;
  kid* kid1 = home1.insert(new kid(home1, 1));
  home1.insert(new kid(home1, 2, kid1));

  kid* kid2 = home2.insert(new kid(home2, 1));
  kid* kid3 = home2.insert(new kid(home2, 2));
  home.insert(new kid(home2, 3, kid2));
  home.insert(new kid(home2, 4, kid3));

  swap(home1,home2); // just swapping the vectors, since it only moves pointers not the objects
}

That's the easy way, but of course I still curse you because I have 2 kids with an id of 1...

Factory

 class KidFactory;

 class KidKey { friend class KidFactory; KidKey() {} };

 class Kid
 {
 public:
   Kid(KidKey, Id id, Id cousinId);

   Id getId() const { return m_id; }

   const Home* getHome() const;
   void setHome(const Home& home);

 private:
   const Home* m_home;
   Id m_id;
   Id m_cousinId;
 };

 // Factory
 class KidFactory
 {
 public:
   Kid& createKid(Id cousinId = -1)
   {
     m_kids.push_back(Kid(KidKey(), m_kids.size(), cousinId));
     return m_kids.back();
   }

   Kid& getKid(Id id)
   {
     return m_kids.at(id); // notice that might generate out_of_range exception
   }

 private:
   std::vector<Kid> m_kids;
 };

 class Home
 {
 public:
   void insert(Kid& kid)
   {
     m_kids.push_back(kid.getId());
     kid.setHome(*this);
   }
 };


 int main(int argc, char* argv[])
 {
   KidFactory factory;
   Home home1, home2;

   home1.insert(factory.createKid());
   home1.insert(factory.createKid(home1.front().getId()));

   Kid& kid1 = factory.createKid();
   home2.insert(kid1);
   home2.insert(factory.createKid(kid1.getId()));

   // once again swapping vectors is fine
 }

Proper design leads to easy to write code... but some boilerplate one in C++ :(