Custom Container

[Cinolt]

I need a container that
1) holds a collection of objects of an arbitrary type, such as:

class foo{
  int a;
  int b;
};

2) adds objects in accordance with a sorting algorithm,
3) removes objects at arbitrary positions within the collection,
4) is able to access the same object regardless of the adding/removing of objects within the collection, and
5) does not have the application specify "keys".

At first glance, map (http://www.cplusplus.com/reference/map/map/) seems to provide the closest to what I want, however it does not satisfy (2) and (5), as map's comparison algorithm compares the Keys, rather than the mapped values, and the collection must be sorted according to the objects themselves. Also, the application must specify keys using map.

Any ideas how I can implement this using STL? Do I really have to implement an entirely new class?

[Daleth]

std::set<T>
http://www.cplusplus.com/reference/set/set/?kw=set

It technically uses keys, but the key is the object itself.

[Cinolt]

There can be multiple of the same objects within the collection, so I can't use set.

[Daleth]

Multiset?
http://www.cplusplus.com/reference/set/multiset/begin/

[Cinolt]

The objects can be modified once in the container. Assume anything that wasn't listed is not a restriction.

[Cubbi]

is able to access the same object regardless of the adding/removing of objects within the collection

In other words, erasing and inserting elements at arbitrary locations does not invalidate references to elements? This leaves you with sorted list and set/multiset/map/multimap. Sorted lists have limited uses (no binary search) and you don't want keys and want multiples, so multiset is the answer.

The objects can be modified once in the container

This contradicts the requirement to be sorted, unless each "modification" is modification followed by re-sorting (which translates, in case of multiset, to erase + modify + insert with a hint)

[Cinolt]

I should have been more clear, I do want keys but it's the container provides the keys; the application doesn't specify them.

Any modifications to any single object ensures that it's still sorted correctly, i.e. the user will only modify attributes that aren't involved in the sorting process, or he modifies it in such a way that the entire collection is still sorted correctly.

List doesn't work because elements are accessed by its position in the sequence. So for example, for a sequence of 10 objects, I add an object at position 7, I remove an object at position 1, then I try to access the object at position 7 and it will not be the same object I previously added.

set/multiset doesn't work because the objects must be modifiable, which I guess could be bypassed by removing an object, then adding the modified object. But set doesn't work because elements are accessed by value, rather than by a key. I want keys.

map doesn't work because it sorts by keys, rather than by the actual contents of the objects.

[cire]

Cinolt wrote:

set/multiset doesn't work because the objects must be modifiable, which I guess could be bypassed by removing an object, then adding the modified object. But set doesn't work because elements are accessed by value, rather than by a key. I want keys.

map doesn't work because it sorts by keys, rather than by the actual contents of the objects.

Contradict much?

[Cinolt]

How so? I want to access elements by keys, but I want the collection to be sorted according to the actual contents of the objects.

[Disch]

How so? I want to access elements by keys, but I want the collection to be sorted according to the actual contents of the objects.

This is somewhat contradictory.

The whole point of accessing by key is so that it can be sorted by key. This allows the lookup by key to be quick because it can do a binary search for the key. O(log(n))

If the container is not sorted by key, then you just have to do a linear search across the entire container to find the value associated with a given key: O(n)


It sounds to me like the closest thing you're going to get with this with standard containers is a multimap where you end up duplicating keys and values:

class FooKey
{
    int keyval1;
    int keyval2;
};

class FooVal
{
    FooKey key;
    int val1;
    int val2;
};

std::multimap<FooKey, FooVal> mm;

FooVal x = whatever;
mm[x.key] = x;

But this, aside from being wasteful and just overall kind of junky, still suffers from the "can't resort itself if you change the value" problem. The only way to get a resort is to remove the element and add it with a new key. This is going to be true of any sorted container... or any container which uses a key. The key cannot be changed.

[Daleth]

Edit: Forget this post.

[Cubbi]

on a side note:

the user will only modify attributes that aren't involved in the sorting process

this is sometimes implemented for the values of a set by declaring those attributes mutable.

In case you really need to attach an index to a differently-ordered storage or do something else beyond what the C++ containers can do, take a look at boost: http://www.boost.org/doc/libs/release/libs/multi_index/doc/index.html

[Cinolt]

Looks like I'm going to have to implement a new class.

I'm still surprised that this isn't possible with STL.

All I'm asking for is a collection of objects sorted by the objects themselves, I want to be able to add an object then be able to access that same object (this is the only reason why I want "keys" in the first place, because without a "key", the position of objects get shifted as objects are added/removed). None of the standard containers can do this.

[Cubbi]

as you add/remove objects to a set/multiset, you can still access your original object using its original iterator, reference, or pointer. That's one of their core properties.

[cire]

All I'm asking for is a collection of objects sorted by the objects themselves, I want to be able to add an object then be able to access that same object (this is the only reason why I want "keys" in the first place, because without a "key", the position of objects get shifted as objects are added/removed). None of the standard containers can do this.

As previously mentioned, std::set/std::multiset do this just fine. What you cannot do is modify the objects and expect them to be automatically resorted.

If the object itself must reside in the same place in memory, store a (smart) pointer or reference wrapper in the container and move that around instead of the actual object.

"All problems in computer science can be solved by another level of indirection"

[Cinolt]

Ah, now I see. Guess I was stuck in the C mindset (just switching over).