Jump to content
Search In
  • More options...
Find results that contain...
Find results in...

Find sequence of elements in vector (C++)

Hey. So I have 2 vectors of different sizes, and in the bigger one I need to be able to find a sequence of elements that matches the smaller one.

 

Here's an example of the vectors:

 

std::vector<int> bigVec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
std::vector<int> smallVec{4, 5, 6};

How would I find smallVec within bigVec?
bigVec contains the sequence 4, 5, 6.
smallVec also has that sequence.
So how would I find that sequence in bigVec?

 

Help is appreciated, thanks!

CPU: Intel Core i7 8700  

GPU: Gigabyte GeForce GTX 1070

MOBO: ASUS Z370-F STRIX  

RAM: 16GB Corsair Vengeance DDR4 2133MHz

Link to post
Share on other sites

Loop through bigVec, until you find the first value of smallVec. Once you find that first number, continue looping through bigVec to find the second number of smallVec. If the subsequent number matches the second number of smallVec, continue doing this again. If not, forget this number and continue doing the same thing.

 

Kinda like this:

for(i = 0; i < bigVec.Count; i++)
{
	for(y = 0; y < smallVec.Count; y++)
    {
		if(bigVec[i] == smallVec[y])
        {
        	// it matches
            if(y == (smallVec.Count - 1))
            {
            	// We got all matches. Not sure what you want to do, but you can simply do i = smallVec.Count and find the location of the match
                // Maybe break, or set somethinbg to true/false?
            }
        }
        else
        {
        	// no match
            break;
        }
    }
    
    if(i == (bigVec.Count -1))
    {
    	// If the bool or whatever is false, or if you have not breaked.. Depends on what you want to do..
        // Number sequence not found
    }
}

 

This is in C#, or C#-like code. I trust you can take this concept and apply it to C++ and make it work for you.

"We're all in this together, might as well be friends" Tom, Toonami.

 mini_cardboard: a 4% keyboard build log and how keyboards workhttps://linustechtips.com/topic/1328547-mini_cardboard-a-4-keyboard-build-log-and-how-keyboards-work/

 

Link to post
Share on other sites

If you need the sequence to be in that exact order then you need to first find the fist element, then check if the element after that is correct and do the same for the third element. If they are, congratulations, you found it - if they aren't, look for the next occurrence of the first element and repeat.

 

Here's a function that returns the index of bigVector where smallVector first appears in the correct order, or -1 if smallVec doesn't appear at all.

int find(vector<int>& bigVec, vector<int>& smallVec){
  for(int i = 0; i < bigVec.Count - smallVec.Count; i++){	//only check for smallVec where there is enough space for it
    int n;
    for(n = 0; n < smallVec.Count; n++){
      if(bigVec[i + n] != smallVec[n]){		//if one of the elements is incorrect exit the loop and set n to -1
        n = -1;
        break;
      }
    }
    if(n != -1) return i;	//if n isn't -1 it means smallVec was found at index i
  }
  return -1;	//if the function gets here it means smallVec was not found
}

 

Don't ask to ask, just ask... please 🤨

