Vector of a struct containing another vector

Okay I am implementing an index of words from an input text file. I have a class that contains a vector declared like this:

Code:

---

vector<indexWord> data;

---

and a struct declared like this:

Code:

---

struct indexWord {
        std::string value;
        std::vector<int> locations;
};

---

So, in essence, I am storing the words and page numbers in the indexWord struct and then storing that info in the data vector. I have an output function that should output these values. How do I go about telling the function to output the "value" and vector of locations using just the data vector?

What exactly is your question? Are you asking how to loop through every element of a vector? Do you want to have cout << indexWord_object do the right thing? What?

Yeah I need to loop through the data vector to output the "value" and vector of locations using the data vector. I don't know how to do this.

You could add a print() method to indexWord, then iterate through data calling the print() method of each element.

That's why vector has iterators. You start at begin(), and you go until you get to end(), and ... well whatever you need to do, you do.

Code:

---

for (vector<indexWord>::iterator current=data.begin(); current!=data.end(); ++current) {
    // do whatever you need to do to the current object, which is *current
}

---

Code:

---

invalid conversion from `const indexWord* const' to `indexWord*'|
||=== Build finished: 1 errors, 0 warnings ===|

---

What's the code on the line referenced by that error message?

What tabstop just gave me:

Code:

---

for (vector<indexWord>::iterator current=data.begin(); current!=data.end(); ++current)

---

Use iterators on both vectors. The first iterator will iterate through indexWord objects and the second iterator will iterate through your int vector in the objects. But this structure is also suited to a map. Key off the map on the string value and the map value will be the vector of integers.

Code:

---

typedef std::vector<int> IntVector;
typedef IntVector::iterator IntVectorIter;
typedef IntVector::const_iterator IntVectorConstIter;

typedef std::map<std::string,IntVector> MapObject;
typedef MapObject::iterator MapObjectIter;
typedef MapObject::const_iterator MapObjectConstIter;


MapObject  AllObjects;

//Iterate through map
MapObjectIter map_iter(AllObjects.begin());
MapObjectIter map_end(AllObjects.end());

while (map_iter != map_end)
{
    IntVectorIter vector_iter(map_iter.second.begin());
    IntVectorIter vector_end(map_iter.second.end());

    while (vector_iter != vector_end)
    {
        //Do something with vector_iter
    }
}

---

Then you didn't do vector<indexWord> data. What is data?

There's nothing wrong with that line of code. What's in the for loop?

data is the vector...

Quote:

---

Originally Posted by R.Stiltskin

There's nothing wrong with that line of code. What's in the for loop?

---

nothing right now. just trying to see if that line of code works and it spit out that error.

Must be a problem someplace else. This compiles fine for me:

Code:

---

#include <iostream>
#include <vector>


struct indexWord {
        std::string value;
        std::vector<int> locations;

        indexWord(std::string s) : value(s) {}
};

int main() {
  std::vector<indexWord> data;
  data.push_back(indexWord(std::string("once")));
  data.push_back(indexWord(std::string("upon")));
  for(std::vector<indexWord>::iterator current=data.begin(); current!=data.end(); ++current) {
    std::cout << current->value << " ";
  }
  std::cout << "\n";
}

---

Are you sure it isn't a list? (I think list iterators are const pointers to const, but I don't remember for sure.) Anyway, what you posted doesn't match. So post everything.

Make it std::vector<indexWord>::const_iterator if you only want to read anyway.

Alright I got it working. Now how to a output these values in the array according to their first letter?

Why is this not getting every single line of the book, the page number, and storing it in the vector?? This is the driver file that runs through the file, gets the line, strips the line into words, then passes those words to the addWord function:

Code:

