Member Avatar for guest7

Hi,

I have a 2 dimensional vector containing entries such as :

10X
01X
001

I merge two rows at a time and get a new row of elements. In other words, when i combine "10X" and "01X" i might get "001" but since "001" is already there i do not want to add it to the 2D vector.

I think "Set" will allow me to store unique elements. But i do not know how to define a Set for this.

Any help is appreciated.

Thanks

  • 2 Contributors
  • 3 Replies
  • 105 Views
  • 9 Hours Discussion Span
  • Latest Post Latest Post by programmersbook

Dani AI

Generated

A concise approach that works well for this problem is to keep a fast membership structure separate from whatever container you use to hold the final rows. That avoids inserting duplicates while letting you control ordering or layout.

A simple pattern (C++11 and later) is to use an unordered_set of keys and a vector for the output order. If each row is naturally a string like "10X", use std::unordered_set<std::string> for membership checks and only push a row into your result vector when insert reports it was new. See the reference for details on the container: std::unordered_set.

If you need to store std::vector<int> or another composite type as the key, provide a small hash functor and equality comparator. Example sketch:

struct VecHash {
    size_t operator()(std::vector<int> const& v) const {
        size_t h = v.size();
        for (int x : v) h = h * 31u + std::hash<int>{}(x);
        return h;
    }
};
struct VecEq { bool operator()(std::vector<int> const& a, std::vector<int> const& b) const { return a==b; } };

std::unordered_set<std::vector<int>,VecHash,VecEq> seen;

Practical tips: represent merge results as compact strings when possible (simpler hashing), call seen.reserve(n) if you expect many rows to avoid rehashing, and push into your output vector only when seen.insert(key).second is true. This preserves insertion order while keeping membership checks fast. These points extend the thread: already started with container-based storage, and highlighted the ordering question — the vector+unordered_set pattern addresses both.

Recommended Answers

All 3 Replies

Member Avatar for guest7

Hi,

I tried writing the code using <set> for my problem. Please let me know if my code is right or not. It is running but still i wish to make sure.

#include <set>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;

int main()
{
	typedef std::vector<int> v1;
	set<v1> cube;
	
	v1 v2;
	v2.push_back(0);
	v2.push_back(0);
	v2.push_back(2);
	cube.insert(v2);
	v2.clear();
	
	v2.push_back(0);
	v2.push_back(1);
	cube.insert(v2);
	v2.clear();
	
	v2.push_back(0);
	v2.push_back(1);
	cube.insert(v2);
	v2.clear();
	
	v2.push_back(1);
	v2.push_back(1);
	v2.push_back(0);
	cube.insert(v2);
	v2.clear();

	v2.push_back(0);
	v2.push_back(0);
	v2.push_back(2);
	cube.insert(v2);
	v2.clear();

	v2.push_back(0);
	v2.push_back(2);
	v2.push_back(0);
	cube.insert(v2);
	v2.clear();

	cout << "Size of set = " << cube.size() << endl;
	
	// Display the cube.
	set<v1>::iterator it;
	for( it = cube.begin(); it != cube.end(); it++ ) 
	{
		for( vector<int>::const_iterator it1 = it->begin(); it1!= it->end(); ++it1 )
		{
			cout << *it1 << " ";
		}
		cout << endl;
	}
	
	return 0;
}
Member Avatar for guest7

Hi,

I think that the set automatically sorts the elements. Is there a way to not do so?

Any help is appreciated.

Member Avatar for programmersbook

That is right, set is has unique elements and is sorted.

Yes is possible, you have to write a own remove function.

like:
- remove only if is already in list/vector
- while not unique

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.