best std container class for my application?

[aseminov]

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!

[VictorN]

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?

[aseminov]

Every instance may not be unique...

[Amleto]

Do you want to add a new object in the middle of the container?


If yes, you could consider deque std:eque 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(...)

[aseminov]

Ok so here is a quick example I made:

#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!

[VictorN]

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"!

[aseminov]

so basically you are sarcastic in general and not helpful?

[VictorN]

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.

[Philip Nicoletti]

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 ?

[MrViggy]

find -- Look at the docs for find. What are you comparing here (the error message says):

it=find(testvec.begin(), testvec.end(), findtest->id_);

Viggy

[GCDEF]

From the way you've described the requirements, multimap sounds like the best container.

[nuzzle]

From the way you've described the requirements, multimap sounds like the best container.

If you listen again unordered_multimap sounds even better.

[monarch_dodra]

From the way you've described the requirements, multimap sounds like the best container.

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...?

[monarch_dodra]

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:

#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:

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_));
  ...
}

[nuzzle]

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.

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.