How to use self-defined structure in C++ Map

Question

I want to use a C++ map structure, such as map<vector<DFSCode>, vector<PDB>> candidate, DFSCode and PDB are two structures I define.

class DFS {
public:
    int from;
    int to;
    int fromlabel;
    int elabel;
    int tolabel;
    DFS(): from(0), to(0), fromlabel(0), elabel(0), tolabel(0) {};
};

struct DFSCode: public vector <DFS> {
public:
    void push (int from, int to, int fromlabel, int elabel, int tolabel)
    {
        resize (size() + 1);
        DFS &d = (*this)[size()-1];

        d.from = from;
        d.to = to;
        d.fromlabel = fromlabel;
        d.elabel = elabel;
        d.tolabel = tolabel;
    }
    void pop () { resize (size()-1); }
};

class PDB {
public:
    unsigned int tid;
    unsigned int gid;
    void push(int did, int vid, int vlabel)
    {
        tuple[did].vid = vid;
        tuple[did].vlabel = vlabel;
    }
    PDB(): tid(0), gid(0), tuple(0) {};
};

I will generate a lot of data which contain vector<DFSCode> and PDB, since one vector<DFSCode> may have many PDB, I want to use vector<PDB> to store them. What I want to do is:

vector<DFSCode> tempdfscodeList;
PDB             temppdb;
map<vector<DFSCode>, vector<PDB>> candidate;
for each `vector<DFSCode>` and `PDB` pair I generate
    candidate[tempdfscodeList].push_back(temppdb);

The first question is: Does above code satisfied my expectation that "one vector<DFSCode> contain many PDB"?

The second question is: I know I have to implement a comparable method of map, since I use vector<DFSCode> as my key, but I don't know how to implement. I try to write one. But it seems not satisfied my expectation that "one vector<DFSCode> contain many PDB", can anyone help me? :)

class dfscodeListCompare {  // compare vector<DFSCode>
public:
    bool operator() (const vector<DFSCode> &c1, const vector<DFSCode> &c2) const
    {
        for(int I = 0; I < c1.size(); I++) {
            if(c1[I].size() == c2[I].size()) {  // the size must be the same
                for(int j = 0; j < c1[I].size(); j++) {
                    if((c1[I][j].from != c2[I][j].from) || (c1[I][j].to != c2[I][j].to) || (c1[I][j].fromlabel != c2[I][j].fromlabel) || (c1[I][j].elabel != c2[I][j].elabel) || (c1[I][j].tolabel != c2[I][j].tolabel))
                        return false;   // if there exist one different
                }
            }
            else
                return false;
        }
        return true;    // pass all condition
    }
};

Why not add a proper constructor to `DFS` which takes the parameters you want, and remove the custom `push_back`. — Andreas Brinck, Mar 26 '12 at 08:15
STL containers do not have virtual destructors, it's impossible to clean them up properly with only a pointer to those classes. See [this answer](http://stackoverflow.com/a/2034936/148481) — Luca Martini, Mar 26 '12 at 08:16
Does you mean i can't use `candidate[tempdfscodeList].push_back(temppdb);`?? Could you point the error?? Thanks:) — LoveTW, Mar 26 '12 at 08:23
@LucaMartini: That is not a valid argument, because your argument implies only those classes can be derive from, which have `virtual` destructors. But that is totally wrong. One can derived from non-polymorphic classes as well (classes without virtual destructors). All that you need to make sure that don't delete them polymorphically : i.e don't delete the derived class object, through the base class pointer. — Nawaz, Mar 26 '12 at 08:24
Can you give me some advisement how can i implement "`one vector contain many PDB`", what structure should i use? Thanks:) — LoveTW, Mar 26 '12 at 08:35
@Nawaz It all depends on design. There are certainly classes with non-virtual destructors which are designed to be base classes---`std::iterator` comes to mind. `std::vector` is _not_ one of these; it has behavior, but no virtual functions. In almost all cases, encapsulation would be better design. — James Kanze, Mar 26 '12 at 08:40
You can only implement "one vector contain many PDB by having DFSCode contain one or more PDBs. — juanchopanza, Mar 26 '12 at 08:59
@JamesKanze: Is there anythihg inherently wrong deriving from `std::vector` if it it is not treated polymorphically? — Nawaz, Mar 26 '12 at 09:04
@Nawaz is there any way of guaranteeing that it won't be treated polymorphically? (Things like `std::iterator` work because the class doesn't have any sort of interface whatsoever; it would simply never occur to anyone to take an `std::iterator<>*`.) — James Kanze, Mar 26 '12 at 09:49
@JamesKanze: That means, if a class doesn't have `virtual` destructor but it has some member functions, then it should not be derived from? — Nawaz, Mar 26 '12 at 09:56
@Nawaz It means that if a class was not expressedly designed to be a base class, it should not be derived from. There are a lot of classes with `virtual` destructors which you shouldn't derive from. There are classes with functions and data (and perhaps a `protected` destructor) which you can safely derive from. It's a question of design. — James Kanze, Mar 26 '12 at 10:02
@JamesKanze: That is very vague, so I couldn't really understand it. I mean, how can I know if a class is designed to be derived from? And if I write a class, how can I convey this? What are the characteristics or derivable classes? Specifically, what is there in `std::vector` which makes it not-to-be-derived-from class? — Nawaz, Mar 26 '12 at 10:06
@Nawaz You document it. And `std::vector` is not documented with regards to how it behaves if you derive from it, and what it might mean to derive from it, so you shouldn't derive from it. — James Kanze, Mar 26 '12 at 12:24
@JamesKanze: Even before documentation, I myself need to know the reasons (i.e the characteristics of the class) based on which I can say that "okay, this class can be derived from". How can I do that? — Nawaz, Mar 26 '12 at 13:03
@Nawaz It's simple: if you design the class to serve as a base, you can derive from it. If you don't, you can't. For classes you don't write yourself, if it's not documented to serve as a base, you shouldn't derive from it. (The documentation can be indirect: if there's an abstract virtual function, the class is probably designed to be used as a base. Of course, if the function is named `f` or `doIt`, and there's no documentation as to what it should do...) — James Kanze, Mar 26 '12 at 15:31
@JamesKanze: It is still confusing.... 1) if the `std::vector` is not meant to be derived from, then why the Standard doesn't declare them as `final` in C++11?.... 2) If a class is not declared `final`, and I derived from it, then I do not see any reason why it should not work properly: does the base know that someone has derived from it? and based on that knowledge the base *decides* to behave improperly, is that so? I find the argument "the class is not designed to be base" arbitrary and insufficient, because it doesn't pinpoint the problem if someone still derives from it. — Nawaz, Mar 26 '12 at 15:39
@Nawaz Because it doesn't have to be `final`. It makes no sense to derive from it, so there's no point in changing it. And it's the class which attempts to derive from `std::vector`, or the user of that class, which will have problems, not `std::vector`. — James Kanze, Mar 26 '12 at 15:56
@JamesKanze: What problems? That is what I don't understand. Please explain this part. — Nawaz, Mar 26 '12 at 16:00