sudo chmod -R 000 /*

What is scaling and how does it work? Asus PB287Q unboxing! Console alternatives :D Watch Netflix with Kodi on Arch Linux Sharing folders over the internet using SSH Beginner's Guide To LTT (by iamdarkyoshi)

Sauron'stm Product Scores:

Spoiler

Just a list of my personal scores for some products, in no particular order, with brief comments. I just got the idea to do them so they aren't many for now :)

Don't take these as complete reviews or final truths - they are just my personal impressions on products I may or may not have used, summed up in a couple of sentences and a rough score. All scores take into account the unit's price and time of release, heavily so, therefore don't expect absolute performance to be reflected here.

 

-Lenovo Thinkpad X220 - [8/10]

Spoiler

A durable and reliable machine that is relatively lightweight, has all the hardware it needs to never feel sluggish and has a great IPS matte screen. Downsides are mostly due to its age, most notably the screen resolution of 1366x768 and usb 2.0 ports.

 

-Apple Macbook (2015) - [Garbage -/10]

Spoiler

From my perspective, this product has no redeeming factors given its price and the competition. It is underpowered, overpriced, impractical due to its single port and is made redundant even by Apple's own iPad pro line.

 

-OnePlus X - [7/10]

Spoiler

A good phone for the price. It does everything I (and most people) need without being sluggish and has no particularly bad flaws. The lack of recent software updates and relatively barebones feature kit (most notably the lack of 5GHz wifi, biometric sensors and backlight for the capacitive buttons) prevent it from being exceptional.

 

-Microsoft Surface Book 2 - [Garbage - -/10]

Spoiler

Overpriced and rushed, offers nothing notable compared to the competition, doesn't come with an adequate charger despite the premium price. Worse than the Macbook for not even offering the small plus sides of having macOS. Buy a Razer Blade if you want high performance in a (relatively) light package.

 

-Intel Core i7 2600/k - [9/10]

Spoiler

Quite possibly Intel's best product launch ever. It had all the bleeding edge features of the time, it came with a very significant performance improvement over its predecessor and it had a soldered heatspreader, allowing for efficient cooling and great overclocking. Even the "locked" version could be overclocked through the multiplier within (quite reasonable) limits.

 

-Apple iPad Pro - [5/10]

Spoiler

A pretty good product, sunk by its price (plus the extra cost of the physical keyboard and the pencil). Buy it if you don't mind the Apple tax and are looking for a very light office machine with an excellent digitizer. Particularly good for rich students. Bad for cheap tinkerers like myself.

 

 

Link to post
Share on other sites
25 minutes ago, minibois said:

Loop through bigVec, until you find the first value of smallVec. Once you find that first number, continue looping through bigVec to find the second number of smallVec. If the subsequent number matches the second number of smallVec, continue doing this again. If not, forget this number and continue doing the same thing.

 

Kinda like this:


for(i = 0; i < bigVec.Count; i++)
{
	for(y = 0; y < smallVec.Count; y++)
    {
		if(bigVec[i] == smallVec[y])
        {
        	// it matches
            if(y == (smallVec.Count - 1))
            {
            	// We got all matches. Not sure what you want to do, but you can simply do i = smallVec.Count and find the location of the match
                // Maybe break, or set somethinbg to true/false?
            }
        }
        else
        {
        	// no match
            break;
        }
    }
    
    if(i == (bigVec.Count -1))
    {
    	// If the bool or whatever is false, or if you have not breaked.. Depends on what you want to do..
        // Number sequence not found
    }
}

 

This is in C#, or C#-like code. I trust you can take this concept and apply it to C++ and make it work for you.

It can find the individual numbers but it fails to find the sequence as a whole thing.

CPU: Intel Core i7 8700  

GPU: Gigabyte GeForce GTX 1070

MOBO: ASUS Z370-F STRIX  

RAM: 16GB Corsair Vengeance DDR4 2133MHz

Link to post
Share on other sites
1 minute ago, EVILCAT6 said:

It can find the individual numbers but it fails to find the sequence as a whole thing.

that's what the second for loop is for. But now I realize you need another sort of function to keep looping through the bigVec once you are started on a matching number

"We're all in this together, might as well be friends" Tom, Toonami.

 mini_cardboard: a 4% keyboard build log and how keyboards workhttps://linustechtips.com/topic/1328547-mini_cardboard-a-4-keyboard-build-log-and-how-keyboards-work/

 

Link to post
Share on other sites
25 minutes ago, minibois said:

- snip -

29 minutes ago, Sauron said:

- snip -

A friend provided a solution that worked perfectly. Here's the code:

for (int i = 0; i <= v1.Length - v2.Length; i++) {
    bool match = true;
    for (int j = 0; j < v2.Length; j++) {
        if (v1[i + j] != v2[j]) {
            match = false;
            break;
        }
    }
    if (match) {
        return true;
    }
}
return false;

 

CPU: Intel Core i7 8700  

GPU: Gigabyte GeForce GTX 1070

MOBO: ASUS Z370-F STRIX  

RAM: 16GB Corsair Vengeance DDR4 2133MHz

Link to post
Share on other sites
3 minutes ago, EVILCAT6 said:

A friend provided a solution that worked perfectly. Here's the code:


for (int i = 0; i <= v1.Length - v2.Length; i++) {
    bool match = true;
    for (int j = 0; j < v2.Length; j++) {
        if (v1[i + j] != v2[j]) {
            match = false;
            break;
        }
    }
    if (match) {
        return true;
    }
}
return false;

 

Seems exactly like mine, it just returns a boolean rather than the position where the sequence is found.

Don't ask to ask, just ask... please 🤨

sudo chmod -R 000 /*

What is scaling and how does it work? Asus PB287Q unboxing! Console alternatives :D Watch Netflix with Kodi on Arch Linux Sharing folders over the internet using SSH Beginner's Guide To LTT (by iamdarkyoshi)

Sauron'stm Product Scores:

Spoiler

Just a list of my personal scores for some products, in no particular order, with brief comments. I just got the idea to do them so they aren't many for now :)

Don't take these as complete reviews or final truths - they are just my personal impressions on products I may or may not have used, summed up in a couple of sentences and a rough score. All scores take into account the unit's price and time of release, heavily so, therefore don't expect absolute performance to be reflected here.

 

-Lenovo Thinkpad X220 - [8/10]

Spoiler

A durable and reliable machine that is relatively lightweight, has all the hardware it needs to never feel sluggish and has a great IPS matte screen. Downsides are mostly due to its age, most notably the screen resolution of 1366x768 and usb 2.0 ports.

 

-Apple Macbook (2015) - [Garbage -/10]

Spoiler

From my perspective, this product has no redeeming factors given its price and the competition. It is underpowered, overpriced, impractical due to its single port and is made redundant even by Apple's own iPad pro line.

 

-OnePlus X - [7/10]

Spoiler

A good phone for the price. It does everything I (and most people) need without being sluggish and has no particularly bad flaws. The lack of recent software updates and relatively barebones feature kit (most notably the lack of 5GHz wifi, biometric sensors and backlight for the capacitive buttons) prevent it from being exceptional.

 

-Microsoft Surface Book 2 - [Garbage - -/10]

Spoiler

Overpriced and rushed, offers nothing notable compared to the competition, doesn't come with an adequate charger despite the premium price. Worse than the Macbook for not even offering the small plus sides of having macOS. Buy a Razer Blade if you want high performance in a (relatively) light package.

 

-Intel Core i7 2600/k - [9/10]

Spoiler

Quite possibly Intel's best product launch ever. It had all the bleeding edge features of the time, it came with a very significant performance improvement over its predecessor and it had a soldered heatspreader, allowing for efficient cooling and great overclocking. Even the "locked" version could be overclocked through the multiplier within (quite reasonable) limits.

 

-Apple iPad Pro - [5/10]

Spoiler

A pretty good product, sunk by its price (plus the extra cost of the physical keyboard and the pencil). Buy it if you don't mind the Apple tax and are looking for a very light office machine with an excellent digitizer. Particularly good for rich students. Bad for cheap tinkerers like myself.

 

 

Link to post
Share on other sites
On 2/6/2020 at 4:25 PM, EVILCAT6 said:

Hey. So I have 2 vectors of different sizes, and in the bigger one I need to be able to find a sequence of elements that matches the smaller one.

 

Here's an example of the vectors:

 


std::vector<int> bigVec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
std::vector<int> smallVec{4, 5, 6};

How would I find smallVec within bigVec?
bigVec contains the sequence 4, 5, 6.
smallVec also has that sequence.
So how would I find that sequence in bigVec?

 

Help is appreciated, thanks!

Try using the STL as much as possible, it's there for that, results in short and cleaner code and tends to perform better then hand-rolled alternatives.

std::vector<int> bigVec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
std::vector<int> smallVec{4, 5, 6};
	
auto it = std::search(bigVec.begin(), bigVec.end(), smallVec.begin(), smallVec.end());
/* it = iterator to the first occurence of the sequence in bigVec. end if not found.
   if you need the location rather then a iterator use std::distance */
if (it == bigVec.end())
{
	std::cout << "not found\n";
}
else
{
	std::cout << "Sequence starts at element number: " << std::distance(bigVec.begin(), it) << '\n';
}

 

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×