Remove item from C-array and shift

[alix]

I am a beginner, and I want to delete an item from an array, non-STL.

This doesn't seem possible? Below. So, out of share curiosity, how can I delete or remove an item from a regular array, I am not using STL. I want to know how this can be done with one dynamic array that's been allocated on the HEAP.

#include <iostream>
#include <string>

class Monster{
public:
  Monster(){};
  Monster(std::string name) : name(name){}
private:
  std::string name = "";
};

class Monsters{
public:
  Monsters(int max):max(max){
    monsters = new Monster[max];
  }

  void add(const Monster* m){
    monsters[total++] = *m;
  }

  void remove(const Monster* m)
  {
    for(Monster* mptr = monsters; mptr!=monsters+total; mptr++){
      if(mptr == m){
        delete mptr;
      }
    }
  }

private:
  Monster* monsters = nullptr;
  int max = 0;
  int total = 0;
};

int main()
{
  int size = 5;
  Monsters* monsters = new Monsters(size);
  Monster* monster1 = new Monster("Sally");
  Monster* monster2 = new Monster("Rich");

  monsters->add(monster1);
  monsters->add(monster2);

  monsters->remove(monster1);

  return 0;
}

[kbw]

As you'll have noticed, an array is a contiguous sequence of bytes. So you have to pretend to delete something.

Typically, you move all the higher elements one space down, overwriting the element you want to loose, and freeing up an extra space on the end.

The same happens with std::vector, except you can additionally shrink the vector to remove that last free space at the end. It happens in two steps, first shuffle everything down by one--erase, the shrink the vector--remove. See The Erase Remove Idiom.
https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom

Finally, shrinking a vector doesn't cause the internal array to change, just the "end" mark to change. The destructor of that last element is called (if it has one) to clean it up.

[alix]

How can I do that with the code above?

[kbw]

#include <algorithm>
#include <iostream>
#include <memory>
#include <string>
#include <vector>

class Monster{
public:
  Monster() = default;
  Monster(std::string name) : name(std::move(name)){}
  bool operator==(const Monster& n) const { return name == n.name; }
private:
  std::string name;
};

class Monsters{
public:
  Monsters(int max){
    // do we care about max?
  }

  size_t size() const { return monsters.size(); }

  void add(Monster* m){
    monsters.emplace_back(std::unique_ptr<Monster>(m));
  }

  void remove(Monster* m)
  {
    monsters.erase(std::remove_if(monsters.begin(),
                                  monsters.end(),
                                  [m](const std::unique_ptr<Monster>& entry) { return *m == *entry; }),
                   monsters.end());
  }

private:
  std::vector<std::unique_ptr<Monster>> monsters;
};

int main()
{
  int size = 5;
  std::unique_ptr<Monsters> monsters(new Monsters(size));
  Monster* monster1 = new Monster("Sally");
  Monster* monster2 = new Monster("Rich");

  monsters->add(monster1);
  monsters->add(monster2);
  std::cout << "monsters.size=" << monsters->size() << '\n';

  monsters->remove(monster1);
  std::cout << "monsters.size=" << monsters->size() << '\n';

  return 0;
}

[alix]

Without "unique_ptr". I know I can use that, but, what if I have: Monster* monsters = nullptr; as my declaration.

[alix]

Something like this: https://codeforwin.org/2015/07/c-program-to-delete-element-from-array.html, except with pointers, but I don't know where to begin.

[kbw]

The link doesn't show anything for me.

Your code, as you posted it, leaks everything. You don't need a Monsters* at all. I kept it to minimize the changes to your original code. main() should look like:

int main()
{
  int size = 5;
  Monsters monsters(size);
  Monster* monster1 = new Monster("Sally");
  Monster* monster2 = new Monster("Rich");

  monsters.add(monster1);
  monsters.add(monster2);

  monsters.remove(monster1);
}

[alix]

What do you mean by "leaks" everything?

[kbw]

All those calls to new allocate memory and you never release it. I used std::unique_ptr<> to manage them.

You don't need pointers at all.

#include <algorithm>
#include <iostream>
#include <memory>
#include <string>
#include <vector>

class Monster {
public:
  Monster() = default;
  Monster(std::string name) : name(std::move(name)){}
  bool operator==(const Monster& n) const { return name == n.name; }
  bool operator==(const std::string& str) const { return name == str; }
private:
  std::string name;
};

class Monsters{
public:
  Monsters() = default;

  size_t size() const { return monsters.size(); }

  void add(Monster m){
    monsters.emplace_back(std::move(m));
  }

  void remove(const std::string& name)
  {
    monsters.erase(std::remove_if(monsters.begin(),
                                  monsters.end(),
                                  [&name](const Monster& entry) { return entry == name; }),
                   monsters.end());
  }

private:
  std::vector<Monster> monsters;
};