James Kanze · Accepted Answer · 2012-03-26T09:57:36.057

A vector of DFSCode can contain many DFSCode. Since a DFSCode can contain many DFS, a vector of DFSCode can contain many, many DFS.

With regards to your code: some suggestions:

Use `push_back` and `pop_back`, rather than `resize`. It's much more idiomatic. Your function `push` should start:
```
    push_back( DFS() );
    back().from() = from;
    ...
```

Give `DFS` a constructor which takes the arguments it needs:

    DFS::DFS( int from, int to, int fromLabel, int eLabel, int toLabel )
        : from( from )
        , to( to )
        , fromLabel( fromLabel )
        , eLabel( eLabel)
        , toLabel( toLabel )
    {
    }

Then `push` becomes simply: push_back( DFS( from, to, fromLabel, eLabel, toLabel ) );

Don't inherit from `std::vector`. Make it a data member.

With regards to your question about the ordering function, std::vector<DFSCode> is basically a two dimensional structure. This can be handled elegantly by means of lexicographical_compare:

struct CompareDFSCode
{
    bool operator()( DFS const& lhs, DFS const& rhs ) const
    {
        if ( lhs.from != rhs.from )
            return lhs.from < rhs.from;
        else if ( lhs.to != rhs.to )
            return lhs.to < rhs.to;
        else if ( lhs.fromLabel != rhs.fromLabel )
            return lhs.fromLabel < rhs.fromLabel;
        else if ( lhs.eLabel != rhs.eLabel )
            return lhs.eLabel < rhs.eLabel;
        else
            return lhs.toLabel < rhs.toLabel;
    }

    bool operator()( DFSCode const& lhs, DFSCode const& rhs ) const
    {
        return std::lexicographical_compare(
            lhs,begin(), lhs.end(),
            rhs.begin(), rhs.end(),
            *this );
    }

    bool operator()(
            std::vector<DFSCode> const& lhs,
            std::vector<DFSCode> const& rhs ) const
    {
        return std::lexicographical_compare(
            lhs.begin(), lhs.end(),
            rhs.begin(), rhs.end(),
            *this );
    }
};

EDIT:

One important point I forgot to mention. With the above comparison operator, the order of items in the vectors is significant. If this is not acceptable, then you'll probably have to end up sorting the elements first (in a temporary).

What is 'lexicographical_sort'? It seems an algorithm rather than i function in C++. — LoveTW, Mar 26 '12 at 09:10
@Mr.mr. Aren't all STL algorithms implemented as (templated) functions? — Antonio Pérez, Mar 26 '12 at 09:16
@Mr.mr. It's a function template in the standard library. It's designed for this sort of thing; it returns true if the first sequence is "less than" the second, for "less than" of a particular element defined by it's fifth argument (or `std::less`, if there is no fifth argument). — James Kanze, Mar 26 '12 at 09:51
@juanchopanza Yes. I was thinking about sorting at the time, and slipped up with the name (even though I had the relevant page in from of me---I can never spell lexicographical without looking). I'll correct my posting. Thanks. — James Kanze, Mar 26 '12 at 09:59

score 0 · Answer 2 · answered Mar 26 '12 at 08:56

The first question is: Does above code satisfied my expectation that "one vector contain many PDB"?

Go for a multimap instead of a map. map can have only one value to a key.Its like one to one relation. multimap can have many values to a single key.

You donot need to inherit DFScode as antonio suggested.

How to use self-defined structure in C++ Map

2 Answers2