best std container class for my application?

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

[monarch_dodra]

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:

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$

[aseminov]

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

[monarch_dodra]

#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[]... ?

[VictorN]

Dear aseminov,
please, have a look at what you have posted (from your OP til the last one):

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

Every instance may not be unique...

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

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?

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.

[aseminov]

Ok I am very sorry, here is some example code of exactly what I will be doing:

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

[laserlight]

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.

[Paul McKenzie]

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.

#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