-
best std container class for my application?
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!
-
Re: best std container class for my application?
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?
-
Re: best std container class for my application?
Every instance may not be unique...
-
Re: best std container class for my application?
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(...)
-
Re: best std container class for my application?
Ok so here is a quick example I made:
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;
}
But I get a compilation error:
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!
-
Re: best std container class for my application?
Quote:
Originally Posted by
aseminov
O...
But I get a compilation error on the if(it) line. How am I suppossed to check if find() returned a match or not?
The first thing you must do is to fix the "compilation error"! :cool:
-
Re: best std container class for my application?
so basically you are sarcastic in general and not helpful?
-
Re: best std container class for my application?
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:
-
Re: best std container class for my application?
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 ?
-
Re: best std container class for my application?
find -- Look at the docs for find. What are you comparing here (the error message says):
Code:
it=find(testvec.begin(), testvec.end(), findtest->id_);
Viggy
-
Re: best std container class for my application?
From the way you've described the requirements, multimap sounds like the best container.
-
Re: best std container class for my application?
Quote:
Originally Posted by
GCDEF
From the way you've described the requirements, multimap sounds like the best container.
If you listen again unordered_multimap sounds even better.
-
Re: best std container class for my application?
Quote:
Originally Posted by
GCDEF
From the way you've described the requirements, multimap sounds like the best container.
Quote:
Originally Posted by
nuzzle
If you listen again unordered_multimap sounds even better.
He wants update if already present, so... an (unordered_)map would be best, no?
EDIT:
Or why not just an (unordered_)set? If the key is in value...?
-
Re: best std container class for my application?
Quote:
Originally Posted by
aseminov
it=find(testvec.begin(), testvec.end(), findtest->id_);[/CODE]
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().
You are correct: Your container contains pointers to object, yet you are looking for an integer.
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:
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
}
In your case, you'd want to use a functor like this:
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_));
...
}
-
Re: best std container class for my application?
Quote:
Originally Posted by
monarch_dodra
He wants update if already present, so... an (unordered_)map would be best, no?
This depends on how you interpret the information in post #3.
If it means keys are not unique then an unordered_multimap is best, otherwise an unordered_map.
Quote:
Or why not just an (unordered_)set? If the key is in value...?
That depends on how the information is "packaged" when used with the container.
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.
-
Re: best std container class for my application?
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.
-
Re: best std container class for my application?
Quote:
Originally Posted by
aseminov
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:
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:
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.
}
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)
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$
-
Re: best std container class for my application?
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
-
Re: best std container class for my application?
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);
}
Sounds like all you really need is a map and operator[]... ?
-
Re: best std container class for my application?
Dear aseminov,
please, have a look at what you have posted (from your OP til the last one):
Quote:
Originally Posted by
aseminov
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
...
Quote:
Originally Posted by
aseminov
Every instance may not be unique...
Quote:
Originally Posted by
aseminov
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.
So, will "Every instance" be always unique or it "may not be unique" and "an be repeated"? :confused:
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?
Quote:
Originally Posted by
aseminov
ok here is an example of input data
id x position y position
---------------------------------
1 0 2
2 3 -7
...
do you understand now?
No I don't understand anything now. :eek:
-
Re: best std container class for my application?
Ok I am very sorry, here is some example code of exactly what I will be doing:
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);
}
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?
Thanks!
-
Re: best std container class for my application?
Quote:
Originally Posted by aseminov
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?
Well, if you #include <unordered_map> and use a std::unordered_map, insertion will be O(1) in the average case.
-
Re: best std container class for my application?
Quote:
Originally Posted by
aseminov
Ok I am very sorry, here is some example code of exactly what I will be doing:
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.
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.
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);
}
This code basically does the same as your previous code. No calls to new or delete, and the AddElement function is simpler and shorter.
Regards,
Paul McKenzie