Printable View
Hello,
I have a class called CTestObject and it has one variable int id. I want to add instances of this to an std container and be able to:
1. quickly determine if the value of "int id" exists in the container and update the object
or
2. add a new object to the container
Which std container is the best for this application? What method should I use to search the container for the object id?
Thanks!
Do you mean that every instance of CTestObject class is unique (has a unique int id)?
Have you implemented a copy ctor ans assignment operator to support object uniqueness?
Every instance may not be unique...
Do you want to add a new object in the middle of the container?
If yes, you could consider deque std::deque or std::list. Otherwise I would suggest std::vector. For 1. you would could do a simple loop over the entire container to look for the id. The efficiency could be improved by keeping the container sorted, but then...
There are containers that will do the sorting for you as soon as elements are added:
std::map and std::set are 'automatically' sorted, but they only keep unique keys/elements resp.. If you dont want to keep duplicate CTestObjects, then std::set will work well for you. If you do need to consider duplicates, then look at std::multimap, or suggestions in previous paragraph.
If you use one of the former suggestions, you could use std::find, or manually loop over the container yourself. Or sort and then use binary_search.
If you use a map or a set, you can use their member method find(...)
Ok so here is a quick example I made:
But I get a compilation error:Code:#include <vector>
using namespace std;
class Test
{
public:
Test(int id) { id_=id; };
~Test() {};
void UpdateTest(Test* update) { value_=update->value_; };
int id_;
int value_;
};
int main()
{
vector<Test*> testvec;
Test* test1 = new Test(1);
Test* test2 = new Test(2);
Test* test3 = new Test(3);
testvec.push_back(test1);
testvec.push_back(test2);
testvec.push_back(test3);
vector<Test*>::iterator it;
Test* findtest = new Test(2);
it=find(testvec.begin(), testvec.end(), findtest->id_);
if(it != testvec.end())
{
(*it)->UpdateTest(findtest);
delete findtest;
}
else
testvec.push_back(findtest);
// cleanup
delete test1;
delete test2;
delete test3;
}
1>c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\algorithm(41): error C2446: '==' : no conversion from 'const int' to 'Test *'
I think I need to use find_if(). Can anyone show me an example of it with respect to what I am trying to accomplish?
Thanks!
The first thing you must do is to fix the "compilation error"! :cool:Quote:
Originally Posted by aseminov
so basically you are sarcastic in general and not helpful?
It would be much more helpful if you showed the exact error message and the line where it happened. :cool:Quote:
Originally Posted by aseminov
1) There is no reason to use vector<Test*> . Store objects instead.
2) How many elements do you expect to have ? If there are many
elements, a linear search (i.e. std::find) is slow
3) You mention the non-uniqueness, when you are searching for an
element and want to update it, which element would you choose ?
find -- Look at the docs for find. What are you comparing here (the error message says):
ViggyCode:it=find(testvec.begin(), testvec.end(), findtest->id_);
From the way you've described the requirements, multimap sounds like the best container.
If you listen again unordered_multimap sounds even better.Quote:
Originally Posted by GCDEF
Quote:
Originally Posted by GCDEF
He wants update if already present, so... an (unordered_)map would be best, no?Quote:
Originally Posted by nuzzle
EDIT:
Or why not just an (unordered_)set? If the key is in value...?
You are correct: Your container contains pointers to object, yet you are looking for an integer.Quote:
Originally Posted by aseminov
There are two solutions:
-The bad one: Make your test implicitly constructable from an integer. This may lead to some unexpected behavior if you are not careful. I really shouldn't even be mentioning this method.
The second solution would be to learn about functors! A funtor is like a function, but it is actually an object that can have a state. To "call the functor", you actually call that object's operator(). Here is an example of a functor that can be instanciated with a specific int, and then can be called to print that int:
In your case, you'd want to use a functor like this:Code:#include <iostream>
class printer_functor
{
public:
printer_functor(int i) : i(i){}
void operator()()
{std::cout << i;}
private:
int i;
};
int main()
{
printer_functor p(5); //Freate a functor called "a" initialized with 5
p(); //"call" a
}
Code:class Compare_Test_Id
{
public:
Compare_Test_Id(int i) : i(i){}
bool operator()(const Test* i_other)
{return i == i_other->id_;}
private:
int i;
};
...
int main()
{
...
it = find_if(testvec.begin(), testvec.end(), Compare_Test_Id(findtest->id_));
...
}
This depends on how you interpret the information in post #3.Quote:
Originally Posted by monarch_dodra
If it means keys are not unique then an unordered_multimap is best, otherwise an unordered_map.
That depends on how the information is "packaged" when used with the container.Quote:
Or why not just an (unordered_)set? If the key is in value...?
If using an unordered set/multiset results in an unnecessary creation of a CTestObject object just to access the container then the unordered map/multimap alternative is better, otherwise not.
Sorry if I gave some ambiguous information. The key values will be unique. They are just an idnetifier, so they can be repeated so that an object can be updated.
See, that doesn't make sense to me:Quote:
Originally Posted by aseminov
You say the key values are unique, yet that identifiers can be repeated?
----
In my opinion, once you start using objects that are identifiable, you have to bind their creation to a factory, and prevent copy construction/assignment between the instances.
This way, you are guaranteed that no two instances share the same ID.
You can also further refine your factory to retrieve existing instances by ID.
This would be a "usecase" example:
The neat part is that this works, and you neither have to worry about id collisions, nor do you even have to worry about about ordering (you could even use an unordered_set, actually)Code:typedef TestFactory::SharedPtrType TestPtr;
//The container
std::set<TestPtr> SetOfTests;
//Create a new istance, with a new unique ID
SharedPtrType sp = TestFactory::Instance()->CreateTestInstance();
//Put it in the container
SetOfTests.insert(sp);
//....
//Later... Is the instance 5 inside the container?
//....
SharedPtrType sp = TestFactory::Instance()->GetExistingInstance(5);
if( !sp )
{
//No instance with an id 5 have even been created
return;
}
std::set<TestPtr>::iterator it = SetOfTests.find(sp);
if(it == SetOfTests.end())
{
//The instance with ID 5 is NOT inside SetOfTests.
}
else
{
//The instance with ID 5 is inside SetOfTests.
}
Chances are you'll have to put an [unordered_]map of int to weak_ptr inside the factory, for efficient retrieval using GetExistingInstance, but the point is that once the factory is nice and wrapped up, the user of the factory does not need to worry about those kind of details.
----
Anyways, that's one way of going at it, there are infinite different approaches out there. My 0.02$
ok here is an example of input data
id x position y position
---------------------------------
1 0 2
2 3 -7
I might get the messages above in one cycle.. then the next set of messages will be:
id x position y position
---------------------------------
2 3 -10
3 2 2
As you can see this time I did not get a position update form id number 1.. I have a new position for id number 2.. and a new element id number 3..
do you understand now?
Thanks
Sounds like all you really need is a map and operator[]... ?Code:#include <tuple>
#include <unordered_map>
int main()
{
std::unordered_map<size_t, std::tuple<int, int>> my_map;
my_map[2] = std::make_tuple(3, 2);
}
Dear aseminov,
please, have a look at what you have posted (from your OP til the last one):Quote:
Originally Posted by aseminov
Quote:
Originally Posted by aseminov
So, will "Every instance" be always unique or it "may not be unique" and "an be repeated"? :confused:Quote:
Originally Posted by aseminov
Besides, your wrote that you "have a class called CTestObject and it has one variable int id"... but now you show an example with two additional variables (x, y). So are they also members of CTestObject or what? And what is the your class CTestObject supposed to do?
No I don't understand anything now. :eek:Quote:
Originally Posted by aseminov
Ok I am very sorry, here is some example code of exactly what I will be doing:
I realize the Insert(AddElement) for vector is O(n) and could be faster if I use a map which would be O(logn). I would say my data set will be only a few hundred members at most. Should I consider using a map?Code:#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
class Test
{
public:
Test(int id, int value) { id_=id; value_=value; };
~Test() {};
void UpdateTest(Test* update) { value_=update->value_; };
int id_;
int value_;
};
vector<Test*> testvec;
void AddElement(Test* element)
{
bool foundElement=false;
for(vector<Test*>::iterator it=testvec.begin(); it!=testvec.end(); it++)
{
if((*it)->id_ == element->id_)
{
(*it)->UpdateTest(element);
cout << "Updating element id: " << element->id_ << " with value: " << element->value_ << endl;
delete element;
foundElement=true;
break;
}
}
if(!foundElement)
{
cout << "Adding new element id: " << element->id_ << " with value: " << element->value_ << endl;
testvec.push_back(element);
}
}
int main()
{
Test* test1 = new Test(1, 8);
Test* test2 = new Test(2, 0);
Test* test3 = new Test(3, 4);
Test* update = new Test(2, 6);
AddElement(test1);
AddElement(test2);
AddElement(test3);
AddElement(update);
}
Thanks!
Well, if you #include <unordered_map> and use a std::unordered_map, insertion will be O(1) in the average case.Quote:
Originally Posted by aseminov
Why are you still using dynamic memory allocation to create Test objects? The code looks more like Java or C# code then it does C++ code. It even comes with the inevitable memory leak that Java-like C++ code seems to always have.Quote:
Originally Posted by aseminov
The Test class has just two int members, and there is no indication with your code that you're going to start deriving from Test (no virtual functions). In addition your AddElement function can be much shorter using algorithms.
This code basically does the same as your previous code. No calls to new or delete, and the AddElement function is simpler and shorter.Code:#include <algorithm>
#include <vector>
#include <iostream>
class Test
{
public:
Test(int id, int value) : id_(id), value_(value) { }
void UpdateTest(const Test& update) { value_= update.value_; };
int id_;
int value_;
};
typedef std::vector<Test> TestVect;
struct FindByID
{
int m_id;
FindByID(int id) : m_id(id) {}
bool operator()(const Test& t) const
{
return t.id_ == m_id;
}
};
std::vector<Test> testvec;
void AddElement(const Test& element)
{
TestVect::iterator it = std::find_if(testvec.begin(), testvec.end(), FindByID(element.id_));
if ( it != testvec.end() )
it->UpdateTest(element);
else
testvec.push_back(element);
}
int main()
{
Test test1(1, 8);
Test test2(2, 0);
Test test3(3, 4);
Test update(2, 6);
AddElement(test1);
AddElement(test2);
AddElement(test3);
AddElement(update);
}
Regards,
Paul McKenzie