0

I need to implement a generic map. I decide to implement it with a linked list. I notice the copy constructor and the assignment operator are similar because they both create and copy linked list. So I wonder if I can use the copy operator in the assignment operator or vice versa. Do you have an idea to do it?

ROMANIA_engineer
  • 54,432
  • 29
  • 203
  • 199
Ohad Shamir
  • 37
  • 1
  • 6
  • 2
    I think you might be looking for: [What is the copy-and-swap idiom?](http://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom) – NathanOliver Jan 15 '16 at 17:20
  • 1
    To use the copy / swap idiom, make sure that the copy constructor is where the actual copying code lies. It should not rely or use the assignment operator. Then you also need a working destructor. You have those two, then the assignment operator is a piece of cake using copy / swap since that idiom relies on working copy constructor and destructor. – PaulMcKenzie Jan 15 '16 at 17:26
  • 1
    I am puzzled at why did you decide to implement a map using a linked list. If I was your teacher, you'd not pass with that. – SergeyA Jan 15 '16 at 17:54
  • Which data structure do you think is better? I choose linked list because it does not have a limit to the data I can store. – Ohad Shamir Jan 15 '16 at 18:01
  • You should use an array, because you need fast access. Linked lists have O(n) and arrays have O(1). But you will need to handle the reallocation of the array when it reaches the size limit. – ssuljic Jan 15 '16 at 18:13
  • We do not take into consideration efficiency considerations in the course. – Ohad Shamir Jan 15 '16 at 18:24
  • @OhadShamir, map is generally meant to be key-value container, where you can efficietly retrieve a certain value given the key. – SergeyA Jan 15 '16 at 18:34
  • @ssuljic In addition to 0(N) vs O(1), linked lists result in truly pathetic caching and prediction because the links could be anywhere in memory. Even where the advantages of a linked list should allow it to shine, cache misses and the reduced effectiveness of pipelines often more than offset the perceived performance gain of the linked list. See https://isocpp.org/blog/2014/06/stroustrup-lists for a more complete discussion. – user4581301 Jan 15 '16 at 19:35
  • Expanding on @SergeyA 's point, once you convert the key, further look-up should be a piece of cake. With a linked list, you are doomed to iterating through the list even if the key tells exactly where in the in the list the value is stored. This utterly defeats the point of a map. Efficiency may not be an issue, but you will have coded a map in name only and not learned the lessons coding your own map was supposed to teach. – user4581301 Jan 15 '16 at 20:16
  • @user4581301, in the sake of correctness, conventional implementation of a map as a tree would suffer the same memory locality issues. – SergeyA Jan 15 '16 at 20:56

1 Answers1

0

In most cases if you've defined the copy constructor, it's already used when you do a copy assignment. That is to say the compiler implicitly uses your copy constructor to define copy assignment in the general case.

Example:

#include<iostream>
using namespace std;
struct copy_me {
   int member;
   copy_me() : member(0) {};
   copy_me(const copy_me &other) : member(other.member) {
      cout << "copy const called" << endl;
   };
};

int main() {
   copy_me me;
   copy_me other = me;
   return other.member;
}

Output:

copy const called

To answer your specific question:

thunt
  • 1