Solved

re-index vector

Posted on 2013-11-18
11
463 Views
Last Modified: 2013-11-18
I am try to reading a set of records from a file to a vector of data  structures.

for example

DataSturcture {

string Name;
int ID;
string AlternateName;

}

I like create a index of each member so I don't have to search everytime I try to access them.  How would I do that?  Is any class in std library or boost can do that?
0
Comment
Question by:tommym121
  • 5
  • 4
  • 2
11 Comments
 
LVL 86

Assisted Solution

by:jkr
jkr earned 224 total points
ID: 39656558
By what field would you like to index them? A std::map is what comes to my mind when thinking about this, i.e. if you want the ID to be the index, you could

#include <map>
using namespace std;

//...
DataSturcture {

string Name;
int ID;
string AlternateName;
};

map<int,DataStructure&> mapIDtoDataStructure;

while(!infile.eof()) {

  DataStructure ds;

  ReadDataStructure(ds);

  // enter to map based on ID

  mapIDtoDataStructure.insert(map::int,DataStructure&>::value_type(ds.ID,da));
}

// ...

// sample lookup for ID = 42
int id = 42;
DataStructure tmp = mapIDtoDataStructure[id];

Open in new window


See also http://en.cppreference.com/w/cpp/container/map
0
 
LVL 86

Assisted Solution

by:jkr
jkr earned 224 total points
ID: 39656572
Ooops, correction, that should be

#include <map>
using namespace std;

//...
DataSturcture {

string Name;
int ID;
string AlternateName;
};

map<int,DataStructure> mapIDtoDataStructure;

while(!infile.eof()) {

  DataStructure ds;

  ReadDataStructure(ds);

  // enter to map based on ID

  mapIDtoDataStructure.insert(map::int,DataStructure>::value_type(ds.ID,ds));
}

// ...

// sample lookup for ID = 42
int id = 42;
DataStructure tmp = mapIDtoDataStructure[id];
                                            

Open in new window


In this case you would not even need a vector and all the structs would be stored in a map instead of that. However, if you still want to keep the vector, my first comment (with a map of references) would still work, yet the storing would be a bit different:

#include <map>
using namespace std;

//...
DataSturcture {

string Name;
int ID;
string AlternateName;
};

map<int,DataStructure&> mapIDtoDataStructure;
vector<DataStructure> vStructs;

// fill vector...

for(vector<DataStructure>::iterator i = vStructs.begin(); i != vStructs.end(); ++i) {
  // enter to map based on ID

  mapIDtoDataStructure.insert(map::int,DataStructure&>::value_type(i->ID,*i));
}

// ...

// sample lookup for ID = 42
int id = 42;
DataStructure tmp = mapIDtoDataStructure[id];
                                            

Open in new window

0
 

Author Comment

by:tommym121
ID: 39656601
jkr,

If I understand what you mean.  I should put the data sturcture into map.  How can I optimize the retrieve of the record,  Sometime I need to use the Name, other time to use the ID or the AlternateName.

I am trying to borrow the same concept in database, i.e. to use each of the field as a key to index so I can simply

Now with you example I can do mapIDTodDataStructure, But I would also like to perform
& mapNameTodDataStructure (Name)
& mapAlternateNameToDataStucture (AlternateName)

Do I have to read the file 3 times or a better way to handle this?

Thanks
0
 
LVL 33

Assisted Solution

by:sarabande
sarabande earned 276 total points
ID: 39656621
you can use a std::vector where you store all records. then have three maps for each search field which would point into the vector.

note, a std::map has a unique key. if you have duplicate values you need tu use a multimap or better a map to vector.

Sara
0
 
LVL 86

Assisted Solution

by:jkr
jkr earned 224 total points
ID: 39656635
No, you could just use 3 maos for that:

#include <map>
using namespace std;

//...
DataSturcture {

string Name;
int ID;
string AlternateName;
};

map<int,DataStructure&> mapIDtoDataStructure;
map<string,DataStructure&> mapNameToDataStructure ;
map<string,DataStructure&> mapAlternateNameToDataStructure ;

vector<DataStructure> vStructs;