int main()
{
  Monsters monsters;
  Monster monster1("Sally");
  Monster monster2("Rich");

  monsters.add(std::move(monster1));
  monsters.add(std::move(monster2));
  std::cout << monsters.size() << '\n';

  monsters.remove("Sally");
  std::cout << monsters.size() << '\n';
}

[alix]

Ah, no worries about that. I am just trying to figure out:

How I can remove the item from array while using a pointer for loop. I read somewhere, that the pointer you pass in, must be used to point to the item you decide to remove. Not sure of how I can interpret this.

[kbw]

We don't recommend using raw pointers, C++ was designed to manage such things safely, and I've shown how this may be achieved above. Nevertheless, here's the remove in it's most basic form, as you've asked for it. But please please please, don't use code that looks like this in anything but a sample.

#include <string>

class Monster {
public:
    Monster(const std::string& str) : name(str) {}
    bool operator==(const std::string& str) const { return name == str; }
private:
    std::string name;
};

int main() {
    size_t max_monsters{ 10 };
    size_t n_monsters{ 0 };
    Monster** monsters{ new Monster*[max_monsters] };
    for (size_t i = 0; i != max_monsters; ++i)
        monsters[i] = nullptr;

    monsters[n_monsters++] = new Monster{"chronos"};
    monsters[n_monsters++] = new Monster{"primeos"};
    monsters[n_monsters++] = new Monster{"davos"};

    for (size_t i = 0; i != n_monsters; ++i)
        if (*monsters[i] == "primeos") {
            delete monsters[i];
            for (size_t j = i + 1; j != n_monsters; ++j)
                monsters[j - 1] = monsters[j];
            --n_monsters;
            break;
        }

    for (size_t i = 0; i != n_monsters; ++i)
        delete monsters[i];
    delete [] monsters;
}

[keskiverto]

How I can remove the item from array

constexpr size_t Max {5};
size_t total {0};
T something [Max];

The 'something' is an array of type T objects.

// change value of something[0]
// change value of something[1]
// change value of something[2]
total = 3; // assert(total <= Max) 

Now we have array with three objects. (In reality we have five, but we make believe.)

We want to remove one of them.

kbw's first example had array of pointers and the value to remove was a pointer.
kbw's second example had array of Monsters and the value to remove was a Monster, whose name did match.

The question is, how do you know which monster to remove?

If we know that it is the second in array, then:

size_t victim = 1;
for ( size_t e = victim; e + 1 < total; ++e ) {
  something[e] = something[e+1];
}
--total;

[alix]

Can't the index of a pointer be used?

for(Monster* mptr = monsters; mptr!=monsters+total; mptr++)

Because the poiner moves to next item. But, I am not sure. The vector.h in C++ does this,

 iterator erase(const_iterator _First_arg, const_iterator _Last_arg) noexcept /* strengthened */ {
        iterator _First      = _Make_iter(_First_arg);
        iterator _Last       = _Make_iter(_Last_arg);
        difference_type _Off = _First - begin();

[kbw]

Can't the index of a pointer be used?

Isn't that my previous post?

[alix]

No vector. std::vector<Monster> monsters;. I have seen this. I know how to do this with STL. But, I want to know if this can be done without STL help. Like in my code above.

[alix]

Here's the code: https://repl.it/@xxxxxx10/experiement#main.cpp, you can run and debug it.

[seeplus]

As has already been discussed at
http://www.cplusplus.com/forum/beginner/273119/
http://www.cplusplus.com/forum/beginner/273117/

when @alix has said that the ordering doesn't matter. You just swap the element to be deleted with the last element and decrement the count of the number of elements. If the element is a pointer, then also delete the memory if needed.

[kbw]

No vector. std::vector<Monster> monsters;. I have seen this. I know how to do this with STL.

You obviously haven't looked at what I posted. Maybe this link will get you there.
https://www.cplusplus.com/forum/beginner/273123/#msg1177871

[alix]

@seeplus, how do you mean? Swap? Any example here?

[seeplus]

That is what std::remove() does as it doesn't change the size. However, you don't actually need to swap here as you can adjust its size. Just copy over the element to be removed by the last element.

From previous code:

	bool remove(const Employee& e)
	{
		for (auto ee = begin(); ee != end(); ++ee)
			if (ee->getName() == e.getName()) {
				*ee = employees[--current_total];
				return true;
			}

		return false;
	}

ee is the pointer to the element to be removed. current_total is the number of elements. First decrement current_total (--current_total) and then copy the last element over the removed element ( *ee = employees[--current_total] )

Using swap this would be:

//*ee = employees[--current_total];
std::swap(*ee, employees[--current_total]);

It depends upon what you want the previous last element to be. Either as it was and use = (in which case both the removed element and the last element are the same), or the removed element and use std::swap().