Who can help me insert into BST node containing a vector.

[Last Resort]

I am trying to extend my BST so that my data is held in a vector, allowing me to use each node as a 'key' and have a set of data that is associated with that 'key' in my vector.

I can't seem to push a string into my vector that I have placed within my node. I have used vectors many times, but this particular implementation has me confounded.

I am obviously "just" trying to append some sort of "vector.push_back" into my BST insert() function so that "if I did not just add a new node, then I insert a string into my vector".

After three full days of researching and trying to "hack it out" I am hoping that someone here will be able to help me understand the basic concept I am somehow missing, and help me resolve my inability to "simply insert a string into a vector".

here is a look at my BST class and node structure:

template<typename K, typename V> class bst {
public:	class node {	
public:	
node(const K& key = K(), const V& value = V())
   {
   }
   K key;
   std::vector<V>* value;// I hope this is the correct method...	
   node* L;
   node* R;
};

and here is a look at my insert function which works fine when creating a new node:

bool insert(const K& key, const V& value) {
		node** n = _search(key);
		if (*n == 0) {
			*n = new node(key, value);
			node_count++;
			return true;
		}
// Here is where I obviously need to "insert"
//I have tried dozens of (WRONG) combinations such as:  
//(*n).value.insert((V)value); but I have failed
//
		return false;
	}

As I have stated before, I am obviously missing something, and it feels like it should be so simple that I am nearly ashamed to ask...
Can anyone please help to enlighten me as to how I can (Or why I cannot) insert into my nodes vector?

Thank you in advance;

Last.

[ne555]

Do you want a multimap?

class node {	
public:	
node(const K& key = K(), const V& value_ = V())
   { //nothing? shouldn't value_ be inserted in value?
   }
   K key;
   std::vector<V>* value;// Why a pointer instead of an object?
   node* L;
   node* R;
};

//I have tried dozens of (WRONG) combinations such as:  
//(*n).value.insert((V)value); but I have failed

//According to your code
//n is a pointer to a pointer
// *n is a pointer
// value is a pointer
(*n)->value->insert(value);

[Last Resort]

Thank you for such a quick reply!

No thank you on the multimap suggestion, as I have already finished a multimap implementation, and want to be able to extend a bst.

node(const K& key = K(), const V& value_ = V()) : key(key),left(0), right(0)
   { //nothing? shouldn't value_ be inserted in value?
   }

I am not 100% sure how to insert my value(value)...I tried a value.push_back(value), but that gave me an error code c2663:'std::vector<_Ty>::push_back':2 overloads have no legal conversion for 'this' pointer
I also tried
node(const K& key = K(), const V& value_ = V()) : key(key),value(value),left(0), right(0)
but that failed also.

but that seemed like a trivial "problem" in comparison to my posted issue which I have seriously spent >36 hours working on!!!

Talk about Serious undue mental hardships and frustration!
:)

Your code suggestion seemed to work: its error code politely told me that 'insert needs two arguments', but insert() needs a position which I cannot provide beyond the first item...

Yet, if I alter your code, and try to use a (*n)->value->push_back(value) I get the same error as when I try to push_back() within the constructor:
error code c2663:'std::vector<_Ty>::push_back':2 overloads have no legal conversion for 'this' pointer

I have no clue why I would be allowed to insert, but not push_back?

I'm sure I just need a new perspective! Thank you for yours!

Thanks again!

Last

[ne555]

I tried a value.push_back(value)

First, the names are confusing. Second, value is a pointer to a vector.
Change the node class declaration and make value a vector. std::vector<V> value;

its error code politely told me that 'insert needs two arguments', but insert() needs a position which I cannot provide beyond the first item...

Sorry about that. value.insert(value.end(), value_); should be equivalent to value.push_back(value_);

error code c2663:'std::vector<_Ty>::push_back':2 overloads have no legal conversion for 'this' pointer

Sorry, could not reproduce the error. Please post the updated code

[Last Resort]

Good day!
I changed the vector pointer to a vector, and renamed the vector to items... I am accustomed to Java having a 'this.', but cannot seem to achieve the same functionality in c++.

template<typename K, typename V> class bst {
public:
	class node {
	public:
		node(const K& key = K(), const V& value = V()) : key(key), left(0), right(0) {
//error code c2663:'std::vector<_Ty>::insert' : 3 overloads have no legal conversion for 'this' pointer
				values.insert(values.end(), value);
		}

		K key;
		const std::vector<const std::string> values;
		int numRecords;
		node* left;
		node* right;
	};

/* Inserts a new node containing key 'key' and value 'value' into the tree.
	Returns true if the node was added, false if the node already exists. */
	bool insert(const K& key, const V& value) {
		node** n = _search(key);
		if (*n == 0) {
			*n = new node(key, value);
			node_count++;
			return true;
		}
		// insert
// error c2100:  illegal indirection
// error c2663: 'std::vector<_Ty>::insert' : 3 overloads have no legal conversion for 'this' pointer.
		(*n)->values.insert((*n)->values.end(), value);

		return false;
	}

Each posted error is disjointedly unique...I compiled each line of code separately.

I am only trying to store an std::string in the vector, so I can search it later!

I am amazed at how complex something so simple in principle can be to implement!!!

Thank you ne555!

Last

[ne555]

In c++ there is the this pointer.

Is actually quite simple

map<int, vector<string> > bst;
bst[42].push_back("hello");

template<typename K, typename V> 
class bst {
public:
	class node {
	public:
		node(const K& key = K(), const V& value = V()) : key(key), left(0), right(0) {
			this->items.push_back(value);
		}
		
		K key;
		std::vector<V> items;
		int numRecords;
		node* left;
		node* right;
	};
};

That should compile. How are you using the class?

[Last Resort]

True ... I should have said that is not easy to get it to work in the context of this particular implementation!

to test my multiMap, I have been iterating through a directory tree and using unique directory paths as the key, I store the directories files names within the value... multimap basically does it for me!

I am trying to do the same thing here with the bst/vector combination. I just cannot get anything to work as it (simply) should.

I tried

node(const K& key = K(), const V& value = V()) : key(key), left(0), right(0) {
			this->items.push_back(value);

but I got an "unhandled exception in my.cpp: access violation reading location 0x00000014" error as soon as the first node is attempted to be inserted.
the error window opens up the xstring library (std::basic_string<_Elem,_traits,_Ax>)
and points to line 1512:
size_type size() const{
return this->_Mysize; } <-- error window points to the return statement.

I click on "break", and there are no errors in the error list.

If I change the your code to an insert:
this->values.insert(this->values.end() , value);
I get the error
error c2664:'std::_Vector_iterator<_Myvec>std::vector<_Ty>::insert<const V&>
(std::_Vector_const_iterator<_Myvec>,_Valty)':cannot convert parameter 1 from 'unsigned int' to 'std::_Vector_const_iterator<_Myvec>'

Is this saying that I am sending it an int, but it wants an iterator? I would swear that an insert is supposed to take an int.

Oy Vey!

And this was supposed to be the "easier" portion of my code... in contrast to the insert() method which I originally posted the question about!!! Although I can see that they are the same problem: I am still having trouble inserting any strings into my vector container?

Thank you so much for your time, as I find this task to be extremely frustrating. I have coded for years and I have never been defeated by two lines of code before.

Obsessed, all I can do is keep hacking away at it.

Last