// fill vector...

for(vector<DataStructure>::iterator i = vStructs.begin(); i != vStructs.end(); ++i) {
  // enter to map based on ID

  mapIDtoDataStructure.insert(map::int,DataStructure&>::value_type(i->ID,*i));
  mapNametoDataStructure.insert(map::string,DataStructure&>::value_type(i->Name,*i));
  mapAlternateNametoDataStructure.insert(map::string,DataStructure&>::value_type(i->AlternateName,*i));
}
                           

Open in new window


This way, you have all maps covering all lookup aspects, and the storage will only happen in the vector - the maps only hold references.
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 33

Assisted Solution

by:sarabande
sarabande earned 276 total points
ID: 39656675
note, the struct may not use std::string if you use it with a binary write or binary read. a std::string has a pointer internally which is not valid anymore when read from file. you may use fixed char buffers instead.


struct DataStructure 
{
      char name[30];
      int    id;
      char alternate[30];
};

std::vector<DataStructure> data;
std::map<std::string, std::vector<int> > nameMap;
std::map<std::string, std::vector<int> > alternateMap;
std::map<int, std::vector<int> > idMap;  // I assume the id is unique

DataStructure ds = { 0 };
int count = 0;
std::ifstream infile(szpath, std::ios::binary | std::ios::in); 
while (infile.read((char*)&ds, sizeof(ds)))
{
      data.push_back(ds);
      idMap[ds.id] = count;
      nameMap[ds.name].push_back(count);
      alternateMap[ds.alternate].push_back(count);
      count++;
}
infile.close();

Open in new window


Sara
0
 
LVL 33

Assisted Solution

by:sarabande
sarabande earned 276 total points
ID: 39656704
you also can use one map for the nameMap and alternateMap using the above technique.

to search for a 'name' you would do:

std::map<std::string, std::vector<int> >::iterator f;

if ((f = nameMap.find("John")) != nameMap.end())
{
    std::vector<int> & refs = f->second;
    for (int i =0; i < (int)refs.size(); ++i)
    {
          std::cout << "ID: " << data[refs[i]].id" << std::endl;
    }
}

Open in new window


Sara
0
 
LVL 33

Assisted Solution

by:sarabande
sarabande earned 276 total points
ID: 39656716
map<int,DataStructure&> mapIDtoDataStructure;

it is not possible to store a reference to class object in a map. you either have to use a pointer or an index to the all-data-vector (as in my sample code).

Sara
0
 
LVL 33

Assisted Solution

by:sarabande
sarabande earned 276 total points
ID: 39656769
should be

// the map maps an ID to an index in the vector of all records
std::map<int, int > idMap;  // I assume the id is unique

Open in new window


Sara
0
 
LVL 86

Accepted Solution

by:
jkr earned 224 total points
ID: 39656770
That is correct - yoet an iterator to the vector works (and this corrects a whole bunch of typos as well):

#include <map>
#include <vector>
#include <string>
using namespace std;

//...
struct DataStructure {

string Name;
int ID;
string AlternateName;
};

vector<DataStructure> vStructs;


map<int,vector<DataStructure>::iterator> mapIDToDataStructure;
map<string,vector<DataStructure>::iterator> mapNameToDataStructure ;
map<string,vector<DataStructure>::iterator> mapAlternateNameToDataStructure ;


void main () {

// fill vector...

for(vector<DataStructure>::iterator i = vStructs.begin(); i != vStructs.end(); ++i) {
  // enter to map based on ID

  mapIDToDataStructure.insert(map<int,vector<DataStructure>::iterator>::value_type(i->ID,i));
  mapNameToDataStructure.insert(map<string,vector<DataStructure>::iterator>::value_type(i->Name,i));
  mapAlternateNameToDataStructure.insert(map<string,vector<DataStructure>::iterator>::value_type(i->AlternateName,i));
}

}
                           
                                            

Open in new window

0
 

Author Closing Comment

by:tommym121
ID: 39657046
Thanks. I learn a lot. Thank you again.
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

863 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

28 Experts available now in Live!

Get 1:1 Help Now