2D Vector - Remove Rows by search

Question

I'm quite new to vector and need some additional help with regards to vector manipulation.

I've currently created a global StringArray Vector that is populated by string values from a text file.

typedef std::vector<std::string> StringArray;
std::vector<StringArray> array1;

I've created a function called "Remove" which takes the input from the user and will eventually compare the input against the first value in the array to see whether it's a match. If it is, the entire row will then deleted and all elements beneath the deleted row will be "shuffled up" a position to fill the game.

The populated array looks like this:

Test1 Test2 Test3
Cat1 Cat2 Cat3
Dog1 Dog2 Dog3

And the remove function looks like this:

void remove()
{
    string input;

    cout << "Enter the search criteria";
    cin >> input;

I know that I will need a loop to iterate through the array and compare each element with the input value and check whether it's a match.

I think this will look like:

for (int i = 0; i < array1.size(); i++)
{
    for (int j = 0; j < array1[i].size(); j++)
    {
        if (array1[i] = input)
        **//Remove row code goes here**
    }
}

But that's as far as I understand. I'm not really sure A) if that loop is correct and B) how I would go about deleting the entire row (not just the element found). Would I need to copy across the array1 to a temp vector, missing out the specified row, and then copying back across to the array1?

I ultimately want the user to input "Cat1" for example, and then my array1 to end up being:

Test1 Test2 Test3
Dog1 Dog2 Dog3

All help is appreciated. Thank you.

score 1 · Accepted Answer · edited May 23 '17 at 12:24

1

So your loop is almost there. You're correct in using one index i to loop through the outer vector and then using another index j to loop through the inner vectors. You need to use j in order to get a string to compare to the input. Also, you need to use == inside your if statement for comparison.

for (int i = 0; i < array1.size(); i++)
{
    for (int j = 0; j < array1[i].size(); j++)
    {
        if (array1[i][j] == input)
        **//Remove row code goes here**
    }
}

Then, removing a row is the same as removing any vector element, i.e. calling array1.erase(array1.begin() + i); (see How do I erase an element from std::vector<> by index?)

edited May 23 '17 at 12:24

Community

1
1

answered Jan 02 '17 at 07:14

Robbie Jones

391
1
7

1

Great, just what I was after Robbie. I knew I had the logic put just didn't quite know how to put it in practice! Thanks very much for your help! :) – GuestUser140561 Jan 02 '17 at 07:19
He doesn't need the inner loop, since he only wants to compare the first value in each StringArray. Also, if sequential operations are not needed, you could use an std::map for array1 using the first item of the StringArray the key, thus having an O(1) when comparing input. – o_weisman Jan 02 '17 at 08:28

Jadh4v · Answer 2 · 2017-01-02T07:17:06.133

0

Use std::list<StringArray> array1;

Erasing an item from an std::vector is less efficient as it has to move all the proceeding data. The list object will allow you to remove an item (a row) from the list without needing to move the remaining rows up. It is a linked list, so it won't allow random access using a [ ] operator.

edited Jan 02 '17 at 07:17

answered Jan 02 '17 at 07:10

Jadh4v

130
3

For the kind of operation in this question the filtering still remains `O(n)` (you save on erase, but you need the looping anyway to do the search). The fact that the gain on the constant factor will compensate for the problems of `std::list` is debatable. – 6502 Jan 02 '17 at 07:45
The efficiency of erase() operation on a vector is not simply a matter of asymptotic complexity. Memory operations like moving data are particularly expensive. In fact, since the search performed is done in a linear fashion, random accessibility of a vector is not required in this case. A call to `vector::erase` will trigger the copy constructors of all proceeding vectors and consequently all the string objects involved. – Jadh4v Jan 02 '17 at 08:08
Not necessarily the copy constructor (move constructor can be used). Talking about memory an `std::vector` is much more cache friendly and the elements don't need extra data for the pointers. Before saying that an `std::list` would be more efficient you'd need real tests on real data... I wouldn't be surprised that there are cases in which it's cheaper to move in a cache-friendly way the data doing the filtering than to jump around between fatter nodes randomly allocated on the heap instead. Actually in my experience `std::list` is of little use in C++ and is rarely the best option. – 6502 Jan 02 '17 at 08:20

score 0 · Answer 3 · answered Jan 02 '17 at 07:40

You can use explicit loops, but you can also use already implemented loops available in the standard library.

void removeTarget(std::vector<StringArray>& data,
                  const std::string& target) {
    data.erase(
        std::remove_if(data.begin(), data.end(),
            [&](const StringArray& x) {
                return std::find(x.begin(), x.end(), target) != x.end();
            }),
        data.end());
}

std::find implements a loop to search for an element in a sequence (what you need to see if there is a match) and std::remove_if implements a loop to "filter out" elements that match a specific rule.

Before C++11 standard algorithms were basically unusable because there was no easy way to specify custom code parameters (e.g. comparison functions) and you had to code them separately in the exact form needed by the algorithm.

With C++11 lambdas however now algorithms are more usable and you're not forced to create (and give a reasonable name to) an extra global class just to implement a custom rule of matching.

2D Vector - Remove Rows by search

3 Answers3