1

I have the following classes in a program.

class Class1 {

    public:

        boost::ptr_vector<Class2> fields;
}

class Class2 {

    public:

        std:string name;
        unsigned int value;
}

I want to write a member function in Class1 that returns a reference or pointer to an element in fields based on Class2's name variable. I don't have to be concerned with the lifetime of the objects in the container.

Currently, I am returning an iterator to the element I want after the function searches from the start of the vector to the element.

boost::ptr_vector<Class2>::iterator getFieldByName(std::string name) {

    boost::ptr_vector<Class2>::iterator field = fields.begin();

    while (field != fields.end()) {

        if (field->name.compare(name) == 0) {
            return field;
        }
        ++field;
    }

    return fields.end();
}

The problems that I'm facing are:

(1.) I need to have fast random access to the elements or the program sits in getFieldByName() too long (a boost::ptr_vector<> is too slow when starting at the beginning of the container)

(2.) I need to preserve the order of insertion of the fields (so I can't use a boost::ptr_map<> directly)

I have discovered Boost::MultiIndex and it seems like it could provide a solution to the problems, but I need to use a smart container so that destruction of the container will also destruct the objects owned by the container.

Is there anyway to achieve a smart container that has multiple methods of access?

burtmacklin16
  • 715
  • 2
  • 13
  • 31
  • Dereference the iterator. The value it returns is a reference. Return that, also as a reference. – Brent Oct 21 '14 at 21:11
  • @Brent I will definitely do that in my final function. I'm more concerned with having fast access to the data and preserving the insertion order – burtmacklin16 Oct 21 '14 at 21:14
  • 1
    Oh, I see. You want O(log(n)) lookup instead of O(n). Barry's answer seems pretty good. – Brent Oct 21 '14 at 21:15
  • 1
    Also, this: http://stackoverflow.com/questions/1098175/a-stdmap-that-keep-track-of-the-order-of-insertion – Brent Oct 21 '14 at 21:17
  • @Brent that's precisely it. Barry's answer wouldn't work – sehe Oct 22 '14 at 00:31
  • Why not? It seems reasonable. Also, looking them up by string is probably not great either. If you want great performance, maybe you should do a hash of the string and search by that, thus avoiding repeated string comparisons. (You'll have to handle collisions linearly of course). Or maybe dynamic perfect hashing if the data doesn't change often, which can give you low cost constant time. – Brent Oct 22 '14 at 14:31
  • 2
    Assuming inserts in the ptr_vector are at the end, you can index it with a map, pairing the name with the offset (size before the push_back()). Look up the name in the map and use the paired offset to index into the vector. Deletions get a bit hairy as you'd have to reindex the elements after the deletion point. – arayq2 Oct 22 '14 at 16:02
  • Do you definitely need a smart container, rather than a container of smart pointers? – Jonathan Wakely Oct 22 '14 at 16:07
  • @JonathanWakely - I am using a smart container to eliminate the overhead of reference counting since the container is used to store thousands of objects. – burtmacklin16 Oct 22 '14 at 16:20
  • @packersfan16, `unique_ptr` has no reference counting and no overhead (but is C++11 only, unless you use `boost::intrusive::unique_ptr` or some other implementation) – Jonathan Wakely Oct 22 '14 at 18:32

1 Answers1

0

You can use two containers. Have a boost::ptr_map<> that stores the actual data, and then have a std::vector<> that stores pointers to the nodes of the map. 

boost::ptr_map<std::string, Class2> by_field;
std::vector<Class2 const*> by_order;

void insert(Class2* obj) {
    if (by_field.insert(obj->name, obj).second) {
        // on insertion success, also add to by_order
        by_order.push_back(obj);
    }
}

This will give you O(lg n) access in your getFieldByName() function (just look it up in by_field) while also preserving the order of insertion (just look it up in by_order).

Barry
  • 286,269
  • 29
  • 621
  • 977
  • You cannot do any such thing since both ptr_map and ptr_vector own their element data. – sehe Oct 21 '14 at 23:32
  • Excuse me, `std::vector` for whatever the right value of `Node` is. Was that really worth a downvote? – Barry Oct 22 '14 at 12:36
  • I don't see why not. This is a lot of hand waving and also incidentally incorrect for the reason I pointed out. There have been comments with more merit – sehe Oct 22 '14 at 15:11
  • @Barry: Perhaps editing that into the answer so it at least wasn't blatantly wrong would give at least some chance of getting the down-vote removed. – Jerry Coffin Oct 22 '14 at 15:21