Member Avatar for lotrsimp12345

Is my understanding of a vector list correct. vector<list<int>>.

The vector holds a list of data type int?

class my_ht_chain
{
public:
	//constructor which creates a table of a certain size 
	my_ht_chain(int size);

	//destructor
	~my_ht_chain();

	//insert a value based on key
	void insert(int key);

	//search for a value based on key
	bool search(int key);

	//delete an item in the list
	void remove(int key);

	//prints out all items stored in hash table
	void show_ht_structure() const;

private:
	//number of vectors to store in array
	int tablesize;

	//table to store key 
	vector<list<int>>* dataTable;

	//used to map a key to a position
	int hashfunction(int key);
};
  • 2 Contributors
  • 8 Replies
  • 108 Views
  • 9 Hours Discussion Span
  • Latest Post Latest Post by lotrsimp12345

Dani AI

Generated

Brief summary and practical tips (building on and )

Think of the structure as "a sequence of buckets, each bucket is an STL list that stores ints." That mental model makes separate chaining simple: the outer container (vector) selects a bucket index; the inner container (list) holds the chain of keys that hash to that index.

Prefer keeping the vector as a member (not a pointer) and size it up front so .at() or operator[] are valid. Compute the bucket index once — do not loop over every index checking for a match. Example patterns:

class my_ht_chain {
  size_t tablesize;
  std::vector<std::list<int>> buckets;
public:
  my_ht_chain(size_t n) : tablesize(n), buckets(n) {}
};
void my_ht_chain::insert(int key) {
  size_t idx = hashfunction(key) % tablesize;   // single computation
  auto &bucket = buckets[idx];
  if (std::find(bucket.begin(), bucket.end(), key) == bucket.end())
    bucket.push_front(key);   // or push_back, depending on desired order
}

Common pitfalls and extra notes

  • The "out_of_range" error usually means the vector had size 0 (was never initialized or resized). Initialize with buckets(n) or call buckets.resize(n) in the constructor — this is what eventually discovered.
  • .at() throws std::out_of_range on bad index; operator[] is unchecked (undefined behavior if out of range).
  • Use size_t for sizes/indices. Consider checking for duplicates before inserting, and use list::remove or erase after finding an iterator for removals.
  • For non-int keys, use std::hash<T> and template the class; rehash (grow and re-distribute) when the load factor gets large.

Reference reading: vector - cppreference and list - cppreference

Recommended Answers

All 8 Replies

Member Avatar for mrnutty

>>"The vector holds a list of data type int? "

the word list has ambiguity.

A better term(IMO) would be : The vector contains a container in which the contained container is of type int and the contained container is a stl's list container.

Member Avatar for lotrsimp12345

so for instance say i did dataTable->at(key) would i be referring to the list or vector? or both?

Member Avatar for mrnutty

so for instance say i did dataTable->at(key) would i be referring to the list or vector? or both?

dataTable is a vector.

dataTable is a list

dataTable.front() is the int.

And also I don't think mixing up vectors and list would be a good
idea, unless it really really makes sense to do so.

Member Avatar for lotrsimp12345

thanks! it makes a lot more sense its just like when you declare an array. we kind of have to for this hash table assignment. Have to create using seperate chaining method. Will ask for help again if i get stuck.

Edited by lotrsimp12345 because: n/a
Member Avatar for lotrsimp12345

kind of need help with syntax again.
in my insert method, i am supposed to expand an vector with a list. Not sure what to do within if statement.
Rather how I say at this index in my vector expand sideways a list which stores data values.

void my_ht_chain::insert(int key)
{
	//go through loop to check if hashing function matches vector index
	for(int i=0; i<tablesize; i++)
	{
		//match
		if(hashfunction(key)==i)
		{
			
		}
	}
}
Edited by lotrsimp12345 because: n/a
Member Avatar for lotrsimp12345

nvm i finally got it work. Thanks thought.

Member Avatar for lotrsimp12345

my insert function won't work. :( I got it to work before.

void my_ht_chain::insert(int key)
{
	//go through loop to check if hashing function matches vector index
	for(int i=0; i<tablesize; i++)
	{
		//match
		if(hashfunction(key)==i)
		{
			dataTable->at(i).push_front(key);
		}
	}
}

out of range invalid vector subscript.

Edited by lotrsimp12345 because: n/a
Member Avatar for lotrsimp12345

nvm i found my mistake it wasn't even in here. It was when i constructor my vector apparently the vector(# of values you wish to assign, what you wish to assign) not other way round.

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.