Delete_items_from_string

[Neil.Dyke]

Hi,

Is it possible to delete certain items from a char sequence or string?
Say i have:

char test[5] = {'a','b','c','d','e'};

Is it possible to delete 'a' for example?

Thanks!

- Neil.

[Lindley]

What you would need to do in that case is shuffle b, c, d, and e over one space, and then mark the array as being one shorter.

This is in general why erasing an element from an array is O(n). Other data structures are better for frequent erasures at arbitrary positions.

Of course, erasing an element from the *end* of an array is O(1), since you only need to reduce the apparent array size by 1.

[Neil.Dyke]

Thanks for your reply, I understand. Would using a std::string in this case be more efficient (as in faster to make)?

[Lindley]

Using a std::string is almost always better than using a plain char array. However, erasing an arbitrary character isn't going to be any faster, because it's doing the same thing under the hood.

Perhaps if you explain your problem at a high level, an appropriate data structure could be suggested.

[Neil.Dyke]

Sure, here's the code. Its a program that reads a file. The first to lines are int, first int states how many rows there are after the 2 lines that have been read. The second int says how much colums there are.
Each cell in the matrix is a char (one letter of the alphabet).
I need to output the letters of the alfabet that haven't been used. To do this i want to create a string list with the alfabet, then for each char read, check if its in the list, then if it is, remove it from the list. Hopefully this makes sense, here's the code:

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int main()
{
ifstream diagram;
diagram.open("diagram.in");
char alfabet[26] = ;
string line;

getline(diagram,line);
int one = atoi(line.c_str());
getline(diagram,line);
int two = atoi(line.c_str());

for(int i=0;i<=two;i++)
{
getline(diagram, line);
for (int n=0;n<=two;n++)
{
char toremove = line[n];
// here the program has to check wheter the char is inside alfabet, and if it is delete it
}
}
// output remaining characters from alfabet
return 0;
}

- Neil

[Lindley]

I would suggest using a bool[26] array, initialized to false, and just set the corresponding index to true whenever you encounter a particular letter. One way to get the index would be

index = tolower(c) - 'a';

Alternatively, you could do something akin to your current plan but more efficient if you use a std::set<char> rather than an array, since erasing an element from a set is O(log n).

[Neil.Dyke]

Thanks Lindley!

[monarch_dodra]

Actually, to keep into the spirit of the original design, a std::set<char> would be perfect. It is the perfect structure, as described by your need.

Now, if you reword your problem, Lindley's suggestion is better, but if just keeping in mind with finding letters and removing them, a set is an excellent structure.