---

    Index create;

    int thePageNum = 1;
    while(book.fileOfBook)
    {
        for(int lineNumber = 0; lineNumber < MAX_LINES_PER_PAGE; lineNumber++)
        {
            string theLine = book.readLine();
            char * pch;
            pch = &theLine[0];
            pch = strtok (pch," :#;[]""\"()!*`1234567890'?,.-");

            while (pch != NULL)
            {
                for(int i = 0; pch[i] != '\0'; i++)
                    pch[i] = tolower(pch[i]);
                string words(pch);
                create.addWord(words, PageNo);
                pch = strtok (NULL, " :#;[]""\"()!*`1234567890'?,.-");
            }
        }
        create.output(indexOut, book.theTitle);
        thePageNum++;
    }

---

This is the addLine function:

Code:

---

void Index::addWord(string word, int pageNumber)
{
    indexWord index;
    index.value = word;
    index.locations.push_back(pageNumber);
    data.push_back(index);
}

---

I try to cout the variable "value" from the struct indexWord and it only goes to line MAX_LINES_PER_PAGE. I need it to run through the whole book. Is there something I am doing wrong?

Code:

---

" :#;[]""\"()!*`1234567890'?,.-"

---

Surely, if this is indeed the same value in both strtok calls, then you probably should have a single declaration of a

Code:

---

const char *separators = " :#;[]""\"()!*`1234567890'?,.-";

---

so that it's easy to see that it IS the same thing.

--
Mats

Alright I finally got it working. Now how to I look through the vector and output it according to first word?

(1) Your driver file is incrementing a variable called "thePageNum" but when it calls the addWord method it sends pageNo as the 2nd parameter.

(2) It seems that every time strtok returns a word, addWord pushes a new indexWord onto the index vector. Instead, if a word already exists in the vector, don't you want to find it and just add another page number to its vector?

(3) But before you add another page number, don't you also want to check to see if that page number is already there?

(4) To print the index in alphabetical order you need to sort it alphabetically. But you might want to consider using a sorted list or a map instead of vector; otherwise to accomplish (2) and (3) you will have to search linearly through the indexWord and pageNo vectors every time.

(5) Do you really want to index words like "the", "and", ...?

Quote:

---

Originally Posted by R.Stiltskin

(1) Your driver file is incrementing a variable called "thePageNum" but when it calls the addWord method it sends pageNo as the 2nd parameter.

(2) It seems that every time strtok returns a word, addWord pushes a new indexWord onto the index vector. Instead, if a word already exists in the vector, don't you want to find it and just add another page number to its vector?

(3) But before you add another page number, don't you also want to check to see if that page number is already there?

(4) To print the index in alphabetical order you need to sort it alphabetically. But you might want to consider using a sorted list or a map instead of vector; otherwise to accomplish (2) and (3) you will have to search linearly through the indexWord and pageNo vectors every time.

(5) Do you really want to index words like "the", "and", ...?

---

I have a condition in my addWord function that doesn't add the words if they are 3 letters or less. Plus this sounds really complicated sorting the vector even though I need to. How do I do this? I haven't learned maps.

I don't know how to search through the vector of a vector and a string. I also don't know how to output the vector containing the page numbers that's in the vector.

I assume you know how to sort the locations vector, since its elements are just ints. Use any sorting algorithm you know. You can access the elements of the vector the same as an ordinary array of ints. Alternatively, use an STL list instead of vector & it comes with a sort method built-in.

To sort the indexWord vector, again use any sorting algorithm you like. In this case, when you look at two elements to see which comes first, compare the value members only, but when you swap, swap the entire indexWord elements. In order to use list to do this automatically for you, you would first have to give it a comparison function showing it how to order two elements. For example:
http://www.codeguru.com/forum/showthread.php?t=366063

Otherwise, try to figure out how to use a map, which will keep things sorted and let you find elements easily. Maybe this will help:
http://www.cppreference.com/wiki/

Quote:

---

Originally Posted by Todd88

I don't know how to search through the vector of a vector and a string. I also don't know how to output the vector containing the page numbers that's in the vector.

---

I don't know why you think outputting the vector of page numbers is different than outputting the big(ger) vector -- loop through all the elements and print.

And sort() is built-in -- you just need to define a function that determines when "this" is less than "that".

The pages vector is inside the struct indexWord and the indexWord vector is inside the class Index though. I am really sorry but I just don't get it! I am sure this is simple stuff but I don't get it!!

