Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C++
Hi people,
 
this maybe an easy question but maybe some of you can say the answer.
 
I am looking for a data structure which allows to delete a *specific* element from a set? which data structure should I use for it?
 
For example using stack is not quite right for me because it allows to delete only the *top* element, not element say which is located in the middle.
 
if I use an array, and delete say an element in the middle, then I have to rearrange the elements in the array so that I put an existing element in the place of the element I deleted; I want the data structure to do this automatically.
 
hope i was clear. thanks!
Posted 8-Dec-12 13:01pm
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 1

You may us the set template in STL.
http://www.cplusplus.com/reference/set/set/[^]
Modifiers:
insert
Insert element (public member function)
erase
Erase elements (public member function)
there is some sample code:
http://www.cplusplus.com/reference/set/set/erase/[^]
  Permalink  
Comments
Matra Divat at 9-Dec-12 8:38am
   
I have problems using the Set with a custom class. Say set< CustomClass > myVar; probably because CustomClass must overload the < or () operators. I am doing this using this example: http://www.cplusplus.com/reference/set/set/set/ e.g., using classcomp but still get a runtime error: "invalid operator <" can you help??
Cashey Wen at 9-Dec-12 12:31pm
   
Runtime error? You mean your code got compiled with no error but when it runs error happend?
If the compiler shows "invalid operator <", it is possible you didn't write the classcomp in a right way, and that's not runtime error.
 
Can you let me see some of your code?
Matra Divat at 9-Dec-12 13:09pm
   
Hi, yes I get an "Assertion failed" error with the message I described.
 
ps. here is some of the code.
 
struct classcomp {

bool operator() (const CustomClass& lhs, const CustomClass& rhs) const
{
return true; // order doesn't matter much for me actually in this case
}

// bool operator <(const CustomClass& lhs)
// {
// return true;
// }
// I get the error specified even if I uncomment what I wrote above
 
};
 

class OtherCustomClass
{
private:
 

set < customclass,classcomp > m_variable;
 

the problem occurs when I try to call "insert" method of Set, with variable: CustomClass
 
m_variable.insert(customObject); // cutomObject is variable of type CustomClass
Cashey Wen at 9-Dec-12 21:03pm
   
Hi, thought the order of elements doesn't matter for you, it does matter for STL.
The STL set uses a "r-b tree" to store all the elements, when you insert an element, the set have to compare the new element with all existing element.
 
The assertion should have told you a file name and a line number about where it happened, you can check it up at the corresponding file, if you do that, you'll probably find sth like this:
 
if (!_Pred(_Left, _Right))
return (false);
else if (_Pred(_Right, _Left))
_DEBUG_ERROR2("invalid operator<", _File, _Line);
return (true);
 
The code shown above is from the header algorithm. This code snippet use the overloaded operator < to check if _Left is smaller than _Right, if _Left is smaller, it will swap the two operand to check if _Right is smaller than _Left.
 
If _Left is smaller than _Right, and _Right is also smaller than _Left, it will assert your < operator is invalid.
 
So if you still want to use set, you have to provide a valid < operator, you can simply return the compare result of one of the CustomClass's members.
 
struct classcomp {

bool operator() (const CustomClass& lhs, const CustomClass& rhs) const
{
return lhs.smdata < rhs.smdata; // smdata is a member of CustomClass in this case
}
Matra Divat at 11-Dec-12 15:29pm
   
Hi thanks - what you said works (I would have hardly guessed it by myself). At least it compiles now and runs and some elements are added to it. But I still have some issue, if I for instance add 4 elements using insert() only one is added... any idea what am I maybe doing wrong?? Thanks. ps. Here is my classcomp():
struct classcomp
{
bool operator() (const CStudent& lhs, const CStudent& rhs) const
{
if(lhs.getID()>rhs.getID())
return true;
else
return false;
}
 
};
I add elements using insert() function, and retrieve them using:
set< CustomClass, classcomp >::iterator it;
 
thanks once again.
Cashey Wen at 12-Dec-12 5:42am
   
I think you might be inserting 4 duplicated elements. STL set automatically removes all duplicated elements, this guarantees elements stored are unique.
 
According to your classcomp, if lhs.getID() is equal to rhs.getID(), the set will regard lhs and rhs as two duplicated elements, only one of them will be stored.
 
If you have to store dumplicated elements, set is not the solution. Sorry for my mistake, I thought "delete a *specific* element from a set" means a set with no dumplicated elements.
 
Well, if it is a question like this, this could be easier. Just use list, I got an example for you.
 
http://www.cplusplus.com/reference/list/list/
 
#include <iostream>
#include <list>
using namespace std;
 
class MyClass
{
public:
MyClass(int _a, int _b, string _c): a(_a), b(_b), c(_c){}
bool operator ==(MyClass mc)
{
if (a == mc.a && b == mc.b && c == mc.c)
{
return true;
}
return false;
}

int a;
int b;
string c;
};
 
int main()
{
list mylist;
list::iterator iter;
 
MyClass mc1(1, 2, "abc");
MyClass mc2(2, 3, "ccc");
MyClass mc3(3, 4, "bbb");

mylist.push_back(mc1);
mylist.push_back(mc2);
mylist.push_back(mc3);

cout << "before deleting:" << endl;
for (iter = mylist.begin(); iter != mylist.end(); iter++)
{
cout << (*iter).a << " " << (*iter).b << " " << (*iter).c << endl;
}

mylist.remove(mc3);
cout << "after deleting:" << endl;
for (iter = mylist.begin(); iter != mylist.end(); iter++)
{
cout << (*iter).a << " " << (*iter).b << " " << (*iter).c << endl;
}

cin >> ws;
return 0;
}
Matra Divat at 12-Dec-12 6:15am
   
Hi thanks for your reply. Indeed actually the getID() method will always return 0 if I do not initialize it to a different value (and this might be a problem, since I don't). ps. I will look at your other suggestion too. pps. I am not sure if I allow duplicate elements, the custom class is of "students" so they may have different components, e.g., such as name surname, completely similar entries are rare I believe in my case. thanks again.
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 2

You can remove a random element from nearly all container classes, but not from a queue or a stack. It could be list, vector, map, etc. I did not count native C/C++ array, which is not a container class. What container class should you choose? It depends on your other requirements.
 
—SA
  Permalink  

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
0 OriginalGriff 295
1 DamithSL 295
2 Sergey Alexandrovich Kryukov 207
3 Peter Leow 155
4 Afzaal Ahmad Zeeshan 154
0 OriginalGriff 7,460
1 DamithSL 5,519
2 Sergey Alexandrovich Kryukov 4,954
3 Maciej Los 4,936
4 Kornfeld Eliyahu Peter 4,514


Advertise | Privacy | Mobile
Web04 | 2.8.141223.1 | Last Updated 8 Dec 2012
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100