Implement Container in c++

Question

i want to implement a container, which contains maximal 20 Solutions. If the container contains 20 Solutions any Solution that is added is only accepted if its

1) new_value < worst value in the Container

2) if new_value is already in the container (and 1) holds) then memcmp(new_assignment, assigment, assignment_size) != 0

Then the worst solutions is deleted. (Including the int array) the assignment_size is for all Solutions the same.

struct Solution {
  double value;
  int *assignment;
  int assigment_size;
};

What is the easiest way to implement this structure? Can you use some container of the STL?

You can use std::list as container. It's your exercise not our ! — double_g, May 28 '14 at 15:48
I thought `std::vector` at first as well, but then it occurs to me that `std::map` might fit this better. `boost::flat_map` if you want performance. It's very nearly _designed_ for this. — Mooing Duck, May 28 '14 at 16:14
I suggest a std::list but any sorted containers could be used. I choose a list to keep logic of insertion/poping element. — double_g, Jun 02 '14 at 11:57

score 0 · Answer 1 · answered May 28 '14 at 15:50

Note: I assumed that your solution is described by the Solution structure you posted.

The easiest solution would be a std::array<Solution, 20>, wrapped in a custom container wrapper.

You should have something like this:

class SolutionsSequence
{
public:
    // in a function to add a solution to the sequence, you should
    // implement the criteria to decide which solution is worse
private:
    std::array<Solution, 20> solutions_;
};

Other than that, you should not use memcpy in C++. Consider using std::copy, or std::copy_n instead.

Also consider using a std::vector for assignments, and then you can get rid of the assignment_size.

I wouldn't recommend `array`, because `array` is designed for 20 at all times, whereas he has a requirement for _up to 20_, which is a very different thing. — Mooing Duck, May 28 '14 at 16:11

user3680510 · Accepted Answer · 2014-05-28T16:30:52.670

0

Ok Thank you. I hope it is correct. It tried to keep the list trough insert sorted so it is easier to check and then you can remove the last element.

struct Solution {
  double power_peak;
  int *assignment;
  int size;
  ~Solution() { delete[] assignment; }
};


class Container {
  list<Solution> Solutions;
  uint max_size;
  double worst_solution;
public:
  Container (uint size)
  {
    max_size = size;
  }
  void addSolution(Solution s)
  {
    list<Solution>::iterator insert_position = Solutions.begin();
    while (insert_position != Solutions.end() && (*insert_position).power_peak < s.power_peak)
    {
      if ((*insert_position).power_peak == s.power_peak && memcmp((*insert_position).assignment, s.assignment, s.size) == 0)
      {
        return;
      }
      ++insert_position;
    }
    Solutions.insert(insert_position, s);
    if (Solutions.size() > max_size)
    {
      Solutions.pop_back();
    }
    worst_solution = (*(--(Solutions.end())))->power_peak;
  }
  double getWorst()
  {
    return worst_solution;
  }
};

edited May 28 '14 at 16:30

answered May 28 '14 at 16:05

user3680510

16
1

1

You either speculated wildly or have inside information, I can't tell which – Mooing Duck May 28 '14 at 16:12
Could you explain some more? – user3680510 May 28 '14 at 16:22
You have renamed `value` to `power_peak`, and made the `worst_solution` publicly available but no other solutions. I don't see why you did either of those things. – Mooing Duck May 28 '14 at 16:36
that don't matter if the name is value or power_peak. i included the worst_solution method to check fast if it is worth to try to insert the Solution. – user3680510 May 28 '14 at 16:43
1

@user3680510 Your code has undefined behavior. Your `Solution` object cannot be copied safely due to missing user-defined copy constructor and assignment operator (read up on "the rule of 3"). If you quit using pointers and used `std::vector` within the `Solution` object, then these issues would go away. – PaulMcKenzie May 28 '14 at 16:43
if i make a list and addSolution(Solution *s) would this also work? – user3680510 May 28 '14 at 16:48
1

@user3680510 - `if i make a list and addSolution(Solution *s) would this also work?` Why are you looking for a problem to a solution? Just use `std::vector assignment` instead of `int* assignment` and all those problems go away. Making more code use pointers makes the code more fragile. – PaulMcKenzie May 28 '14 at 16:50
2

`struct Solution { std::vector assignment; double power_peak; };` is all you need. Not only does this remove the issue of not being safely copyable, you don't need the `size` member since a vector knows it's size by calling the `vector::size` function. – PaulMcKenzie May 28 '14 at 16:55
ok but i still don't understand why array don't know its size but when you call delete[] array the delete knows the size of the array – user3680510 May 28 '14 at 16:57
@user3680510 - You need to understand that the way you wrote the `Solution` class makes it unsuitable to be stored in a container such as `std::list`. It has nothing to do with what `delete[]` can or cannot do. See here: http://stackoverflow.com/questions/4172722/what-is-the-rule-of-three Make the changes I suggested, and all of those issues disappear. – PaulMcKenzie May 28 '14 at 16:58
@user3680510: It's always irked me that `delete[]` knows the size of the array, and also how many bytes of memory there are, but there's no way for us to get either piece of information. Nobody understands why. – Mooing Duck May 28 '14 at 17:10

Implement Container in c++

2 Answers2