Quote:

---

Originally Posted by Todd88

The pages vector is inside the struct indexWord and the indexWord vector is inside the class Index though.

---

Why do you think that makes a difference? Once you have a hold of the vector, it doesn't matter where it came from, just loop through it.

Quote:

---

Originally Posted by tabstop

And sort() is built-in -- you just need to define a function that determines when "this" is less than "that".

---

I didn't know that sort() is built-in to vector. It isn't mentioned here:
http://www.cppreference.com/wiki/stl/vector/start

If that reference is incomplete, do you have a link to a better one?

sort() is a free function, not a member of vector.

Quote:

---

Originally Posted by R.Stiltskin

I didn't know that sort() is built-in to vector.

---

It is not. However, like std::vector, it is part of the standard library, available by including <algorithm>.

Quote:

---

Originally Posted by R.Stiltskin

I didn't know that sort() is built-in to vector. It isn't mentioned here:
http://www.cppreference.com/wiki/stl/vector/start

If that reference is incomplete, do you have a link to a better one?

---

sort() is built-in to C++, not to vector. (It requires a random access iterator, so you need either arrays, or vector, or some custom-built random access object, to use it.)

Quote:

---

Originally Posted by tabstop

sort() is built-in to C++

---

Not really, since it is part of the standard library, not the core language, but admittedly that is being a little pedantic.

Quote:

---

Originally Posted by laserlight

It is not. However, like std::vector, it is part of the standard library, available by including <algorithm>.

---

Yeah, thanks for pointing that out. It really is time for me to start using those.

Alright I just need an addInOrder and binarySearch algorithm for the index vector. That's it and I'm done!!! But yet again...I'm lost.

That would be lower_bound() in both cases. You can use binary_search if you're only interested in existence, though.

I need to order if first before using lower_bound(). I need to order it by the string word.

Well, that's what sort() is for, isn't it?

Actually, you'd use upper_bound() for insertion, though. And if you always do this, you never need to sort(), because it's always sorted.

So this should work right?

Code:

---

void Index::addWord(string word, int pageNumber)
{
    indexWord index;
    if(word.length() > 3)
    {
        index.value = word;
        index.locations.push_back(pageNumber);
        data.push_back(index);
        vector<int>::iterator current;
        sort (index.value.begin(), index.value.end());
    }
}

---

Wow..this actually sorts the words characters haha. So the string adventure would be adeenrstuv...

Quote:

---

Originally Posted by Todd88

So this should work right?

---

I have not read through this thread carefully, but at a glance I suspect you want to write it like this instead:

Code:

---

void Index::addWord(string word, int pageNumber)
{
    if(word.length() > 3)
    {
        indexWord index;
        index.value = word;
        index.locations.push_back(pageNumber);
        sort(index.value.begin(), index.value.end());
        data.push_back(index);
    }
}

---

I moved the declaration of index into the body of the if statement since there is no point creating it if it will not be used. I re-ordered the statements according to how I think they should be ordered, but you'll have to check. I removed the declaration of current since it appears to be unused.

Quote:

---

Originally Posted by laserlight

I have not read through this thread carefully, but at a glance I suspect you want to write it like this instead:

Code:

---

void Index::addWord(string word, int pageNumber)
{
    if(word.length() > 3)
    {
        indexWord index;
        index.value = word;
        index.locations.push_back(pageNumber);
        sort(index.value.begin(), index.value.end());
        data.push_back(index);
    }
}

---

I moved the declaration of index into the body of the if statement since there is no point creating it if it will not be used. I re-ordered the statements according to how I think they should be ordered, but you'll have to check. I removed the declaration of current since it appears to be unused.

---

This still sorts the characters of the string value instead of sorting the "data" vector by the string value.

Quote:

---

Originally Posted by Todd88

This still sorts the characters of the string value instead of sorting the "data" vector by the string value.

---

hmm... but if you want to sort the data vector, then I would expect something like:

Code:

---

sort(data.begin(), data.end());

---

If indexWord is not already less than comparable with an overloaded operator< then you should either overload operator< for indexWord such that it sorts by the string value, or you provide a function object to serve as a predicate for sorting.

So if you don't want to rearrange the letters in the word, then don't sort index.value. If you want to sort the index, then just sort index. Of course, since index is local to the if-statement, and will cease to exist once that first curly brace is hit, that seems a little extreme.

I overloaded the operator < using:

Code:

---

bool indexWord::operator< (indexWord& string)
{
    return value < string.value;
}

---

It's still telling me that there is no match for operator <

It needs to be const correct:

Code:

---

bool indexWord::operator< (const indexWord& string) const
{
    return value < string.value;
}

---

and the binary_search algorithm should work too correct? It does work for me though.

Code:

---

binary_search (data.begin(), data.end(), word)

---

right?

Okay why can't I do this:

Code:

---

void Index::addWord(string word, int pageNumber)
{
    if(word.length() > 3)
    {
        indexWord index;
        for (vector<indexWord>::iterator current=data.begin(); current!=data.end(); ++current)
        {
            if(word != current->value)
            {
                index.value = word;
                index.locations.push_back(pageNumber);
                //sort(data.begin(), data.end());
                data.push_back(index);
            }
        }
    }
}

---

Once I take the iterator statement out it works fine but I can't compare the string portion of the vector to a string?? I am so confused?!?

Can't as in compile error? If so, what error?

No there is no error. It just doesn't add to the vector correctly.

Not correctly as in "it's not there" or as in "it's in the wrong place"?

Here's what your addWord does:

Suppose word (the one passed as argument 1 of addWord) is "Markov". And suppose you already have 100 indexWords in the vector data, but none of them has value=="Markov".

addWord looks at the first of the 100 elements of data, finds that its value member is not "Markov", so it assigns index.value="Markov", assigns index.locations[0]=pageNumber (this is a "new" indexWord so its locations vector starts out empty), and pushes this index onto the back of the vector data.

Then it looks at the next element of data and does the same thing again, and so on ...
...so it ultimately pushes 100 copies of "Markov" onto the vector, then continues, looking at each of those new copies but since for each of them the value is "Markov", it doesn't add any more copies.

On the other hand, if an indexWord with value=="Markov" is already in data, addWord simply skips over that element and goes on to the next, and never adds a second element to the locations vector of any indexWord.

God, I must be completely blind.

Quote:

---

Originally Posted by R.Stiltskin

Here's what your addWord does:

Suppose word (the one passed as argument 1 of addWord) is "Markov". And suppose you already have 100 indexWords in the vector data, but none of them has value=="Markov".

addWord looks at the first of the 100 elements of data, finds that its value member is not "Markov", so it assigns index.value="Markov", assigns index.locations[0]=pageNumber (this is a "new" indexWord so its locations vector starts out empty), and pushes this index onto the back of the vector data.

Then it looks at the next element of data and does the same thing again, and so on ...
...so it ultimately pushes 100 copies of "Markov" onto the vector, then continues, looking at each of those new copies but since for each of them the value is "Markov", it doesn't add any more copies.

On the other hand, if an indexWord with value=="Markov" is already in data, addWord simply skips over that element and goes on to the next, and never adds a second element to the locations vector of any indexWord.

---

That's exactly what is SHOULD do :D

Really? So if, the first time you read "Markov" there are already 100 other words in the index, you want to now have 200 entries in the index (100 of them with value "Markov")?

Quote:

---

Originally Posted by R.Stiltskin

Really? So if, the first time you read "Markov" there are already 100 other words in the index, you want to now have 200 entries in the index (100 of them with value "Markov")?

---

Oh wait no. That is what it does now which is bad. Sorry, didn't read it close enough. Trying to get rid of that. It prints out like 100 of the same string. I am trying to fix it by doing a binary search to see if it's in the vector and if it is, just add the page number to the vector it is associated with...if you get my point.

What a waste of time. A vector of structs with vectors is a map. But if you want to do an O(n) search through the first vector I guess that is your choice.

Quote:

---

Originally Posted by Bubba

What a waste of time. A vector of structs with vectors is a map. But if you want to do an O(n) search through the first vector I guess that is your choice.

---

I'm sure it is a waste of time but I haven't learned maps yet :(

I would say then this is a good opportunity to learn about them. Fact is if you have used one container in the STL you've almost used them all. Most follow the iterator pattern so if you've done iterators in vectors doing them in maps is nearly the same thing.

A map is a container where each item in the map has a key and an associated value. You can do a search on the key and the map will give you the value. If the key is not in the map then it will return one past the end of the map or simply map_object.end(). In a map each item has a unique key. There are also multimaps where items multiple items can have the same key. There is also a hash_map (although not yet standardized) which allows you to specifiy a hash function and 'can' be faster than map given the hash function is the correct one for the job.

Vectors are nice and they are fast but if you need to search through them they are much slower than a map. As well when you remove an item from a vector it invalidates everything past that point. So if you are relying on the indices of the vector as object ID's and you remove an object in the middle of the vector, all IDs beyond the point of removal are now incorrect. A map of your structs would give you better lookup time and also makes it easier on you to code. A vector of structs with a vector is a bit confusing as opposed to a map keyed off by the name in your struct which then gives you the vector.

You can sort the vector but when there is a container more suited to your needs than vector is I see no point. It's not that vector cannot do what you want it's that map can probably do it more efficiently. The STL containers are extremely robust and the functions that can be used on them are numerous. It is very possible to gain most of the functionality you need out of almost every container but that does not mean you have chosen the right container for the job.

So a vector of integers is:

Code:

---

std::vector<int> IntVector;

---

And a map of integers keyed off by strings is:

Code:

---

std::map<std::string,int> IntMap;

---

Maps require 'pairs' which can be done via std::pair<> or via std::map<>::value_type(). To insert into the IntMap I've shown you would do:

Code:

---

//Using std::pair
IntMap.insert(std::pair<std::string,int>("Test",100));

//Using map::value_type
IntMap.insert(std::map<std::string,int>::value_type("Test",100));

---

There is another way to insert using the array access operator, however, I highly recommend you steer clear of the array access operator when it comes to maps. IMO, it has some 'hidden' behavior that is a bug waiting to happen.

Many of us could tell you tons of ways to optimize your vector and make it faster but in the end if you are using the wrong container for the job, none of the optimizations will be as fast or suited to the task as using the right container for the job.

My general rule of thumb is when you see a bunch of vectors inside of vectors then perhaps you are using the wrong container for the job. It really depends on the situation and the task as to what container you use. But the most important lesson here when it comes to the STL is use the right container and the STL will reward you.

A map<string, set<unsigned> > is what I thought about too.

Here's how it might look like. Note that inserting a keyword and a pagenumber, while making sure that they are in sorted order and unique takes just one simple line.

Code:

---

#include <iostream>
#include <string>
#include <map>
#include <set>
#include <cctype>

int main()
{
    typedef std::map<std::string, std::set<unsigned> > Index;
    Index index;
    std::string line;
    unsigned line_num = 0;

    //enter empty line to stop
    while (std::cout << ++line_num << ": " && std::getline(std::cin, line) && !line.empty()) {
        //tokenize
        std::string::iterator word_start, word_end = line.begin();
        while (
            word_start = std::find_if(word_end, line.end(), std::ptr_fun<int, int>(std::isalnum)),
            word_end = std::find_if(word_start, line.end(), std::not1(std::ptr_fun<int, int>(std::isalnum))),
            word_start != word_end
        ) {
            //could be converted to lower-case
            if (word_end - word_start > 3)
                index[std::string(word_start, word_end)].insert(line_num);
        }
    }
    //display what we got
    for (Index::iterator word_it = index.begin(); word_it != index.end(); ++word_it) {
        std::cout << word_it->first << ':';
        for (std::set<unsigned>::iterator line_it = word_it->second.begin(); line_it != word_it->second.end(); ++line_it) {
            std::cout << ' ' << *line_it;
        }
        std::cout << '\n';
    }
}

---

However, perhaps if you are going to index once but use the index a lot, you might also just throw the line (page) numbers into a vector and finally sort them and remove duplicates.

Nice I didn't think about a map of sets. Tis why I love the STL containers. So much functionality just waiting to be used.

Quote:

---

Originally Posted by anon

A map<string, set<unsigned> > is what I thought about too.

Here's how it might look like. Note that inserting a keyword and a pagenumber, while making sure that they are in sorted order and unique takes just one simple line.

Code:

---

#include <iostream>
#include <string>
#include <map>
#include <set>

int main()
{
    typedef std::map<std::string, std::set<unsigned> > Index;
    Index index;
    std::string line;
    unsigned line_num = 0;

    //enter empty line to stop
    while (std::cout << ++line_num << ": " && std::getline(std::cin, line) && !line.empty()) {
        //tokenize
        std::string::iterator word_start, word_end = line.begin();
        while (
            word_start = std::find_if(word_end, line.end(), std::ptr_fun<int, int>(std::isalnum)),
            word_end = std::find_if(word_start, line.end(), std::not1(std::ptr_fun<int, int>(std::isalnum))),
            word_start != word_end
        ) {
            //could be converted to lower-case
            if (word_end - word_start > 3)
                index[std::string(word_start, word_end)].insert(line_num);
        }
    }
    //display what we got
    for (Index::iterator word_it = index.begin(); word_it != index.end(); ++word_it) {
        std::cout << word_it->first << ':';
        for (std::set<unsigned>::iterator line_it = word_it->second.begin(); line_it != word_it->second.end(); ++line_it) {
            std::cout << ' ' << *line_it;
        }
        std::cout << '\n';
    }
}

---

However, perhaps if you are going to index once but use the index a lot, you might also just throw the line (page) numbers into a vector and finally sort them and remove duplicates.

---

Wow that's perfect. Don't really have a clue about how it works though. :( Would be perfect for this project though.

Quote:

---

Originally Posted by Todd88

Wow that's perfect. Don't really have a clue about how it works though. :( Would be perfect for this project though.

---

Could you maybe alter it a bit so it takes in my parameters? That would be a perfect solution to my problem.

What exactly don't you understand?

Tokenization:

Code:

---

word_start = std::find_if(word_end, line.end(), std::ptr_fun<int, int>(std::isalnum))

---

Finds the first character for which isalnum returns true - start of word.

Code:

---

word_end = std::find_if(word_start, line.end(), std::not1(std::ptr_fun<int, int>(std::isalnum)))

---

Finds the first character for which isalnum returns not true - start of delimiter sequence.

Probably the third arguments to find_if are hard to grasp. These consist of function objects (more precicely functions returning function objects) found in header <functional> (which I failed to include :)) which turn the standard isalnum function into a suitable function object.

Instead you could write simple function objects like this:

Code:

---

struct is_alnum
{
    bool operator()(char c) const
    {
        return isalnum(c);
    }
};

//used
word_start = std::find_if(word_end, line.end(), is_alnum());

---

Inserting into the index

Code:

---

index[std::string(word_start, word_end)].insert(line_num);

---

This does many things:
1) construct a string from the found iterator pair
2) use this string as an index into the map. map's operator[] either returns the item corresponding to the key if it exists, or first creates a new entry for this key and then returns the corresponding default-constructed value (in this case an empty set) - exactly what's needed.
3) then it calls the insert method on the returned set to add the line number (again, if the value already exists in the set, nothing is added).

Code:

---

//display what we got

---

This is a pretty ordinary way to loop over containers with iterators. The only thing to keep in mind that map holds a std::pair, which has two members: first (the key - in this case of string type) and second (the mapped type - in this case a set of unsigneds).

Thinking about it, perhaps using the set for line numbers is a bit of an overkill: the line numbers will be added in sorted order anyway, so we don't need one part of the functionality of the set, and because of that it wouldn't be hard to ensure uniqueness of mapped numbers either if we had a used a somewhat more memory-efficient vector - just look at the last value in the vector (if any) and see if the value to be added is different.